{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\nLittle Sub is happy to see that you solve his geometry problem quickly, so he comes with another geometry problem for you as the reward.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nGiven a 2-dimensional space described as $\\{(x,y)|0 \\le x\\le M,0\\le y\\le M\\}$ and $N$ points $P_1(x_1,y_1), P_2(x_2,y_2), \\dots, P_N(x_N,y_N)$ (note that different points may share the same coordinate), we define a \"good square\" as a square inside the given 2-dimensional space such that the edges of the square is parallel to the x-axis or the y-axis, and none of the given $N$ points are \u003cb\u003estrictly\u003c/b\u003e inside it.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\u003c/p\u003e\r\nYou\u0027re also given $Q$ queries. In each query, given a coordinate $(u,v)$, please calculate that the largest area of a good square such that $(u,v)$ is \u003cb\u003estrictly\u003c/b\u003e inside.\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\r\n\u003cp\u003e\r\nThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \\le T \\le 10$), indicating the number of test cases. For each test case:\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nThe first line contains two integers $M$ (${2\\leq M\\leq 10^9}$) and $N$ (${0\\leq N\\leq 5000}$), indicating the range of the given 2-dimensional space and the number of the given points.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nFor the following $N$ lines, the $i$-th line contains two integers $X_i$ and $Y_i$ (${0\\le X_i,Y_i\\le M}$), indicating the Euclidean coordinate of the $i$-th point.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nThe next line contains one integer $Q$ (${1\\leq Q\\leq 5000}$), which denotes the number of queries.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nIn the following $Q$ lines, each line contains two integers $u$ and $v$(${0\\le u,v\\le M})$, indicating a query.\r\n\u003c/p\u003e\r\n\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\u003cp\u003e\r\nFor each query, output an integer in one line representing the answer.\r\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5 5\r\n1 4\r\n2 1\r\n3 2\r\n4 1\r\n4 4\r\n3\r\n3 1\r\n2 3\r\n4 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n9\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003ch4\u003eHint\u003c/h4\u003e\r\n\r\n\u003cp\u003e\r\nWe now illustrates the second query of the sample input below.\r\n\u003c/p\u003e\r\n\u003cimg src\u003d\"CDN_BASE_URL/bfdad1a91a119fea44237c9c9e286415?v\u003d1715534795\" alt\u003d\"“example”\"\u003e\r\n"}}]}