{"problem":{"name":"Ex - Manhattan Christmas Tree","description":{"content":"There are $N$ Christmas trees in the two-dimensional plane. The $i$\\-th tree is at coordinates $(x_i,y_i)$. Answer the following $Q$ queries. > Query $i$: What is the distance between $(a_i,b_i)$ and","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc233_h"},"statements":[{"statement_type":"Markdown","content":"There are $N$ Christmas trees in the two-dimensional plane. The $i$\\-th tree is at coordinates $(x_i,y_i)$.\nAnswer the following $Q$ queries.\n\n> Query $i$: What is the distance between $(a_i,b_i)$ and the $K_i$\\-th nearest Christmas tree to that point, measured in Manhattan distance?\n\n## Constraints\n\n*   $1\\leq N \\leq 10^5$\n*   $0\\leq x_i\\leq 10^5$\n*   $0\\leq y_i\\leq 10^5$\n*   $(x_i,y_i) \\neq (x_j,y_j)$ if $i\\neq j$.\n*   $1\\leq Q \\leq 10^5$\n*   $0\\leq a_i\\leq 10^5$\n*   $0\\leq b_i\\leq 10^5$\n*   $1\\leq K_i\\leq N$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$\\vdots$\n$x_N$ $y_N$\n$Q$\n$a_1$ $b_1$ $K_1$\n$\\vdots$\n$a_Q$ $b_Q$ $K_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc233_h","tags":[],"sample_group":[["4\n3 3\n4 6\n7 4\n2 5\n6\n3 5 1\n3 5 2\n3 5 3\n3 5 4\n100 200 3\n300 200 1","1\n2\n2\n5\n293\n489\n\nThe distances from $(3,5)$ to the $1$\\-st, $2$\\-nd, $3$\\-rd, $4$\\-th trees to that point are $2$, $2$, $5$, $1$, respectively.  \nThus, the answers to the first four queries are $1$, $2$, $2$, $5$, respectively."]],"created_at":"2026-03-03 11:01:14"}}