În premieră în acest an, pentru a putea ridica marele trofeu “Urmașul lui Moisil” vor fi necesare o serie de ștampile ce se obțin de la Primărie.
La Primăria din Iași sunt N
camere numerotate de la 1
la N
. În fiecare cameră există câte o ștampilă pe care apare o literă mică a alfabetului englez a-z
. Pot exista camere cu același caracter pe ștampilă.
În instituţie sunt două categorii de camere, în funcţie de modul în care acordă ștampilele:
- camere simple – se aplică ștampila camerei imediat, fără a fi necesare ştampilele din alte camere.
- camere complicate – Mecanismul birocratic intră în acţiune! Funcţionarul unei astfel de camere
i
aplică ştampila pe cerere apoi solicită obţinerea în ordine a ştampilelor camerelorc[i1], c[i2] ... c[iLg]
, toate aceste camere având numere mai mari strict decâti
. După fiecare ștampilă obținută în camerele specificate, aplică și el, încă o dată, ştampila camerei sale. Spunem că această cameră complicată este dependentă de fiecare dintre camerele din lista asociată, care pot fi la rândul lor simple sau complicate.
De exemplu, dacă 5
este o cameră complicată cu ştampila z
și este dependentă de camera simplă 7
(cu caracterul u
) atunci, la ieșirea din camera 5
, pe cerere va apărea secvența zuz
. Dacă 1
este de asemenea o cameră complicată în care se ștampilează cu litera t
și este dependentă de camera simplă 2
(cu caracterul x
) și de camera complicată 5
atunci, la finalizarea validării cererii în camera 1
, va apărea pe cerere secvența txtzuzt
. Obținerea ștampilelor poate implica un efort considerabil, dar respectarea acestei reguli birocratice este recompensată prin premiul care este deosebit de valoros.
Cerința
Pentru ca festivitatea de premiere să nu înceapă prea târziu , câștigătorul trofeului trebuie să raspundă repede la M
întrebări de tipul (q,k)
: care este litera de pe poziția k
a șirului de ștampile obținut de la camera q
?
Date de intrare
Pe prima linie a fișierului birocratie.in
se găsesc două numere naturale N
și M
cu semnificația: numărul de camere și numărul de întrebări la care trebuie răspuns.
Pe următoarele N
linii se găsesc descrierile camerelor, câte o linie pentru fiecare cameră, de forma: si Li c[i1] c[i2] ... c[iLi]
unde si
reprezintă caracterul ștampilei din camera i
, Li
reprezintă numărul camerelor de care depinde obţinerea acesteia iar c[i1] c[i2] ... c[iLi]
este lista asociată camerei i şi conţine camerele, în ordine a de vizitare impusă. Pentru camere simple Li
este 0
.
Următoarele M
linii conțin câte două numere q
și k
, separate printr-un spațiu, reprezentând întrebările: care este al k
-lea caracter din șirul de ștampile al camerei q
? (pozițiile se numerotează de la 1
).
Date de ieșire
Fișierul birocratie.out
va conţine M
linii, pe fiecare linie i
fiind scrisă o singură literă ce reprezintă răspunsul la întrebarea i
, i∈[1,M]
.
Restricții și precizări
N≤1000, M≤1000
Li≤5000
pentru orice camerăk≤1.000.000.000
și1≤q≤N
pentru orice întrebare- Pentru orice
i∈[1,N] cij>i
: camerele de care depinde camerai
au indici cu valori mai mari
strict decâti
- Pentru orice întrebare
(q,k)
,k
este mai mic sau egal decât lungimea șirului de ștampile al camereiq
- Pentru orice cameră, numărul maxim de ștampile necesare este
≤ 1.000.000.000
- Orice succesiune de camere
c[1] c[2] ... c[Lg]
în carec[i-1]
este dependentă dec[i]
,i∈[2,Lg]
, areLg≤20
- pentru teste în valoare de
15
puncteLi≤1
pentru orice cameră - pentru teste în valoare de
35
punctek≤1000
pentru orice întrebare
Exemplu:
birocratie.in
2 4 b 1 2 a 0 1 1 1 2 1 3 2 1
birocratie.out
b a b a
Explicație
Sunt 2
camere și 4
întrebări:
Camera 1
este dependentă de camera 2
. Ștampila validă este bab
.
Camera 2
este simplă și are ștampila validă a
.
Pozițiile în șirurile asociate sunt numerotate de la 1.
În acest exemplu se întreabă despre toate pozițiile din toate camerele, pe rând.
birocratie.in
5 3 e 2 3 2 d 2 4 5 c 0 p 0 q 0 1 3 1 4 2 1
birocratie.out
e d d
Explicație
Sunt 5
camere și 3
întrebări. Camera 1
depinde de camerele 3
și 2
: e(3)e(2)e
adică ecedpdqde
.
Camera 2
depinde de camerele 4
și 5
: d(4)d(5)d
, adică dpdqd
.
Camera 3
: simplă cu ștampila c
Camera 4
: simplă cu ștampila p
Camera 5
: simplă cu ștampila q
Se întreabă despre ștampilele 3
și 4
din camera 1
(e
, respectiv d
) și ștampila 1
din camera 2
(ștampila d
).
birocratie.in
4 13 x 4 3 2 3 4 q 2 4 4 z 0 p 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13
birocratie.out
x z x q p q p q x z x p x
Explicație
Camera 1
depinde de camerele : 3 2 3 4
(pot exista repetiții) Șirul asociat este x(3)x(2)x(3)x(4)x
, adică xzxqpqpqxzxpx
.
Camera 2
depinde de camerele 4
și iar 4
, ştampila validă a camerei 2 fiind qpqpq
.
Camerele 3
și 4
sunt simple, cu ştampilele z
și respectiv p
.
Se întreabă, pe rând, despre fiecare caracter din șirul de ștampile al camerei cu numărul 1
.