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

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

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

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

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

Назовем человека с номером a k-сыном человека с номером 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))). Конность пустого множества равно нулю. Здесь операция x → y обозначает операцию побитового СЛЕДОВАТЕЛЬНО двух 30-битных чисел. Подробное описание операции смотрите в примечании.

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

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

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

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

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

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

Примеры

Примечание

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

10 → 32 = 1073741813.

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

• 0 → 0 = 1;

• 0 → 1 = 1;

• 1 → 0 = 0;

• 1 → 1 = 1.