3-й этап Республиканской олимпиады по информатике 2022-2023, 2й тур

Есеп F. XOR-сумма

Ограничение по времени:

2 seconds

Ограничение по памяти:

512 megabytes

$n$ бүтін оң саннан тұратын $a$ массиві берілген. $1$-ден $m$-ге дейінгі әрбір бүтін $k$ саны үшін $(a_1 \bmod k) \oplus (a_2 \bmod k) \oplus \ldots \oplus (a_n \bmod k)$ мәнін табыңыз. Бұл жерде $\oplus$ биттік XOR немесе болдырмау НЕМЕСЕ операциясын білдіреді. Бұл операция барлық заманауи бағдарламалау тілдерінде бар, С++, Python және Java тілінде <<^>>, ал Pascal тілінде <>. Бұл жерде $\bmod$ бөлгендегі қалдықты білдіреді. Яғни, $(a \bmod b)$ — $a$ санын $b$ санына бөлгендегі қалдық.

Формат входного файла

Бірінші жолда екі бүтін сан $n$ және $m$ ($1 <= n, m <= 500\,000$) беріледі. Екінші жолда $a_1, a_2, \ldots, a_n$ ($1 <= a_i <= m$) массиві беріледі.

Формат выходного файла

Бос орын арқылы $m$ бүтін сан шығарыңыз, ол жерде $k$-ші сан $(a_1 \bmod k) \oplus (a_2 \bmod k) \oplus \ldots \oplus (a_n \bmod k)$ мәніне тең болуы қажет.

Примеры:

Вход

4 5
2 5 4 2

Ответ

0 1 3 1 4

Вход

10 12
1 2 4 8 9 10 11 12 3 5

Ответ

0 1 1 1 0 1 0 5 9 3 11 1

( Temirlan Satylkhanov )