== include(page="template/taskheader" task_id="brperm") ==

'Editorialul':problema/brperm/editorial

Notă: În enunţ, $b{~1~}...b{~K~}$ reprezintă un întreg scris în notaţie binară, unde <tex> b_1 </tex> este cel mai semnificativ bit, iar b{~K~} este cel mai puţin semnificativ bit.

h2. SE DA UN ARBORE...

Vrăjitoarea Roxana, în timp ce zbura pe mătură prin galaxie, a descoperit o nouă planetă (paneta _BR-PERM_) unde toţi locuitorii erau implicaţi într-un dans ciudat. În acest dans, participanţii stau într-o linie, iar apoi se reordonează. Într-un dans la care participa $2^K^$ locuitori, persoana de pe poziţia $b{~1~}...b{~K~}$ se va muta la poziţia $b{~K~}...b{~1~}$ (indexat de la 0).
Roxana a realizat că fiecare persoana de pe _BR-PERM_ poartă îmbrăcaminte din una dintre cele 26 de culori. Aceste culori vor fi reprezentate de litere din alfabetul latin.
_BR-PERM_-ienii consideră speciale şirurile de dansatori unde secvenţa de culori pe care locuitorii le poarta înainte şi după dans sunt la fel. Ei numesc astfel de secvenţe drăguţe. De exemplu, cand $K=2$, avem un şir de $4$ dansatori $0, 1, 2, 3$ care dupa dans va fi ordonat în următorul fel: $0, 2, 1, 3$. Astfel secvenţa de culori $abba$ este drăguţă, dar $abca$ nu este.
_BR-PERM_-ienii o roagă pe Roxana să îi ajute cu această problemă (se pare că vrăjitoarele mereu ajută oamenii să îşi rezolve problemele. Aceştia îi arată un şir de n dansatori şi o roagă să îi răspundă la mai multe întrebari: "Este secvenţa de lungime $2^K^$ care începe la dansatorul $P$ drăguţă?

Poveste şi cerinţă...
 
Am considerat ca sunt date anumite queryuri in input, daca secventa cutare e sau nu br-palindrom. Desigur, putem schimba formatul asta in varianta originala, in caz ca devine inutila schimbarea.
 
 
*Queryurile sunt doar pe lantul catre radacina* - nu vrem lca-uri si alte nebunii

h2. Date de intrare

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$. $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)$
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$.

Fişierul de intrare "brperm.in" conţine, pe prima linie numărul $N$. Pe linia următoare se află un şir de caractere (litere mici ale alfabetului latin) de lungime $N$. Pe următoarea linie se află numărul de întrebari $Q$, iar pe următoarele $Q$ linii se află câte două numere $P$, $K$.
 

h2. Date de ieşire

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

În fişierul de ieşire "brperm.out" se află răspunsurile la cele Q întrebări ( $1$ dacă secvenţa dată este drăguţă, $0$ dacă nu este), în ordine, câte unul pe linie.
 

h2. Restricţii

* *SIGMA = 26*

* $1 ≤ N ≤ 500000$
 
* $1 ≤ Q ≤ 500000$

* $... ≤ ... ≤ ...$

* Pentru 20 puncte, $1 ≤ N ≤ 1000$ şi $1 ≤ Q ≤ 1000$

* Subtask1 (10 puncte): O(Q * N * logN) && *NU* neaparat linie
* Subtask2 (10 puncte): O(N * logN + Q * N) && *NU* neaparat linie
* Subtask3 (10 puncte): O(N * logN + Q) && linie && SIGMA = 2 && biased random (comisia a ales, pt fiecare test, cate un numar real $p$ intre $0$ si $1$ iar fiecare caracter este 'a' cu probabilitate $p$ si 'b' cu probabilitate $1-p$)
* Subtask4 (30 puncte): O((N + Q) * logN * logN) sau O((N + Q) * sqrt(N + Q) + Q) (nu cunosc solutie, dar cine stie?) - anulat si inghitit de subtaskul urmator in caz ca nu dam queryuri
* Subtask5 (10 puncte): O(N * logN * logN + Q) - acelasi lucru ca subtaskul urmator daca nu dam queryuri
* Subtask6 (10 puncte): O((N + Q) * logN) - in caz ca exista
* Subtask7 (20 puncte): O(N * logN + Q) - in caz ca exista, altfel punctele merg la ultimul subtask existent

* Pentru alte 30 puncte, $1 ≤ N ≤ 100000$ şi $1 ≤ Q ≤ 100000$
 
* Pentru alte 20 puncte, s conţine doar caracterele 'a' şi 'b', iar culorile sunt alese aleator independent cu o anumită probabilitate fixată pentru fiecare test.

h2. Exemplu
table(example). |_. brperm.in |_. brperm.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 8
  axxyxxyb
  4
  0 3
  1 1
  1 2
  3 2
| 1
  1
  0
  1

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="brperm") ==