Контрольная сумма
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$$$ независимых тестовых случаев.

Обратите внимание, что в этой версии задачи есть всего один тест с $$$n=50\,000, q=8$$$, который вы можете скачать по этой ссылке. Ваше решение не обязано проходить тесты из условия, и не будет на них протестировано. Если вы хотите проверить ваше решение на тестах из условия, отправляйте его в задачу E3, где первые два теста соответствуют примерам из условия.

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:
Во второй версии задачи подразумевалось, что нужно сделать что-нибудь чуть более содержательное. Решение с явным перебором ответа и подсчётом чек-суммы, скорее всего, не уложится в разумное время выполнения ($$$8 \cdot 50\,000 \cdot 2^{32}$$$ — больше, чем $$$10^{15}$$$ операций, хотя с оптимизациями и можно успеть посчитать это за несколько часов/дней).
Есть несколько способов соптимизировать это решение, избавившись от зависимости либо от $$$n$$$, либо от $$$2^{32}$$$. Например, можно заметить, что при изменении одного любого бита в любую сторону (с 0 на 1 и с 1 на 0) к значению crc32 применяется ксор с числом, не зависящим от остальных бит. Так, можно для каждого бита исходной последовательности посчитать, как изменится чек-сумма при изменении данного бита. После этого можно снова решать задачу за $$$2^{32}$$$ на каждый запрос.