{"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 loves math very much, and has just come up with an interesting problem when he is working on his geometry homework.\n\u003c/p\u003e\n\u003cp\u003e\nIt is very kind of him to share this problem with you. Please solve it with your coding and math skills. Little Sub says that even Mr.Potato can solve it easily, which means it won\u0027t be a big deal for you.\n\u003c/p\u003e\n\u003cp\u003e\nThe problem goes as follows:\r\n\u003c/p\u003e\r\n\u003cdiv style\u003d\"margin-left: 2em; font-size: 14px\"\u003e\r\n\u003cp\u003e\r\n Given two integers $N$ and $K$, and $K$ points $P_1, P_2, \\dots, P_K$ with their Euclidean coordinates $(x_1, y_1), (x_2, y_2), \\dots, (x_K, y_K)$ on a 2-dimensional plane. Different points may share the same coordinate.\n\u003c/p\u003e\n\u003cp\u003e\r\nDefine the function \\[ F(u, v) \u003d \\sum_{i\u003d1}^K f(u, v, i) \\] where \\[ f(u, v, i) \u003d \\begin {cases} (u - x_i) + (v - y_i)\r\n \u0026amp; u \\geq x_i\\ \\text{and}\\ v \\geq y_i \\\\ 0 \u0026amp; \\text{otherwise} \\end {cases} \\] \n\u003c/p\u003e\n\u003cp\u003e\nYou are required to solve several queries.\n\u003c/p\u003e \n\u003cp\u003e\nIn each query, one parameter $C$ is given and you are required to calculate the number of integer pairs $(u, v)$ such that $1 \\leq u,v \\leq N$ and $F(u, v) \u003d C $.\r\n\u003c/p\u003e\r\n\u003c/div\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 1000$), indicating the number of test cases. For each test case:\n\u003c/p\u003e\n\u003cp\u003e\r\nThe first line contains two positive integers $N$ and $K$ ($1 \\le N,K \\le 10^5$).\n\u003c/p\u003e\n\u003cp\u003e\nFor the following $K$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \\le x_i, y_i \\le N$), indicating the coordinate of the $i$-th point.\n\u003c/p\u003e\r\n\u003cp\u003e\nThe next line contains an integer $Q$ ($1 \\le Q \\le 10$), indicating the number of queries.\n\u003c/p\u003e\n\u003cp\u003e\nThe following line contains $Q$ integers $C_1, C_2 \\dots, C_Q$ ($1 \\le C_i \\le 10^{18}$), indicating the parameters for each query.\r\n\u003c/p\u003e\r\n\u003cp\u003e\nIt\u0027s guaranteed that at most 20 test cases has $N, K \\ge 10^4$.\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\r\n\u003cp\u003e\r\nFor each test case, output the answers of queries respectively in one line separated by a space.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nPlease, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!\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\u003e2\r\n4 2\r\n1 1\r\n2 3\r\n5\r\n1 2 3 4 5\r\n15 5\r\n1 1 \r\n7 3 \r\n5 10 \r\n8 6 \r\n7 15\r\n3\r\n25 12 31\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 3 4 1 2\r\n5 11 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}