G. Сообщения на дереве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб известны своей любовью к передаче сообщений друг другу. В этот раз у них есть корневое дерево, где Боб находится в корне, а во всех остальных вершинах находится по одной копии Алисы. Корневая вершина имеет номер 0, а остальные пронумерованы от 1 до n.

В некоторые моменты времени некоторая из копий Алисы отправляет Бобу сообщение и хочет получить на него ответ. Назовём такую копию инициатором. Процесс отправки сообщения проходит следующим образом:

  • Инициатор посылает сообщение человеку, стоящему в вершине, являющейся предком вершины инициатора, и начинает ждать ответа.
  • Когда какая-то из копий Алисы получает сообщение от кого-либо из вершин-потомков, она посылает это сообщение в вершину-предка и начинает ждать ответа.
  • Когда Боб получает сообщение от кого-то стоящего в непосредственном ребёнке корня, он сразу отправляет в эту вершину ответ.
  • Когда какая-либо из копий Алисы (не инициатор) получает ответ, которого она ожидает, она немедленно отправляет его в ту дочернюю вершину, из которой пришёл запрос.
  • Когда инициатор получает ожидаемый ответ, она становится свободной и никому ничего не посылает.
  • Есть особый случай: никакая копия Алисы не может одновременно ждать ответа на два сообщения, поэтому если какая-то копия получает сообщение, когда она уже ждёт ответа на другое сообщение, то она просто отклоняет запрос, отправляя его вершине, которая его прислала. Далее копии Алисы обрабатывают этот ответ так же, как если бы он пришёл от Боба.
  • Передача сообщения родительской вершине или ответа ребёнку происходит мгновенно, но сообщение или ответ доходит до получателя всегда через 1 секунду.

Если какая-то из копий Алисы получает несколько сообщений из вершин-потомков одновременно, и в этот момент данная копия не занята ожиданием ответа, то она обрабатывает сообщение, посланное инициатором с минимальным номером, а все остальные отклоняет. Если какая-либо из копий Алисы получает одновременно сообщение от потомка и ответ, которого она ожидает, то считается, что она успевает сначала обработать ответ, а затем в ту же секунду обработать пришедшие сообщения как обычно.

Вам даны моменты времени, в которые копии Алисы становятся инициаторами и отправляют сообщения Бобу. Для каждого сообщения найдите момент времени, когда инициатор получит ответ (от Боба или от какой-то из копий Алисы).

Можете считать, что если какая-то из Алис хочет отправить сообщение (то есть стать инициатором) в момент ожидания ответа, она сама немедленно отклоняет это сообщение и получает ответ сама от себя за нулевое время.

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

В первой строке входных данных записаны два целых числа n и m (1 ≤ n, m ≤ 200 000) — количество вершин с копиями Алисы и количество сообщений, которые будут отправлены.

Во второй строке содержится n целых чисел p1, p2, ..., pn (0 ≤ pi < i), i-е из этих чисел означает номер предка вершины с номером i.

Следующие m строк описывают сообщения. В i-й из них записаны два целых числа xi и ti (1 ≤ xi ≤ n, 1 ≤ ti ≤ 109) — номер вершины, в которой расположена копия Алисы, являющаяся инициатором, и момент времени, когда она это делает (в секундах). Сообщения даются в порядке возрастания времени создания, то есть ti + 1 ≥ ti для 1 ≤ i < m. Гарантируется, что все пары (xi, ti) различны.

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

Выведите m целых чисел, i-е из которых должно быть равно моменту времени, в который инициатор i-го сообщения получит ответ.

Примеры
Входные данные
6 3
0 1 2 3 2 5
4 6
6 9
5 11
Выходные данные
14 13 11
Входные данные
3 2
0 1 1
2 1
3 1
Выходные данные
5 3
Входные данные
8 3
0 1 1 2 3 3 4 5
6 1
8 2
4 5
Выходные данные
7 6 11
Примечание

В первом примере первое сообщение инициируется в момент времени 6, достигает Боба в момент времени 10, а инициатор получает ответ в момент времени 14. Второе сообщение достигает вершины 2 в момент времени 11. В это время копия Алисы во второй вершине все еще ждет ответа на первое сообщение, поэтому отклоняет второе. Ответ достигает инициатора в момент времени 13. Третье сообщение вообще никому не отправляется, т. к. в момент времени 11 Алиса в вершине 5 ждет ответа на второе сообщение.

Во втором примере первое сообщение достигает Боба, а второе отклоняется Алисой в вершине 1, т. к. приоритет имеет сообщение, отправленное инициатором с меньшим номером.

В третьем примере первое и третье сообщение достигнут Боба, а второе будет отклонено Алисой в вершине 3.