{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/JULY18/mandarin/PDELIV.pdf\"\u003eMandarin chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/JULY18/russian/PDELIV.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/JULY18/vietnamese/PDELIV.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\nFlatland is a 1D country — all points in Flatland lie on one line. Everybody in Flatland loves pizza (because it\u0027s flat enough).\r\n\r\nThere are $n$ pizzerias numbered $1$ through $n$, which serve $m$ consumers numbered $1$ through $m$. Let\u0027s denote the position of the $i$-th pizzeria by $s_i$ and the position of the $i$-th consumer\u0027s home by $c_i$. No two pizzerias are located at the same position, but the position of any consumer can coincide with the position of any pizzeria or consumer.\r\n\r\nEvery consumer wants to order one pizza, spending as little money as possible. The $i$-th pizzeria sells each pizza at a certain baseline price $p_i$; delivering pizza from point $x_1$ to point $x_2$ costs an additional $(x_1 - x_2) ^ 2$. These prices are independent — even if multiple pizzas can be delivered at once, each consumer needs to pay the full price for their delivery.\r\n\r\nUnfortunately, some consumers don\u0027t like some pizzerias, so they won\u0027t order pizza from them. Specifically, for each consumer, you are given a list of pizzerias this consumer won\u0027t order from no matter what.\r\n\r\nFor each consumer, find the amount of money they will spend for the pizza with delivery.\r\n\r\n### Input\r\n- The first line of the input contains two space-separated integers $n$ and $m$ denoting the number of pizzerias and the number of consumers.\r\n- For each $i$ ($1 \\le i \\le n$), the $i$-th of the following $n$ lines contains two space-separated integers $s_i$ and $p_i$.\r\n- For each $i$ ($1 \\le i \\le m$), the $i$-th of the following $m$ lines contains two space-separated integers $c_i$ and $k_i$, followed by a space (if $k_i \\gt 0$) and $k_i$ space-separated integers $d_{i, 1}, d_{i, 2}, \\dots, d_{i, k_i}$ denoting the list of pizzerias the $i$-th consumer won\u0027t order from.\r\n\r\n### Output\r\nPrint $m$ lines. For each $i$ ($1 \\le i \\le m$), the $i$-th of these lines should contain a single integer — the amount of money the $i$-th consumer will spend.\r\n\r\n### Constraints \r\n- $1 \\le n, m \\le 200,000$\r\n- $0 \\le s_i, c_i \\le 10^9$ for each valid $i$\r\n- $1 \\le p_i \\le 10^9$ for each valid $i$\r\n- $0 \\le k_i \\le n-1$ for each valid $i$\r\n- $0 \\le \\sum_{i\u003d1}^m k_i \\le 400,000$\r\n- $1 \\le d_{i, j} \\le n$ for each valid $i, j$\r\n- $s_1, s_2, \\dots, s_n$ are pairwise distinct\r\n\r\n### Subtasks\r\n**Subtask #1 (15 points):** $n, m \\le 1,000$\r\n\r\n**Subtask #2 (35 points):** $k_i \u003d 0$ for each valid $i$\r\n\r\n**Subtask #3 (50 points):** original constraints"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3 3\r\n1 7\r\n10 5\r\n8 9\r\n3 0\r\n3 1 1\r\n6 2 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\r\n34\r\n13\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nThe first consumer likes all the pizzerias, so they order a pizza from the first pizzeria, since it will cost the least, $7 + (3 - 1)^2 \u003d 11$.\r\n\r\nThe second consumer doesn\u0027t like the first pizzeria, so they won\u0027t order from there, even though it\u0027s the cheapest option. Therefore, they order a pizza from the third pizzeria. It costs $9 + (8 - 3)^2 \u003d 34$.\r\n\r\nThe third consumer likes only the third pizzeria, so they order from there. It costs $9 + (8 - 6)^2 \u003d 13$."}}]}