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

Среди членов сопротивления, которых Уйэд называет «Другими», есть строгая иерархия в виде подвешенного дерева. В корне находится лидер сопротивления под номером $$$1$$$, и у каждого другого члена сопротивления есть один непосредственный начальник, всего $$$n$$$ мутантов.

Чтобы организоваться к сражению с Кассандрой Новой, необходимо для этого сначала оценить, каковы их шансы, и продумать план. Для этого необходимо для нескольких ключевых членов сопротивления (таких, как Электра, Блейд, Гамбит и X-23), определить количество их подчиненных $$$d$$$-го уровня.

Подчиненные $$$d$$$-го уровня в организации определяются следующим образом:

Иными словами, это все потомки данной вершины в дереве на расстоянии ровно $$$d$$$ от нее. Ответьте на $$$q$$$ запросов описанного вида.

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

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

В следующей строке даны $$$n - 1$$$ целых чисел $$$p_2,\ldots,p_{n}$$$ — номера непосредственных начальников членов организации со второго по $$$n$$$-го ($$$1 \le p_i < i$$$).

В последних $$$q$$$ строках содержатся запросы, каждый из которых задается парой целых чисел $$$v_i$$$ и $$$d_i$$$ — номером члена организации и интересующего уровня подчиненных ($$$1 \le v \le n$$$; $$$0 \le d \le n - 1$$$).

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

Выведите $$$q$$$ строк, в $$$i$$$-й из которых должен идти ответ на $$$i$$$-й запрос — целое число от $$$0$$$ до $$$n$$$.

Пример

Входные данные
5 5
1 1 3 3
1 1
1 2
3 1
3 0
2 2
Выходные данные
2
2
2
1
0