#0007CB

[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. Спрам того \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 з помоцу шлїдуюцих правилох: