Diferențe pentru problema/zodiac între reviziile #2 si #12

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

Poveste și cerință...

Nana este o fată foarte superstițioasă căreia îi plac petrecerile – ea își alege partenerul de dans după zodie. Ionel vrea s-o impresioneze pe Nana ghicindu-i viitorul – să-i prezică zodia partenerului dintr-o zi viitoare.
 
Ionel a observat că alegerea zodiei preferate ale Nanei depinde doar de preferința din ziua anterioară și de zodia considerată de Mama Omida, astrologa ORB TV, ca fiind cea mai norocoasă. Așadar, a stat și și-a notat această dependență într-un tabel 12 x 12, în care elementul de pe poziția $(i, j)$ indică zodia preferată a Nanei, dacă ieri a preferat zodia [$i$], iar Mama Omida consideră $j$ cea mai norocoasă zodie astăzi.
 
În plus, Ionel a spart baza de date a ORB TV și a aflat un șir format din caractere din mulțimea _{a, b, c, d, e, f, g, h, i, j, k, l}_ ce conține cu siguranță ca subsecvență zodiile pe care Mama Omida le va declara drept norocoase în viitor. Chiar mai mult, știe că aceste preziceri sunt periodice (în loc de a ghici din nou în stele, Mama Omida refolosește zodiile de la început). Astfel, dacă secvența folosită de Mama Omida este _a, e, f_, atunci ea va numi drept zodia zilei următoarele zodii, în ordine: _a, e, f, a, e, f, a, e, f, ..._
 
Acum, Ionel se întreabă: _„dacă subsecvența de la $x$ la $y$ este succesiunea zodiilor din viitor, care va fi zodia preferată a Nanei peste $z$ zile?”_ Deoarece Ionel nu are cunoștințe algoritmice, el nu știe să răspundă fără a număra băbește sau ghici răspunsul, așa că vă întreabă pe voi.

h2. Date de intrare

Fișierul de intrare $zodiac.in$ ...

Fișierul de intrare $zodiac.in$ va conține, în această ordine, următoarele date:
 
* $N$ – lungimea șirului
* $C$ – zodia preferată a Nanei la momentul inițial
* $S$ – șirul de date furate din baza de date
* 12 linii a câte 12 caractere de la _a_ la _l_, reprezentând tabelul observat de Ionel
* $Q$ – numărul de întrebări
* $Q$ linii de forma $x y z$, reprezentând întrebările lui Ionel
 

h2. Date de ieșire

În fișierul de ieșire $zodiac.out$ ...

În fișierul de ieșire $zodiac.out$ se vor afla $Q$ caractere, pe câte o linie fiecare, reprezentând răspunsurile la cele $Q$ întrebări ale lui Ionel.

h2. Restricții

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

* 2 ≤ $N$ ≤ 50 000
* 1 ≤ $Q$ ≤ 300 000
* Pentru fiecare întrebare $(x, y, z)$, 0 &le; $x$ &le; $y$ < $|S|$, 1 &le; $z$ &le; 10[^9^] și sunt numere întregi
* Caracterele lui [$S$], ale tabelului și zodia preferată inițială a Nanei aparțin mulțimii _{a, b, c, d, e, f, g, h, i, j, k, l}_ (primele 12 caractere ale alfabetului latin)
* Pentru tabel: _a_ este zodia 1, _b_ este zodia 2 etc, _c_ este zodia 3, ... _l_ este zodia 12
* Pentru întrebările puse de Ionel, șirul se consideră indexat de la 0
* Pentru 30% din teste, $N, Q$ &le; 2 000

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

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

| 6 a
abcdef
abcdefghijkl
bcdefghijkla
cdefghijklab
defghijklabc
efghijklabcd
fghijklabcde
ghijklabcdef
hijklabcdefg
ijklabcdefgh
jklabcdefgha
klabcdefghaj
labcdefghajk
3
1 3 2
2 5 3
4 5 4
| d
j
g

|

h3. Explicație
 
...
 

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