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).
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 A{~1~} U V$. $Q$ reprezinta numarul de query-uri, $A{~1~}$ este primul query.

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, impreuna cu $X{~i~}$, 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~} = X{~i~} mod log{~2~}(lungimea lantului de la A{~i~} la radacina)$

Pentru a determina query-ul $A{~i+1~}$ dandu-se query-ul $A{~i~}$ si raspunsul $R$ la queryul acesta, se foloseste formula $A{~i+1~} = (A{~i~} + R) * U + V mod N$.
h2. Date de ieşire