Брати по крові наносять удар у відповідь
Полікарп роздобув дерево сімейних зв'язків. Знайдене дерево описує сімейні зв'язки 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.