Cerința

Cătălin este cel mai important general din armata țării sale, care are N membri (soldați și ofițeri), numerotați de la 1 la N (Cătălin are numărul 1). Un ofițer este un soldat care are în subordinea sa alți soldaţi. Conform ierarhiei militare, Cătălin și toți ceilalți ofițeri primesc inițial 3 subalterni (soldații cu numerele 2, 3 şi 4). Fiecare dintre cei trei, primește la rândul lui alți 3 subalterni, după următoarea regulă: ofițerul cu numărul x primește subalternii 3 * x – 1, 3 * x, 3 * x + 1 (dacă aceștia există în armată).

S-a descoperit că în această armată există trădători. Mai exact, toți cei numerotați cu numere prime sunt dovediți trădători, iar Cătălin știe bine asta, asa că ia măsuri radicale: decide să îi elimine pe rând pe toți acești misei, începând chiar cu subalternul său cu numărul 2. Dacă ofițerul cu numărul X este eliminat, toți subalternii săi devin subalternii comandantului său. Eliminându-l pe 2, subalternii acestuia devin subalternii comandantului lui 2, adică ai lui Cătălin. După trista eliminare a lui 2, Cătălin trece mai departe și elimină pe rând pe cei cu numerele 3, 5, 7, 11, 13 … Subalternii lui 3, 5, 7 devin subalternii lui 1, cei ai lui 11 devin ai lui 4 și tot așa.

După măcel, Cătălin trebuie să răspundă la Q întrebări ale împăratului care dorește să afle câți subalterni are un membru x al armatei sale. Dacă x a fost eliminat, Cătălin va transmite pentru acesta răspunsul -1.

Date de intrare

Fișierul de intrare armata.in conține pe prima linie două numere naturale nenule, N și Q reprezentând numărul de membri ce făceau parte inițial din armată și numărul de întrebări primite de la împărat după etapa de eliminare a trădătorilor. Pe următoarele Q linii se află câte un număr de identificare al unui membru din armată nominalizat de Împărat.

Date de ieșire

Fișierul de ieșire armata.out va conține Q numere, fiecare pe câte o linie, reprezentând răspunsul lui Cătălin la întrebările Împăratului, conform specificațiilor din enunț.

Restricții și precizări

• 1 ≤ N, Q ≤ 1.000.000
• Codurile întrebărilor nu depăşesc 6 cifre.

Exemplu:

armata.in

12 4
1
3
6
4

armata.out

5
-1
0
1

Explicație

În armată sunt 12 oameni. Împăratul solicită informații despre conducătorii: 1, 3, 6, 4

Cei care sunt eliminați au codurile: 2, 3, 5, 7, 11.

Cătălin (1) rămâne cu subalternii: 4, 6 (primit după eliminarea lui 2), 8, 9, 10 (primiți după eliminarea lui 3).
3 este eliminat, deci răspunsul este -1
6 nu rămâne cu nici un subaltern
4 rămâne cu 12, pe care îl avea de la început