28622번 - Подземная лаборатория 다국어

문제

Как мы знаем, Элой и Варл отправились на поиски резервной GAIA. Одно из мест, где могла бы она находиться --- заброшенная подземная лаборатория компании <<Далекий Зенит>>.

Лаборатория состоит из $n$ комнат, расположенных в горе. Комната с номером $i$ находится на глубине $d_i \geqslant 0$ метров от уровня земли. Если $d_i = 0,ドル то комната находится на поверхности.

Поскольку лаборатория долгое время не использовалась, комнаты успели замерзнуть и обледенеть, и теперь в комнате номер $i$ расположено $a_i$ единиц льда. Чтобы избавляться от льда и талой воды, между комнатами была построена сеть из $n$ труб. Для каждого $i$ из комнаты номер $i$ выходит ровно одна труба вниз; эта труба ведет в комнату номер $b_i,ドル расположенную на большей глубине. На самой большой глубине расположена единственная комната; труба из нее ведет в подземное озеро.

Пропускная способность каждого метра трубы равна единице воды в минуту. Это означает, что если в комнате есть вода, за оду минуту по трубе из нее вытекает ровно одна единица воды. Кроме того, если в момент времени $t$ минут единица воды начала течь по трубе длины $d_{b_i} - d_i$ из комнаты $i$ в комнату $b_i,ドル то эта единица попадет в комнату $b_i$ в момент времени $t + d_{b_i} - d_i$ минут.

Изначально вода во всех комнатах лаборатории находилась в замерзшем состоянии. Из-за нарушения биосферы в момент времени 0ドル$ минут лед в комнатах на поверхности мгновенно растаял и начал течь по трубам вниз.

Когда растаявшая вода впервые доходит до низа трубы, ведущей в вершину $i,ドル весь лед в этой комнате мгновенно тает, и вода начинает течь по трубе $i \to b_i$ со скоростью 1ドル$ метр в минуту. Обратите внимание, что лед тает моментально, и вода не задерживается в комнате. Другими словами, если к моменту времени $t$ минут в комнату $i$ попала первая единица воды, к тому же моменту времени вода заполнит трубу $i \to b_i$ на одну единицу. Комнаты можно считать неограниченными по объему, то есть вмещающими произвольное количество единиц воды.

Элой подозревает, что оборудование, которое долго находилось в комнатах с большим уровнем воды, могло испортится. Поэтому она хочет узнать, сколько минут в комнате $r_i$ талая вода была на уровне не меньше $x_i$ (в комнате находилось хотя бы $x_i$ единиц воды). Помогите героине узнать ответы на $m$ запросов такого вида.

입력

В первой строке через пробел даны два целых числа $n$ и $m$ --- количество комнат в лаборатории и количество запросов (1ドル \leqslant n \leqslant 10^5$; 1ドル \leqslant m \leqslant 2 \cdot 10^5$).

В следующих $n$ строках дается описание комнат: в $i$-й через пробел перечислены три целых числа $b_i,ドル $d_i$ и $a_i$ --- номер комнаты, в которую ведет труба из комнаты $i,ドル глубина комнаты, и количество замерзшей воды в ней (0ドル \leqslant b_i \leqslant n$; 0ドル \leqslant d_i, a_i \leqslant 10^6$).

Равенство $b_i = 0$ означает, что вода из этой комнаты стекает в подземное озеро неограниченного объема. Гарантируется, что существует единственное $i,ドル для которого $b_i = 0$.

Равенство $d_i = 0$ означает, что комната номер $i$ находится на поверхности. Гарантируется, что если $b_i > 0,ドル то $d_i < d_{b_i}$.

В $i$-й из $m$ следующих строк через пробел даны два целых числа $r_i$ и $x_i$ --- номер комнаты и интересущий уровень воды в ней в рамках $i$-го запроса (1ドル \leqslant r_i \leqslant n$; 1ドル \leqslant x_i \leqslant 10^9$).

출력

В $m$ строках выведите по одному целому числу --- время (в минутах), в течение которого в комнате $r_i$ уровень воды был не меньше $x_i$.

Отвечая на запросы, следует учитывать только то время, когда вода находилась в жидком состоянии.

제한

힌트

Рассмотрим первый тест:

1. В момент времени 0ドル$ минут вода была в замерзшем состоянии. Сразу после этого лед в верхних комнатах начинает таять.
2. Через минуту в первой и второй комнатах будут одна и две единицы воды соответственно. В трубах 1ドル \to 3$ и 2ドル \to 3$ находится по единице воды.
3. Две минуты от начала в первой и второй комнатах будет ноль и одна единица воды, соответственно, а в трубах из них вниз --- по две единицы воды.
4. Поскольку трубы заполнены полностью, в следующий же момент лед в третьей комнате растает, и начнет стекать в озеро со скоростью 1ドル$ ед./минуту, тогда как в комнату из двух труб будет втекать 2ドル$ ед./минуту.
5. К моменту времени 3ドル$ минуты, таким образом, в третьей комнате будет две единицы воды, а комнаты 1ドル$ и 2ドル$ будут пусты. В трубе 1ドル \to 3$ будет оставаться еще одна единица воды в самом низу трубы, тогда как труба 2ドル \to 3$ будет полной.
6. Еще через минуту в третьей комнате накопится три единицы воды, а труба 1ドル \to 3$ опустеет, из-за чего уровень воды в третьей комнате перестанет расти.
7. В момент времени 5ドル$ минут в третьей комнате все еще три единицы воды, но теперь в трубе 2ドル \to 3$ вода закончилась, значит за каждую следующую минуту количество воды в комнате 3ドル$ будет уменьшаться на 1ドル$.

Таким образом, ответы на запросы будут такими:

1. В первой комнате две единицы воды находятся только в момент времени 0ドル,ドル после чего это количество сразу начинает уменьшаться, поэтому ни на каком положительном отрезке времени уровень воды в первой комнате не достигает 2ドル$.
2. Во второй комнате уровень воды никогда не равен 4ドル$.
3. При этом уровень воды больше либо равен 1ドル$ между моментами времени 0ドル$ и 2ドル,ドル то есть ровно 2ドル$ минуты.
4. В третьей комнате уровень воды становится равен 1ドル,ドル как только лед тает (в момент времени 2ドル$), и держится $\geqslant 1$ до момента времени 7ドル,ドル после чего он упадет ниже.
5. Аналогично, он не меньше 2ドル$ между моментами времени 3ドル$ и 6ドル$.
6. И не меньше 3ドル$ между моментами времени 4ドル$ и 5ドル$.

Ниже приведено изменение заполненности комнат для второго примера в первые 10 минут, начиная с 0.