[ol2] XORovanje delilaca

Miközben Dóra a természetben sétált és rókákat figyelt, egy eldobott papírlapot talált, amelyen egy n szám, és k darab különböző d_1, d_2, \ldots, d_k szám volt felírva. Ezek a számok érdekesnek tűntek számára, ezért megpróbálta kideríteni a jelentésüket. Rájött, hogy a \{d_1, d_2, \ldots, d_k\} számhalmaz megegyezik az n szám összes osztójának halmazával. Más szóval, minden 1 \le i \le k esetén érvényes, hogy d_i osztója n-nek. Továbbá igaz minden pozitív egész x számra, amely osztója n-nek, hogy létezik egy egyedi 1 \le i \le k index, amelyre d_i = x.

A \text{xor\_delilaca} (x) függvény az x szám összes osztójának kizáró vagy művelete. Formálisan, legyenek a d_1, d_2, \ldots d_k számok az x szám összes osztói. Ekkor: \text{xor\_delilaca} (x) = d_1\ \text{xor}\ d_2\ \text{xor}\ \ldots\ \text{xor}\ d_k.

Dóra szeretné meghatározni a \text{xor\_delilaca} függvény értékét az összes d_1, d_2, \ldots, d_k értékre. Mivel a természetben van és nincs számítógép közelében, a számok pedig nagyon nagyok, titeket kért meg, hogy segítsetek neki.

A bemenet leírása

A szabványos bemenet első sora két számot tartalmaz: n-t (a feladat szövegében szereplő n számot) és k-t (az n szám osztóinak számát).

A szabványos bemenet második sorában k szám található (d_1, d_2, \ldots, d_k) – az n szám összes osztója.

A kimenet leírása

A szabványos kimenet egyetlen sorában k számot kell kiírni. Közülük az i-edik szám értéke \text{xor\_delilaca}(d_i) kell hogy legyen.

1. példa

Bemenet

1 1
1

Kimenet

1

A példa magyarázata

Az 1 szám еgyetlen osztója 1, ezért: \text{xor\_delilaca}(1) = 1.

2. példa

Bemenet

12 6
12 1 3 6 2 4  

Kimenet

14 1 2 6 3 7

A példa magyarázata

A 12 szám osztói: 1, 2, 3, 4, 6 és 12, ezért: \text{xor\_delilaca}(12) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 4\ \text{xor}\ 6\ \text{xor}\ 12 = 14.

Az 1 szám egyetlen osztója 1, ezért: \text{xor\_delilaca}(1) = 1.

A 3 szám osztói 1 és 3, ezért: \text{xor\_delilaca}(3) = 1\ \text{xor}\ 3 = 2.

A 6 szám osztói 1, 2, 3 és 6, ezért: \text{xor\_delilaca}(6) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 6 = 6.

A 2 szám osztói 1 és 2, ezért: \text{xor\_delilaca}(2) = 1\ \text{xor}\ 2 = 3.

A 4 szám osztói 1, 2 és 4, ezért: \text{xor\_delilaca}(4) = 1\ \text{xor}\ 2\ \text{xor}\ 4 = 7.

Korlátozások

1 \le n \le 10^{18}

1 \le k \le 10^5

1 \le d_i \le n, minden 1 \le i \le k-ra

A \{d_1, d_2, \ldots, d_k\} számhalmaz megegyezik az n szám összes osztójának halmazával

Az összes d_1, d_2, \ldots d_k szám különböző

A tesztpéldák öt diszjunkt csoportba vannak sorolva::

• A 10 pontot érő tesztpéldákban: érvényes, hogy n \le 1\ 000
• A 15 pontot érő tesztpéldákban: érvényes, hogy n \leq 10^5
• A 15 pontot érő tesztpéldákban: érvényes, hogy n \leq 10^7
• A 20 pontot érő tesztpéldákban: érvényes, hogy n \le 10^9
• A 40 pontot érő tesztpéldákban: nincsenek további korlátozások.

Megjegyzés

A kizáró vagy jelölésére Pascal-ban a xor-t használják, míg C++-ban a ^ szimbólummal írjuk le. Az x\ \text{xor} \ y műveletet az x,y nemnegatív számok esetén a folytatásban leírt módon definiálhatjuk. Először a számokat bináris formában kell felírni. Ha egy szám rövidebb, mint a másik, akkor azt vezető nullákkal kell kiegészíteni mindaddig, amig a bináris számjegyek száma nem lesz megegyező. Így a bináris számok két sorozatát kapjuk, amelyekre a_1, \ldots, a_k és b_1, \ldots b_k jelölést használjuk. Majd minden i \in {1, \ldots, k } pozícióra kiszámoljuk a c_i-t az alábbi szabályok mentén:

• Ha a_{i} = 0, b_{i} = 0, akkor c_{i} = 0
• Ha a_{i} = 0, b_{i} = 1 akkor c_{i} = 1
• Ha a_{i} = 1, b_{i} = 0 akkor c_{i} = 1
• Ha a_{i} = 1, b_{i} = 1 akkor c_{i} = 0

A c_1, \ldots, c_k bináris számjegyekből alkotott sorozat (amely tartalmazhat vezető nullákat is) az eredmény bináris leírása, vagyis az x \ \text{xor} \ y számé.

A kizáró vagy kommutatív és asszociatív művelet, tehát érvényes, hogy:

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