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

Задача F. XOR-сумма

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

2 секунды

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

512 мегабайт

Дан массив $a$ из $n$ целых положительных чисел. Для каждого целого числа $k$ от $1$ до $m$ найдите значение $(a_1 \bmod k) \oplus (a_2 \bmod k) \oplus \ldots \oplus (a_n \bmod k)$. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++,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 )