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

Exemplu

boltz.in	boltz.out
10 4 2 9 1 3 2 9 2 4	9 BOLTZ 4

stud Ion Petcu

Facultatea de Matematica si Informatică Bucuresti

infooltenia2013@gmail.com