[old] XORovanje delilaca

În timp ce se afla în natură și observa vulpile, Dana a dat peste o foaie de hârtie pe care era scris un număr n, urmat de k numere distincte d_1, d_2, \ldots, d_k. Aceste numere i s-au părut interesante Danei, așa că a încercat să le găsească semnificația. Ea a realizat că mulțimea numerelor \{d_1, d_2, \ldots, d_k\} este aceeași cu mulțimea tuturor divizorilor lui n. Cu alte cuvinte, pentru fiecare 1 \le i \le k este valabil că d_i divide n. De asemenea, pentru fiecare număr întreg pozitiv x care divide n există un singur indice 1 \le i \le k, astfel încât d_i = x.

Funcția \text{xor\_delilaca} (x) este disjuncția exclusivă a tuturor divizorilor numărului x. Formal, să fie numerele d_1, d_2, \ldots d_k toți divizorii lui x. Atunci \text{xor\_delilaca} (x) = d_1\ \text{xor}\ d_2\ \text{xor}\ \ldots\ \text{xor}\ d_k.

Dana vrea să găsească valorile funcției \text{xor\_delilaca} pentru toate valorile d_1, d_2, \ldots, d_k. Deoarece se află în natură și nu lângă un calculator, iar numerele sunt foarte mari, ea te-a rugat pe tine să o ajuți.

Descrierea intrării

În prima linie sunt două numere n și k, numărul n din enunțul problemei și numărul de divizori ai lui n.

În a doua linie se află k ale numerelor, d_1, d_2, \ldots, d_k, toți divizorii numărului n.

Descrierea ieșirii

Pe o singură linie a ieșirii trebuie să se afișeze k ale numerelor. Cel de-al i dintre ele trebuie să aibă valoarea \text{xor\_delilaca}(d_i).

Exemplul 1

Intrare 1

1 1

1

Ieșire 1

1

Explicație 1

Singurul divizor al numărului 1 este 1. Prin urmare \text{xor\_delilaca}(1) = 1.

Exemplul 2

Intrare 2

12 6

12 1 3 6 2 4  

Ieșire 2

14 1 2 6 3 7

Explicație 2

Divizorii numărului 12 sunt 1, 2, 3, 4, 6 și 12, astfel încât \text{xor\_delilaca}(12) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 4\ \text{xor}\ 6\ \text{xor}\ 12 = 14.

Singurul divizor al numărului 1 este 1. Prin urmare \text{xor\_delilaca}(1) = 1.

Divizorii numărului 3 sunt 1 și 3, astfel încât \text{xor\_delilaca}(3) = 1\ \text{xor}\ 3 = 2.

Divizorii numărului 6 sunt 1, 2, 3 şi 6, astfel încât \text{xor\_delilaca}(6) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 6 = 6.

Divizorii numărului 2 sunt 1 şi 2, astfel încât \text{xor\_delilaca}(2) = 1\ \text{xor}\ 2 = 3.

Divizorii numărului 4 sunt 1, 2 şi 4, astfel încât \text{xor\_delilaca}(4) = 1\ \text{xor}\ 2\ \text{xor}\ 4 = 7.

Restricții

1 \le n \le 10^{18}

1 \le k \le 10^5

1 \le d_i \le n, pentru fiecare 1 \le i \le k

Mulțimea numerelor \{d_1, d_2, \ldots, d_k\} este aceeași cu mulțimea tuturor divizorilor numărului n

Toate numerele d_1, d_2, \ldots d_k sunt distincte

Exemplele de test sunt împărțite în 5 grupuri disjuncte:

• În testele care valorează 10 puncte: este valabil n \le 1\ 000

• În testele care valorează 15 puncte: este valabil n \leq 10^5

• În testele care valorează 15 puncte: este valabil n \leq 10^7

• În testele care valorează 20 puncte: este valabil n \le 10^9

• În testele care valorează 40 puncte: fără restricții suplimentare.

Notă

Operatorul de disjuncție exclusivă în Pascal este notat cu xor, în timp ce C++ se scrie folosind simbolul^. Această operație x\ \text{xor} \ y​ pentru numere întregi nenegative x,y​ se definește astfel. Mai întâi, numerele se scriu în reprezentare binară. Dacă un număr are mai puține cifre decât celălalt, i se adaugă zerouri la început până când ambele au același număr de cifre binare. Astfel se obțin două șiruri de cifre binare, pe care le notăm cu a_1, \ldots, a_k​ şi b_1, \ldots b_k​. Apoi, pentru fiecare poziție i \in {1, \ldots, k }​ se calculează c_i​ folosind următoarele reguli:

• Pentru a_{i} = 0, b_{i} = 0 este valabil c_{i} = 0

• Pentru a_{i} = 0, b_{i} = 1 este valabil c_{i} = 1

• Pentru a_{i} = 1, b_{i} = 0 este valabil c_{i} = 1

• Pentru a_{i} = 1, b_{i} = 1 este valabil c_{i} = 0

Șirul de cifre binare c_1, \ldots, c_k (care poate avea zerouri la început) reprezintă scrierea binară a rezultatului, respective numărul x \ \text{xor} \ y.

Disjuncția exclusivă este o operație comutativă și asociativă. Cu alte cuvinte, se aplică:

• a\ \text{xor} \ b\ =\ b\ \text{xor} \ a​

• (a\ \text{xor} \ b)\ \text{xor} \ c\ =\ a\ \text{xor} \ (b\ \text{xor}\ c)​