11. Доставка

В городе $N$ есть один прямой проспект, на котором каждый дом имеет целочисленные координаты.

В городе $N$ есть $n$ складов. Вашему интернет-магазину требуется обработать $m$ заказов. $i$-й склад находится в точке $s_i$, а $i$-й заказ приходит из дома в точке $c_i$. Координаты любых двух складов различны, но координаты заказов могут совпадать.

Вам нужно минимизировать издержки для каждого заказа. А именно: стоимость товара на складах разная, равно как и стоимость бензина для доставки. Формально забрать товар с $i$-го склада стоит $p_i$. Доставка из точки $x_1$ в точку $x_2$ стоит $(x_1 – x_2)^2$.

К сожалению, на некоторых складах нет нужных товаров. А именно: $i$-й заказ нельзя доставить со складов $d_{i,1}, \dots, d_{i,k_i}$.

Для каждого заказа найдите минимальную себестоимость доставки заказа.

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 200\ 000$) — количество складов и заказов соответственно.

-я из следующих $n$ строк содержит два целых числа $s_i$ и $p_i$ ($0 \le s_i \le 10^9$, $1 \le p_i \le 10 ^ 9$) — координата $i$-го склада и цена на получение любого товара в нём соответственно.

-я из следующих $m$ строк содержит целые числа $c_i$, $k_i$, $d_{i,1}, \dots, d_{i,k_i}$ ($0 \le c_i \le 10^9$, $0 \le k_i \le n – 1$, $1 \le d_{i,j} \le n$) — координата для доставки $i$-го заказа, количество складов, которые не хранят нужный товар, и номера этих складов соответственно.

Также гарантируется, что $\sum k_i \le 400\ 000$.

Выведите $m$ чисел, $i$-е из которых — себестоимость доставки $i$-го заказа.

Первый заказ доступен везде и будет стоить $7 + (3 – 1)^2 = 11$ при заказе из первого склада.

Второй заказ нельзя доставить с первого склада, но можно доставить со второго склада за $9 + (10 – 3)^2 = 34$.

Третий заказ доступен только на третьем складе, где стоимость составляет $9 + (8 – 6)^2 = 13$.