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

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

Nana este o fată foarte superstițioasă căreia îi plac petrecerile – ea își alege partenerul de dans după zodie. Elful vrea s-o impresioneze pe Nana ghicindu-i viitorul – să-i prezică zodia partenerului dintr-o zi viitoare.

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.

Elful a observat că alegerea zodiei preferate ale Nanei depinde doar de preferința din ziua anterioară și de zodia considerată de Mama Omida, astroloaga 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.

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, Elful 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). Adică dacă secvența folosită de Mama Omida este a, e, f, atunci ea va numi drept zodia zilei urmatoarele zodii, în ordine: a, e, f, a, e, f, a, e, f, ...

Î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, Elful 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 Elful 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.

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$ va conține, în această ordine, următoarele date:

* N – lungimea șirului
* S – șirul de date furate din baza de date
* C – zodia preferată a lui A la momentul inițial
* Q – numărul de întrebări
* Q linii de forma x, y, z, reprezentând întrebările Elfului

* $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$ se vor afla Q caractere, pe câte o linie fiecare, reprezentând răspunsurile la cele Q întrebări ale Elfului

Î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), 1 <= x < y <= |S|, 1 <= z <= 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
 

* 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 |
| 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

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

j
g

|

h3. Explicație
 
...
 

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