Fişierul de intrare $brperm.in$ contine pe primul rand numarul $N$ de noduri.
Al doilea rand contine cate $N - 1$ numere, iar al $i$-lea este tatal nodului $i$ in arbore (retineti ca nodul $0$ este radacina). Se garanteaza ca tatal unui nod are indicele mai mic ca el.
Al treilea rand contine un sir de $N - 1$ caractere, din care al $i$-lea caracter este caracterul pe muchia dintre $i$ si tatal sau.

Al patrulea rand contine valorile $Q X{~1~} Y{~1~} a b c d$.

Al patrulea rand contine valorile $Q X{~1~} Y{~1~} a b c d$. $Q$ reprezinta numarul de query-uri.
Fie $A{~i~}$ al $i$-lea nod de query, si $2^B{~i~}^$ a $i$-a lungime de query. Fie $R{~i~}$ raspunsul la cel de al $i$-lea query: 1 daca si numai daca lantul de la $A{~i~}$ in sus de lungime $2^B{~i~}^$ este $br-palindrom$, 0 altfel. Acestea se calculeaza dupa formulele:
$X{~i+1~} = (i + X{~i~} + R{~i~}) * a + b mod 1.000.000.007$
$Y{~i+1~} = (i + Y{~i~} + R{~i~}) * c + d mod 1.000.000.007$
$A{~i~} = X{~i~} mod N$
$B{~i~} = Y{~i~} mod log{~2~}(lungimea lantului de la A{~i~} la radacina)$

h2. Date de ieşire

În fişierul de ieşire $brperm.out$ se afiseaza numerele $X{~Q+1~} Y{~Q+1~}$. Acestea se definesc dupa recurentele urmatoare:
 
$A{~i~} = X{~i~} mod N$
$B{~i~} = Y{~i~} mod log{~2~}(lungimea lantului de la A{~i~} la radacina)$
$R{~i~} = 1 daca lantul de lungime $2^B{~i~}^$ de la $A{~i~}$ insrep radacina este br-permutare, 0 altfel$.
$X{~i+1~} = (i + X{~i~} + R{~i~}) * a + b mod 1.000.000.007$
$Y{~i+1~} = (i + Y{~i~} + R{~i~}) * c + d mod 1.000.000.007$

În fişierul de ieşire $brperm.out$ se afiseaza numerele $X{~Q+1~} Y{~Q+1~}$.

h2. Restricţii