Fişierul intrare/ieşire:	bolt.in, bolt.out	Sursă	Lot Deva Seniori 2019, baraj 2
Autor	Lucian Bicsi	Adăugată de	Alex Luchianov •AlexandruLuchianov1
Timp execuţie pe test	0.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bolt

Suntem la Lotul National de Informatica de la Deva si, cum comisia este prea ocupata pregatind problemele, cei N concurenti se plictisesc. Ei au inceput sa joace jocul Bolt, care se desfasoara dupa urmatoarele reguli:

• Toti cei N participanti se asaza in cerc in ordine trigonometrica. Participantul 2 se asaza la dreapta participantului 1, participantul 3 la dreapta participantului 2 si asa mai departe. Participantul 1 va fi la dreapta participantului N.
• Se alege o cifra speciala C.
• Participantul cu numarul 1 incepe numaratoarea (zice 1) si ceilalti continua in sens trigonometric(spre dreapta). Numaratoara se continua cu participantul cu numarul 2, si asa mai departe.
• Atunci cand un participantu, ajunge la un numar care este multiplu al lui C sau contine cifra C in scrierea sa in baza 10, acesta trebuia sa spune cuvantul "fulger" in loc de acel numar.
• De fiecare data cand cuvantul "fulger" este spus, se inverseaza ordinea jocului (daca se mergea in ses trigonometric, se va continua in sens orar si invers).

Primele 18 mutari ale unui joc cu N = 5 participanti si c = 7 este descris mai jos cuvantul fulger este marcat prin litera F):

De fiecare data cand cineva greseste, respectivul trebuie sa bea un pahar de lapte cald si jocul se continua(pentru ca dupa cum bine stiti, laptele afecteaza viteza de reactie si face jocul mai amuzant).
Cum cei N participanti nu sunt suficient de incurcati de laptele cald, ei se decis sa faca jocul si mai interesant, alegand o multime S de cifre speciale distincte, in loc de o singura cifra, si aplicand regulile de mai sus simulta pentru toate cifrele din S. De exemplu daca S = {3, 7}, atunci participantul la rand trebuie sa spuna cuvantul fulger daca numarul curent este multiplu de 3 sau de 7 sau cand contine cifrele 3 sau 7 in reprezentarea sa.

De asemenea, pentru a fi si mai buni la acest joc, majoritatea participantilor calculeaza in avans ce numere urmeaza sa zica si la care dintr acestea trebuie sa spuna "fulger". Comisia, care acum sta si priveste, vrea sa stie ce concurent va spune un numar dat K (sau "fulger"-ul corespunzator numarului dupa caz) si rasplateste cu puncte pe oricine va putea raspunde.

Date de intrare

Fişierul de intrare bolt.in va contine pe prima linie numerele N si K, si valorile din S alaturate

Date de ieşire

În fişierul de ieşire bolt.out va contine pe prima linie numarul jucatorului care va spune numarul dat K (sau "fulger"-ul corespunzator numarului dupa caz).

Restricţii

• Pentru teste in valoare de 11 puncte: 3 ≤ N ≤ 100.000, 1 ≤ K ≤ 10^5 si 1 ≤ |S| ≤ 9
• Pentru alte teste in valoare de 50 puncte: 3 ≤ N ≤ 100.000, 1 ≤ K ≤ 10^12 si 1 ≤ |S| = 9.
• Pentru alte teste in valoare de 20 puncte: 3 ≤ N ≤ 100.000, 1 ≤ K ≤ 10^2000 si 1 ≤ |S| = 1.
• Pentru alte teste in valoare de 19 puncte: 3 ≤ N ≤ 100.000, 1 ≤ K ≤ 10^2000 si 1 ≤ |S| ≤ 9.

Exemplu

Explicaţie

Exemplele 1 si 2 sunt descrise in enunt. In exemplul e, jocul va alterna intre concurentii 1 si 9 deoarece fiecare va spune fulger (jocul se dovedeste a fi destul de monoton pentru ceilalti 7 concurenti).

In celelalte cazuri, va trebui sa ne credeti pe cuvant.

Cum se trimit solutii?