{"raw_statement":[{"iden":"problem statement","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?"},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"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"},{"iden":"sample output 1","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}