[old] XORovanje delilaca

Dok je bila u prirodi i promatrala lisice, Dunja je naišla na bačen list papira na kome je zapisan broj n, a zatim k različitih brojeva d_1, d_2, \ldots, d_k. Dunji su ovi brojevi izgledali interesantno, pa je pokušala pronaći im značenje. Shvatila je kako je skup brojeva \{d_1, d_2, \ldots, d_k\} isti kao skup svih djelitelja broja n. Drugim riječima, za svako 1 \le i \le k važi kako d_i dijeli n. Također važi kako za svaki pozitivan cijeli broj x koji dijeli n postoji jedinstven indeks 1 \le i \le k takav da d_i = x.

Funkcija \text{xor\_djelitelja} (x) ekskluzivna je disjunkcija svih djelitelja broja x. Formalno, neka su brojevi d_1, d_2, \ldots d_k svi djelitelji broja x. Onda je \text{xor\_djelitelja} (x) = d_1\ \text{xor}\ d_2\ \text{xor}\ \ldots\ \text{xor}\ d_k.

Dunja želi naći vrijednosti funkcije \text{xor\_djelitelja} za sve vrijednosti d_1, d_2, \ldots, d_k. Kako je u prirodi i nije pored računala, a brojevi su iznimno veliki, zamolila Vas je da joj pomognete.

Opis ulaza

U prvoj liniji dva broja n i k, broj n iz teksta zadatka i broj djelitelja broja n.

U drugoj liniji se nalazi k brojeva, d_1, d_2, \ldots, d_k, svi djelitelji broja n.

Opis izlaza

U jednom redu izlaza je potrebno ispisati k brojeva. i-ti od njih treba imati vrijednost \text{xor\_djelitelja}(d_i).

Primjer 1

Ulaz 1

1 1
1

Izlaz 1

1

Objašnjenje 1

Jedini djelitelj broja 1 je 1. Samim time je \text{xor\_djelitelja}(1) = 1.

Primjer 2

Ulaz 2

12 6
12 1 3 6 2 4  

Izlaz 2

14 1 2 6 3 7

Objašnjenje 2

Djelitelji broja 12 su 1, 2, 3, 4, 6 и 12, tako da je \text{xor\_djelitelja}(12) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 4\ \text{xor}\ 6\ \text{xor}\ 12 = 14.

Jedini djelitelj broja 1 je 1. Samim time je \text{xor\_djelitelja}(1) = 1.

Djelitelji broja 3 su 1 i 3, tako da je \text{xor\_djelitelja}(3) = 1\ \text{xor}\ 3 = 2.

Djelitelji broja 6 su 1, 2, 3 i 6, tako da je \text{xor\_djelitelja}(6) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 6 = 6.

Djelitelji broja 2 su 1 i 2, tako da je \text{xor\_djelitelja}(2) = 1\ \text{xor}\ 2 = 3.

Djelitelji broja 4 su 1, 2 i 4, tako da je \text{xor\_djelitelja}(4) = 1\ \text{xor}\ 2\ \text{xor}\ 4 = 7.

Ograničenja

1 \le n \le 10^{18}

1 \le k \le 10^5

1 \le d_i \le n, za svako 1 \le i \le k

Skup brojeva \{d_1, d_2, \ldots, d_k\} je isti kao skup svih djelitelja broja n

Svi brojevi d_1, d_2, \ldots d_k su različiti

Test primjeri su podijeljeni u 5 disjunktnih skupina:

• U testovima vrijednim 10 bodova: važi n \le 1\ 000
• U testovima vrijednim 15 bodova: važi n \leq 10^5
• U testovima vrijednim 15 bodova: važi n \leq 10^7
• U testovima vrijednim 20 bodova: važi n \le 10^9
• U testovima vrijednim 40 bodova: bez dodatnih ograničenja.

Napomena

Operator ekskluzivne disjunkcije u Pascalu označen je s xor, dok u C++ ga zapisujemo s pomoću simbola ^. Ova operacija x\ \text{xor} \ y​ se za nenegativne cijele brojeve x,y​ definira na sljedeći način. Prvo se brojevi zapišu u binarnome zapisu. Ako jedan broj ima manje znamenki od drugoga, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih znamenki. Tako se dobivaju dvije niske binarnih znamenki, označimo ih s a_1, \ldots, a_k​ i b_1, \ldots b_k​. Zatim se za svaku poziciju i \in {1, \ldots, k }​ računa c_i​ s pomoću sljedećih pravila:

• Za a_{i} = 0, b_{i} = 0 važi c_{i} = 0
• Za a_{i} = 0, b_{i} = 1 važi c_{i} = 1
• Za a_{i} = 1, b_{i} = 0 važi c_{i} = 1
• Za a_{i} = 1, b_{i} = 1 važi c_{i} = 0

Niska binarnih znamenki c_1, \ldots, c_k (koja možda ima vodeće nule) je binarni zapis rezultata, odnosno broja x \ \text{xor} \ y.

Ekskluzivna disjunkcija je komutativna i asocijativna operacija. Odnosno, važi:

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