Qan qardaşları cavab zərbəsi vurur
Polikarp ailə əlaqələrinin ağacını tapdı. Bu ağac n nəfərin ailə əlaqələrini təsvir edir və hər biri 1-dən n-ə qədər nömrələnmişdir. Ağacda hər bir insanın ən çox birbaşa bir əcdadı var. Həmçinin, hər bir insanın müəyyən bir tip atı var, məsələn, x nömrəli insanın t_x tipli atı var. Atların tipləri mütləq unikal deyil.
Əgər a nömrəli insan b nömrəli insanın birbaşa əcdadı olarsa, biz a nömrəli insanı b nömrəli insanın 1-əcdadı adlandıracağıq.
Əgər b nömrəli insanın 1-əcdadı varsa və a nömrəli insan b nömrəli insanın 1-əcdadının (k-1)-əcdadı olarsa, biz a nömrəli insanı k-əcdadı (k > 1) b nömrəli insanın adlandıracağıq.
Ağacda ailə əlaqələri dövr yaratmır. Başqa sözlə, öz əcdadı olan bir insan yoxdur (yəni, özünün x-əcdadı olan bir insan yoxdur, bəzi x üçün, x > 0).
Əgər b nömrəli insan a nömrəli insanın k-əcdadı olarsa, biz a nömrəli insanı k-oğlu b nömrəli insanın adlandıracağıq.
Polikarp maraqlıdır ki, kimdə nə qədər və hansı atlar var. O, bir kağıza m ədəd v_i, k_i cütlüyü yazdı. Ona hər bir v_i, k_i cütlüyü üçün k_i-oğullarının atlıq dərəcəsini öyrənməyə kömək edin.
İnsanlar dəstəsinin atlıq dərəcəsi p_1, p_2, ..., p_r (p_1 < p_2 < ... < p_r) sayılır (p_1 → (p_2 → (... → p_r))). Boş dəstənin atlıq dərəcəsi sıfıra bərabərdir. Burada x → y əməliyyatı iki 30-bitlik ədədin bitwise NƏTİCƏ əməliyyatını ifadə edir. Əməliyyatın ətraflı təsviri qeyddə verilmişdir.
Giriş verilənləri
Giriş məlumatlarının ilk sətirində n (1 ≤ n ≤ 10^5) tam ədədi yazılmışdır — kənddəki insanların sayı. Növbəti n sətirdə kənddəki insanların təsviri verilmişdir. Bu sətirlərin i-ci sətirində boşluqla ayrılmış t_i və r_i (0 ≤ t_i ≤ 10^9, 0 ≤ r_i ≤ n) tam ədədləri yazılmışdır, burada t_i — i nömrəli insanın atının tipi, r_i isə i nömrəli insanın birbaşa əcdadının nömrəsi və ya əgər i nömrəli insanın birbaşa əcdadı yoxdursa 0.
Növbəti sətirdə m (1 ≤ m ≤ 10^5) tam ədədi yazılmışdır — Polikarpın qeydlərinin sayı. Növbəti m sətirdə boşluqla ayrılmış tam ədədlər cütlüyü yazılmışdır. i-ci sətirdə v_i, k_i (1≤ v_i, k_i ≤ n) tam ədədləri yazılmışdır.
Ailə əlaqələrinin dövr yaratmadığı təmin edilir.
Çıxış verilənləri
Polikarpın qeydlərinə cavab olaraq m tam ədəd çıxarın, boşluqla ayrılmış — Polikarpın qeydlərinə cavablar. Qeydlərə cavabları giriş məlumatlarında olduğu sırada çıxarın.
Qeyd
İki 30-bitlik ədədin bitwise NƏTİCƏ əməliyyatının nəticəsi 30-bitlik ədəddir, hər bir 30 bit əməliyyat operandlarının bitwise NƏTİCƏ əməliyyatı ilə əldə edilir. Xüsusilə
10 → 32 = 1073741813.
Bitlər üçün NƏTİCƏ əməliyyatının həqiqət cədvəli:
0 → 0 = 1;
0 → 1 = 1;
1 → 0 = 0;
1 → 1 = 1.