Fişierul intrare/ieşire:	zodiac.in, zodiac.out	Sursă	Baraj Yakutia 2014
Autor	Andreescu Mihai	Adăugată de	Andreescu Mihai •mihai995
Timp execuţie pe test	1.6 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Zodiac

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 × 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.

Date de intrare

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

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 lui Ionel.

Restricţii

• 2 ≤ N ≤ 50 000
• 1 ≤ Q ≤ 300 000
• Pentru fiecare întrebare (x, y, z), 0 ≤ x ≤ y < |S|, 1 ≤ z ≤ 10⁹ ş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 ≤ 2 000

Exemplu