Поликарп раздобыл дерево родственных связей. Найденное дерево описывает родственные связи \textbf{n} человек, пронумерованных от \textbf{1} до \textbf{n}. Каждый человек в этом дереве имеет не более одного непосредственного предка. Также каждый человек в дереве имеет коня некоторого типа, человек номер \textbf{x} имеет коня типа \textbf{t_x}. Типы коней не обязательно уникальные. Назовем человека с номером \textbf{a} \textbf{1}-предком человека с номером \textbf{b}, если человек с номером \textbf{a} является непосредственным предком человека с номером \textbf{b}. Назовем человека с номером a \textbf{k}-предком (\textbf{k} > \textbf{1}) человека с номером \textbf{b}, если у человека с номером \textbf{b} есть \textbf{1}-предок, и человек с номером \textbf{a} является \textbf{(k-1)}-предком \textbf{1}-предка человека с номером \textbf{b}. В найденном дереве родственные связи не образуют циклов. Другими словами не существует человека, который непосредственно или косвенно является собственным предком (то есть является \textbf{x}-предком самого себя, для некоторого \textbf{x}, \textbf{x} > \textbf{0}). Назовем человека с номером \textbf{a} \textbf{k}-сыном человека с номером \textbf{b}, если человек с номером \textbf{b} является \textbf{k}-предком человека с номером \textbf{a}. Поликарп очень сильно интересуется сколько у кого и каких коней. Он записал на листочке \textbf{m} пар чисел \textbf{v_i}, \textbf{k_i}. Помогите ему для каждой пары \textbf{v_i}, \textbf{k_i} узнать величину \textit{конности} множества \textbf{k_i}-сыновей человека с номером \textbf{v_i}. \textit{Конностью} множества людей \textbf{p_1}, \textbf{p_2}, ..., \textbf{p_r} (\textbf{p_1} < \textbf{p_2} < ... < \textbf{p_r}) называется число (\textbf{p_1} → (\textbf{p_2} → (... → \textbf{p_r}))). \textit{Конность} пустого множества равно нулю. Здесь операция \textbf{x} → \textbf{y} обозначает операцию побитового \textbf{СЛЕДОВАТЕЛЬНО} двух \textbf{30}-битных чисел. Подробное описание операции смотрите в примечании. \InputFile В первой строке входных данных записано единственное целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}) --- количество людей в дереве. В следующих \textbf{n} строках записано описание людей в дереве. В \textbf{i}-той из этих строк записаны через пробел целое число \textbf{t_i} и целое число \textbf{r_i} (\textbf{0} ≤ \textbf{t_i} ≤ \textbf{10^9}, \textbf{0} ≤ \textbf{r_i} ≤ \textbf{n}), где \textbf{t_i} --- тип коня человека с номером \textbf{i}, а \textbf{r_i} --- номер непосредственного предка человека с номером \textbf{i} или \textbf{0} если у человека с номером \textbf{i} нет непосредственного предка. В следующей строке записано единственное целое число \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^5}) --- количество записей Поликарпа. В \textbf{m} следующих строках записаны пары целых чисел через пробел. В \textbf{i}-ой строке записаны целые числа \textbf{v_i}, \textbf{k_i} (\textbf{1 }≤ \textbf{v_i}, \textbf{k_i} ≤ \textbf{n}). Гарантируется, что родственные связи не образуют циклов. \OutputFile Выведите \textbf{m} целых чисел, разделенных пробельными символами, --- ответы на записи Поликарпа. Ответы для записей выводите в том порядке, в котором записи встречаются во входных данных. \Note Результат операции побитового \textbf{СЛЕДОВАТЕЛЬНО} двух \textbf{30}-битных чисел --- это \textbf{30}-битное число, каждый из \textbf{30 }бит которого получается операцией битового СЛЕДОВАТЕЛЬНО двух битов операндов. В частности \textbf{10 }→\textbf{ 32 = 1073741813}. Таблица истинности для операции СЛЕДОВАТЕЛЬНО для битов: \begin{itemize} \item \textbf{0} → \textbf{0 = 1}; \item \textbf{0} → \textbf{1 = 1}; \item \textbf{1} → \textbf{0 = 0}; \item \textbf{1} → \textbf{1 = 1}. \end{itemize}