408691: GYM103262 F Divan любит тыквы

Однажды стране Берляндии очень понадобились деньги, и было принято решение продать прекрасный парк с тыквами. К большому счастью правителей Берляндии, в мире есть ровно один бизнесмен, который может выкупить этот парк — Divan.

Узнав о таком заманчивом предложении, Divan первым делом поинтересовался, а что же представляет собой этот парк? Ему ответили, что это множество тыкв. Некоторые из них соединены между собой дорогами, да так, что между любой парой тыкв существует лишь один путь. (Строго говоря, парк — это дерево с тыквами в вершинах.) Всего парк состоит из $$$n$$$ тыкв.

Такой ответ устроил бизнесмена, и обсуждение сделки продолжилось. Так как парк тыкв — не особо практичная вещь, Divan хочет, чтобы она была удивительной. Узнав план парка, Divan решил, что будет водить по нему своих друзей. Для этого он разработает несколько маршрутов. Каждый маршрут будет задаваться парой вершин $$$(v, u)$$$. Это значит, что маршрут начинается в $$$v$$$ и идет до $$$u$$$ по единственному пути.

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

Так как Divan — самый богатый бизнесмен мира, он не утруждает себя логичностью построения маршрутов. Он просто выдумывает их и спрашивает у государства Берляндии: а если бы я повел друзей из $$$v$$$ в $$$u$$$, то сколько раз они бы удивились? После чего ждет ответа, и все повторяется заново, пока Divan не устанет. А это может быть ой как не скоро, ведь он готов задать $$$q$$$ вопросов.

Помогите правительству побороть кризис, ответив на все вопросы Divanа.

На первой строке входных данных находится два числа $$$n$$$ и $$$q$$$ — количество тыкв в парке и количество вопросов ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq q \leq 200\,000$$$).

На второй строке входных данных находятся $$$n$$$ целых чисел $$$W_1$$$, $$$W_2$$$, ..., $$$W_n$$$ — размер тыкв ($$$1 \leq W_i \leq n$$$).

Далее следует $$$n-1$$$ строка, в каждой из которых записано два числа $$$a$$$ и $$$b$$$ ($$$1 \leq a, b \leq n$$$, при этом $$$a \neq b$$$) — номера тыкв, которые соединяет очередная дорога.

Гарантируется, что от любой тыквы к любой другой можно пройти, и притом единственным способом.

Далее следует $$$q$$$ строк, каждая из которых содержит два числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \leq x_i, y_i \leq n$$$) — зашифрованный запрос.

Для того чтобы узнать настоящий запрос, нужно положить $$$v_i = (x_i + p) \bmod n + 1$$$, $$$u_i = (y_i + p) \bmod n + 1$$$, где $$$v_i$$$ — начало пути для очередного запроса, $$$u_i$$$ — конец пути, $$$p$$$ — ответ на предыдущий запрос, а $$$\bmod$$$ — операция взятия остатка от деления. Для первого запроса $$$p = 0$$$.

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

Подзадача 1, 40 баллов: $$$n, q \le 5000$$$.

Подзадача 2, 60 баллов: дополнительных ограничений нет.

6 3
2 4 2 1 3 1
1 3
2 3
3 4
5 3
6 5
5 1
0 3
5 1

3
2
1

Парк тыкв в примере можно схематично изобразить следующим образом:

где окружности представляют собой тыквы. Внутри окружности подписан номер соответствующей тыквы, а снаружи — её размер.

В примере $$$n=6$$$ и заданы три запроса. Первый зашифрованный запрос — $$$x_1 = 5, y_1 = 1$$$. Поскольку $$$p=0$$$, получаем настоящий запрос $$$u_1 = (5 + 0) + 1 = 6$$$, $$$v_1 = (1 + 0) + 1 = 2$$$. Маршрут между этими тыквами проходит через тыквы — $$$6, 5, 3, 2$$$, соответственно, их размеры равны $$$1, 3, 2, 4$$$. На этом маршруте друзья будут удивляться 3 раза — при виде тыкв с размерами $$$1, 3, 4$$$.

Второй зашифрованный запрос — $$$x_2 = 0, y_2 = 3$$$. Поскольку ответ на предыдущий запрос — 3, то получаем $$$u_2 = (3 + 0) + 1 = 4, v_2 = (3 + 3) \bmod 6 + 1 = 1$$$. Маршрут проходит через тыквы $$$4, 2, 1$$$ с размерами $$$1, 2, 2$$$. Друзья удивятся при виде первых двух тыкв, поэтому ответ — 2. Обратите внимание, что при виде второй тыквы размера $$$2$$$ друзья не удивляются.

В третьем запросе $$$x_3 = 5, y_3 = 1$$$, $$$u_3 = (5 + 2) \bmod 6 + 1 = 2$$$, $$$v_3 = (1 + 2) + 1 = 4$$$. Маршрут проходит через тыквы $$$2, 3, 4$$$ размерами $$$4, 2, 1$$$. Друзья удивляются только при виде первой тыквы маршрута. Обратите внимание, что зашифрованный запрос совпадает с первым: $$$x_3 = x_1 = 5$$$, $$$y_3 = y_1 = 1$$$. Однако, поскольку ответ на предыдущий запрос ($$$p$$$) изменился, то реальные значения $$$u_3, v_3$$$ отличаются от первого запроса, поэтому ответ на него тоже другой.