Контрольная сумма
Contest: VK Cup 2019 - Квалификация (Engine)
Tags: *special

Данные пользователей ВКонтакте хранятся на десятках тысяч серверов. Для того, чтобы можно было определять ошибки при записи данных на диск, на диск регулярно записываются текущие контрольные суммы CRC32 (Wiki, IEEE 802-3). Благодаря этому, при чтении данных можно заново вычислить контрольную сумму и проверить, что данные и контрольная сумма записаны корректно.

Разумеется, проверки на совпадение контрольной суммы встроены в большинство сервисов ВКонтакте. Но как-то раз оказалось, что в одном сегменте данных нужно изменить значение четырех последовательных байт на новое — нужно заменить значения последовательности $$$a_i, a_{i+1}, a_{i+2}, a_{i+3}$$$ на $$$x_0, x_1, x_2, x_3$$$. При этом, нужно чтобы значение контрольной суммы CRC32 осталось прежним. Конечно, при изменении последовательности ее контрольная сумма изменится, поэтому кроме изменения этих четырех байт на новое значение, были выбраны четыре байта $$$a_{j}, a_{j+1}, a_{j+2}, a_{j+3}$$$, которым можно назначить любое значение. Ваша задача выбрать им новые значения так, чтобы CRC32 данной последовательности не изменился, или определить, что это невозможно. Поскольку изменение данных — операция серьезная, перед самим изменением нужно определить, как изменится последовательность для $$$q$$$ независимых тестовых случаев.

Input format:
В первой строке дано два целых числа $$$n$$$ и $$$q$$$ — количество байт в файле и количество запросов, для которых нужно решить задачу ($$$8 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$).

Во второй строке дано $$$n$$$ чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ — содержимое файла в байтах ($$$0 \le a_i \le 255$$$).

В следующих $$$q$$$ строках дано по шесть чисел $$$i, j, x_0, x_1, x_2, x_3$$$ — позиция $$$i$$$, начиная с которой нужно заменить четыре байта на $$$x_0, x_1, x_2, x_3$$$, и позиция $$$j$$$, начиная с которой можно менять четыре байта как угодно ($$$0 \le i, j \le n-4$$$; $$$0 \le x_0, x_1, x_2, x_3 \le 255$$$). Гарантируется, что отрезки $$$[i; i+3]$$$ и $$$[j; j+3]$$$ не пересекаются.

Output format:
Для каждого запроса выведите четыре целых числа $$$z_0, z_1, z_2, z_3$$$, на которые нужно заменить четыре байта с номерами $$$j, j+1, j+2, j+3$$$, чтобы crc32 не изменился. Обратите внимание, что все запросы независимы, и на самом деле последовательность не изменяется.

Если существует несколько решений, выведите любое, а если для данного запроса валидного решения нет, выведите No solution.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
CRC32 байтовой последовательности из первого примера (1 2 3 4 5 6 7 8) равен 3fca88c5, CRC32 измененной последовательности (0 0 0 0 212 34 127 159) так же равен 3fca88c5. Стандартная утилита crc32 из большинства дистрибутивов линукса должна посчитать от них данную контрольную сумму.

CRC32 последовательности из второго примера равен ecbb4b55.

Example input:
8 1
1 2 3 4 5 6 7 8
0 4 0 0 0 0

Example output:
212 34 127 159

Example input:
16 3
4 5 6 7 0 0 0 0 0 0 0 85 200 47 47 0
11 0 0 0 0 0
3 12 7 0 0 0
0 11 0 0 0 0

Example output:
0 0 0 0
200 47 47 0
0 0 0 0

Editorial:
Существует несколько полных решений данной задачи. Например, можно воспользоваться следующим наблюдением (которое было использовано в предыдущей подзадаче):
Пусть $$$b_0, b_1, \ldots, b_{8n-1}$$$ — последовательность бит, соответствующая последовательности $$$a_0, a_1, \ldots, a_{n-1}$$$. Для каждого бита $$$j$$$ существует число $$$t_j$$$, такое, что $$$\textrm{CRC32}(b_0 \oplus d_0, b_1 \oplus d_1, \ldots, b_{8n-1} \oplus d_{8n-1}) = \operatorname{CRC32}(b_0, b_1, \ldots, b_{8n-1}) \oplus d_0 t_0 \oplus d_1 t_1 \oplus \ldots \oplus d_{8n-1} t_{8n-1}$$$, где $$$d_0, d_1, \ldots, d_{8n-1}$$$ — изменения данной последовательности.
Для каждого запроса у нас есть $$$32$$$ варианта выбрать между $$$0$$$ и $$$1$$$ для соответствующих значений $$$d_j$$$, которые можно изменять в данном запросе. Зная соответствующие значения $$$t_j$$$, можно составить систему из $$$32$$$ линейных уравнений с $$$32$$$ неизвестными над полем по модулю $$$2$$$. Можно показать, что у неё есть единственное решение, из которого и получается ответ к задаче.
Значения $$$t_j$$$ можно посчитать за $$$32 \cdot 8 \cdot n$$$, используя рекурренту вида $$$t_j = \sum \limits_{k=0}^{31} P_k t_{j+1+k}$$$, где $$$P_k$$$ — $$$32$$$ бита, соответствующие записи развёрнутого полинома, используемого в алгоритме.