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

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile 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