[ol2] XORovanje delilaca

Док је била у природи и посматрала лисице, Дуња је наишла на бачен лист папира на коме је записан број n, а затим k различитих бројева d_1, d_2, \ldots, d_k. Дуњи су ови бројеви изгледали интересантно, па је покушала да им пронађе значење. Схватила је да је скуп бројева \{d_1, d_2, \ldots, d_k\} исти као скуп свих делилаца броја n. Другим речима, за свако 1 \le i \le k важи да d_i дели n. Такође важи да за сваки позитиван цео број x који дели n постоји јединствен индекс 1 \le i \le k такав да d_i = x.

Функција \text{xor\_delilaca} (x) је еклузивна дисјункција свих делилаца броја x. Формално, нека су бројеви d_1, d_2, \ldots d_k сви делиоци броја x. Онда је \text{xor\_delilaca} (x) = d_1\ \text{xor}\ d_2\ \text{xor}\ \ldots\ \text{xor}\ d_k.

Дуња жели да нађе вредности функције \text{xor\_delilaca} за све вредсноти d_1, d_2, \ldots, d_k. Како је у природи и није поред рачунара, а бројеви су веома велики, замолила је Вас да јој помогнете.

Опис улаза

У првој линији два броја n и k, број n из текста задатка и број делилаца броја n.

У другој линији се налази k бројава, d_1, d_2, \ldots, d_k, сви делиоци броја n.

Опис излаза

У једном реду излаза је потребно исисати k бројева. i-ти од њих треба да има вредност \text{xor\_delilaca}(d_i).

Пример 1

Улаз 1

1 1
1

Излаз 1

1

Објашњење 1

Једини делилац броја 1 је 1. Самим тиме је \text{xor\_delilaca}(1) = 1.

Пример 2

Улаз 2

12 6
12 1 3 6 2 4  

Излаз 2

14 1 2 6 3 7

Објашњење 2

Делиоци броја 12 су 1, 2, 3, 4, 6 и 12, тако да је \text{xor\_delilaca}(12) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 4\ \text{xor}\ 6\ \text{xor}\ 12 = 14.

Једини делилац броја 1 је 1. Самим тиме је \text{xor\_delilaca}(1) = 1.

Делиоци броја 3 су 1 и 3, тако да је \text{xor\_delilaca}(3) = 1\ \text{xor}\ 3 = 2.

Делиоци броја 6 су 1, 2, 3 и 6, тако да је \text{xor\_delilaca}(6) = 1\ \text{xor}\ 2\ \text{xor}\ 3\ \text{xor}\ 6 = 6.

Делиоци броја 2 су 1 и 2, тако да је \text{xor\_delilaca}(2) = 1\ \text{xor}\ 2 = 3.

Делиоци броја 4 су 1, 2 и 4, тако да је \text{xor\_delilaca}(4) = 1\ \text{xor}\ 2\ \text{xor}\ 4 = 7.

Ограничења

1 \le n \le 10^{18}

1 \le k \le 10^5

1 \le d_i \le n, за свако 1 \le i \le k

Скуп бројева \{d_1, d_2, \ldots, d_k\} је исти као скуп свих делилаца броја n

Сви бројеви d_1, d_2, \ldots d_k су различити

Тест примери су подељени у 5 дисјунктних група:

• У тестовима вредним 10 поена: важи n \le 1\ 000
• У тестовима вредним 15 поена: важи n \leq 10^5
• У тестовима вредним 15 поена: важи n \leq 10^7
• У тестовима вредним 20 поена: важи n \le 10^9
• У тестовима вредним 40 поена: без додатних ограничења.

Напомена

Оператор ексклузивне дисјункције у Pascal-u је означен са xor, док у C++ га записујемо помоћу симбола ^. Ова операција x\ \text{xor} \ y​ се за ненегативне целе бројеве x,y​ дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са a_1, \ldots, a_k​ и b_1, \ldots b_k​. Затим се за сваку позицију i \in {1, \ldots, k }​ рачуна c_i​ помоћу следећих правила:

• За a_{i} = 0, b_{i} = 0 важи c_{i} = 0
• За a_{i} = 0, b_{i} = 1 важи c_{i} = 1
• За a_{i} = 1, b_{i} = 0 важи c_{i} = 1
• За a_{i} = 1, b_{i} = 1 важи c_{i} = 0

Низ бинарних цифара c_1, \ldots, c_k (који можда има водеће нуле) је бинарни запис резултата, односно броја x \ \text{xor} \ y.

Екслузивна дисјункција је комутативна и асоцијативна операција. Односно, важи:

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