G. Лава в Джейлбрейке
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После большого взрыва в Джейлбрейке на арене появились опасные вулканы! Тебе, как бойцу Brawl Stars, нужно уметь предсказывать распространение лавы, чтобы избежать поражения.

На прямой расположены $$$n$$$ вулканов. $$$i$$$-й вулкан начинает извергаться в момент времени $$$t_i$$$ из точки $$$p_i$$$ с максимальной высотой лавы $$$h_i$$$.

Лава распространяется по следующим правилам:

  • В момент извержения ($$$t_i$$$) в точке $$$p_i$$$ высота лавы равна $$$0$$$.
  • За каждую единицу времени лава распространяется на $$$1$$$ единицу расстояния в обе стороны.
  • Высота лавы в точке $$$p_i + y$$$ в момент времени $$$t_i + x$$$ после извержения вычисляется как $$$\min(\max(0, x - |y|), h_i)$$$.
  • Если лава из нескольких вулканов достигает одной точки, берется максимальная высота.

Тебе нужно ответить на $$$q$$$ запросов: для момента времени $$$T$$$ и точки $$$X$$$ определи высоту лавы.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ — количество вулканов и запросов ($$$1 \le n, q \le 2 \cdot 10^5$$$).

Следующие $$$n$$$ строк содержат по три целых числа $$$t_i$$$, $$$p_i$$$, $$$h_i$$$ — параметры вулканов ($$$0 \le t_i \le 10^9$$$, $$$-10^9 \le p_i \le 10^9$$$, $$$1 \le h_i \le 10^9$$$).

Следующие $$$q$$$ строк содержат по два целых числа $$$T_j$$$, $$$X_j$$$ — параметры запросов ($$$0 \le T_j \le 10^9$$$, $$$-10^9 \le X_j \le 10^9$$$).

Выходные данные

Для каждого запроса выведите одно целое число — высоту лавы в точке $$$X_j$$$ в момент времени $$$T_j$$$.

Примеры
Входные данные
2 3
1 0 3
3 5 2
2 1
4 2
5 6
Выходные данные
0
1
1
Входные данные
1 2
0 0 5
1 1
2 3
Выходные данные
0
0