Baieţii de la 8 joacă Boltz. Acest joc are următoarele reguli:
se porneşte de la o mulţime P vidă
dacă numărul curent este divizibil cu oricare dintre numerele din P, spunem că numărul este BOLTZ
În orice moment al jocului, se poate adăuga un număr în P, cu condiţia ca acest număr să fie putere de număr prim.
Astfel, se definesc doua tipuri de operaţii:
1 x se adaugă x în P
2 x se întreabă dacă x este BOLTZ sau nu
Cerinţă
Se dau M operaţii. Să se raspundă la cele de tip 2.
Date de intrare
Fişierul de intrare boltz.in conţine pe prima linie numerele naturale N şi M. Pe următoarele M linii se vor afla câte două numere, separate prin spaţiu, de forma op x cu semnificaţia de mai sus (se garantează că toate numerele x sunt naturale cuprinse între 1 şi N, inclusiv).
Date de ieşire
Fişierul de ieşire boltz.out va conţine pe fiecare linie răspunsul la câte o întrebare de tip 2, în ordinea corespunzătoare fişierului de intrare. Răspunsul este BOLTZ dacă numărul din întrebare e "boltz" respectiv valoarea numărului, în caz contrar.
Restricţii
N, M <= 350 000
Pentru 30% din teste N, M <= 5000
La operaţiile de tip 1 se garantează că numărul x este putere de număr prim
Răspunsul pentru orice operaţie tip 2 va lua în calcul operaţiile de tip 1 care au apărut înaintea sa