Î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$. 





<br>



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$.



<br>



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. 



<br>



## Descrierea intrării



<br>





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



<br>



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



<br>



## Descrierea ieșirii



<br>



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)$.



<br>



## Exemplul 1



<br>



### Intrare 1



<br>



```

1 1

1

```



<br>



### Ieșire 1



<br>



```

1

```



### Explicație 1



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



<br>

 

## Exemplul 2



<br>



### Intrare 2



<br>



```

12 6

12 1 3 6 2 4  

```



<br>



### Ieșire 2



<br>



```

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$.



<br>



## Restricții





<br>





$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



<br>



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. 



<br>



## Notă



<br>



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)​$



<br> 

