406876: GYM102591 D Бред

У вас есть $$$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