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

Полікарп натрапив на родовід, що описує взаємини між $n$ людьми, пронумерованими від $1$ до $n$. Кожна особа в цьому дереві може мати не більше одного безпосереднього предка. Крім того, кожен має коня певного типу: людина $x$ володіє конем типу t_x. Зверніть увагу, що типи коней можуть повторюватися.

Особа під номером $a$ називається $1$-предком особи $b$, якщо $a$ є безпосереднім предком $b$.

Для k > 1, особа під номером $a$ є $k$-предком особи $b$, якщо у $b$ є $1$-предок, і $a$ є (k-1)-предком цього $1$-предка $b$.

Родовід є ациклічним, тобто жодна особа не є власним предком ні безпосередньо, ні опосередковано (тобто нема такої особи, що вона є $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, \ldots, p_r (p_1 < p_2 < \ldots < p_r) обчислюється як (t_{p_1} \rightarrow (t_{p_2} \rightarrow (\ldots \rightarrow t_{p_r}))). Якщо множина порожня, то кінна цінність дорівнює нулю. Операція x \rightarrow y означає побітову операцію THEN над двома $30$-бітними числами. Детальніше про цю операцію дивіться в поясненні внизу.