eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Брати по крові наносять удар у відповідь

Брати по крові наносять удар у відповідь

Ліміт часу 1 секунда
Ліміт використання пам'яті 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-бітних чисел. Детальний опис операції дивіться у примітці.

Вхідні дані

У першому рядку вхідних даних записано єдине ціле число 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).

Гарантується, що сімейні зв'язки не утворюють циклів.

Вихідні дані

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

Примітка

Результат операції побітового ОТЖЕ двох 30-бітних чисел — це 30-бітне число, кожен з 30 біт якого отримується операцією бітового ОТЖЕ двох бітів операндів. Зокрема

10 32 = 1073741813.

Таблиця істинності для операції ОТЖЕ для бітів:

  • 00 = 1;

  • 01 = 1;

  • 10 = 0;

  • 11 = 1.

Приклад

Вхідні дані #1
6
1 0
1 1
0 1
3 2
4 2
5 2
4
1 1
1 2
2 1
3 1
Вихідні дані #1
1073741822
1073741823
1073741823
0