eolymp
bolt
Try our new interface for solving problems
Problems

Братья по крови наносят ответный удар

Братья по крови наносят ответный удар

Time limit 1 second
Memory limit 256 MiB

Поликарп раздобыл дерево родственных связей. Найденное дерево описывает родственные связи n человек, пронумерованных от 1 до n. Каждый человек в этом дереве имеет не более одного непосредственного предка. Также каждый человек в дереве имеет коня некоторого типа, человек номер x имеет коня типа t_x. Типы коней не обязательно уникальные.

Назовем человека с номером a1-предком человека с номером b, если человек с номером a является непосредственным предком человека с номером b.

Назовем человека с номером a k-предком (k > 1) человека с номером b, если у человека с номером b есть 1-предок, и человек с номером a является (k-1)-предком 1-предка человека с номером b.

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

Назовем человека с номером ak-сыном человека с номером b, если человек с номером b является k-предком человека с номером a.

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

Конностью множества людей p_1, p_2, ..., p_r (p_1 < p_2 < ... < p_r) называется число (p_1 → (p_2 → (... → p_r))). Конностьпустого множества равно нулю. Здесь операция xy обозначает операцию побитового СЛЕДОВАТЕЛЬНО двух 30-битных чисел. Подробное описание операции смотрите в примечании.

Input data

В первой строке входных данных записано единственное целое число n (1n10^5) — количество людей в дереве. В следующих n строках записано описание людей в дереве. В i-той из этих строк записаны через пробел целое число t_i и целое число r_i (0t_i10^9, 0r_in), где t_i — тип коня человека с номером i, а r_i — номер непосредственного предка человека с номером i или 0 если у человека с номером i нет непосредственного предка.

В следующей строке записано единственное целое число m (1m10^5) — количество записей Поликарпа. В m следующих строках записаны пары целых чисел через пробел. В i-ой строке записаны целые числа v_i, k_i (1v_i, k_in).

Гарантируется, что родственные связи не образуют циклов.

Output data

Выведите m целых чисел, разделенных пробельными символами, — ответы на записи Поликарпа. Ответы для записей выводите в том порядке, в котором записи встречаются во входных данных.

Examples

Input example #1
6
1 0
1 1
0 1
3 2
4 2
5 2
4
1 1
1 2
2 1
3 1
Output example #1
1073741822
1073741823
1073741823
0

Note

Результат операции побитового СЛЕДОВАТЕЛЬНО двух 30-битных чисел — это 30-битное число, каждый из 30 бит которого получается операцией битового СЛЕДОВАТЕЛЬНО двух битов операндов. В частности

10 32 = 1073741813.

Таблица истинности для операции СЛЕДОВАТЕЛЬНО для битов:

  • 00 = 1;

  • 01 = 1;

  • 10 = 0;

  • 11 = 1.