406876: GYM102591 D Бред
Description
У вас есть $$$n$$$ точек с координатами $$$(x_i,y_i)$$$. У каждой точки есть вес $$$p_i$$$
Вес ребра между двумя точками $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$ равен величине $$$|x_1-x_2| * |y_1-y_2|$$$.
Назовем путь в возрастающим если веса вершин на этом пути возрастают.
Длина пути - сумма весов ребер.
Вам даны $$$m$$$ отрезков $$$(l_i, r_i)$$$.
Для каждого отрезка выведите длину возрастающего пути состоящего из всех точек $$$(x_l, y_l), (x_{l + 1}, y_{l + 1})...(x_r, y_r)$$$.
Входные данные
В первой строке два целых числа $$$n, q$$$ $$$(1 \le n, q \le 100000 )$$$ - количество точек и количество отрезков.
В следующих $$$n$$$ строках по три целых числа $$$x_i, y_i, p_i$$$ $$$(1 \le x_i, y_i \le 100000)$$$ - описание точек.
Гарантируется, что все $$$p_i$$$ — различные целые числа от $$$1$$$ до $$$n$$$ (то есть они образуют перестановку).
В следующих $$$q$$$ строках по два целых числа $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ - описание отрезков.
Выходные данныеДля каждого отрезка, выведите ответ.
ПримерВходные данные10 10 61 59 3 97 16 9 2 94 8 57 48 2 91 93 10 30 50 5 75 93 6 67 6 1 61 60 4 56 56 7 9 10 4 6 9 10 3 5 8 10 4 9 2 3 1 7 5 10 2 7Выходные данные
20 2677 20 2619 344 2713 7410 10203 4567 9934