Контрольная сумма

题目描述

Данные пользователей ВКонтакте хранятся на десятках тысяч серверов. Для того, чтобы можно было определять ошибки при записи данных на диск, на диск регулярно записываются текущие контрольные суммы CRC32 ([Wiki](https://en.wikipedia.org/wiki/Cyclic_redundancy_check), 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 $ , который вы можете скачать по [этой ссылке](https://drive.google.com/open?id=117PBFxdKNhMsauCBiI8FAeSW2T9uP0rr). Ваше решение не обязано проходить тесты из условия, и не будет на них протестировано. Если вы хотите проверить ваше решение на тестах из условия, отправляйте его в задачу E3, где первые два теста соответствуют примерам из условия.

输入输出格式

输入格式

В первой строке дано два целых числа $ 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] $ не пересекаются.

输出格式

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

输入输出样例

输入样例 #1

8 1
1 2 3 4 5 6 7 8
0 4 0 0 0 0

输出样例 #1

212 34 127 159

输入样例 #2

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

输出样例 #2

0 0 0 0
200 47 47 0
0 0 0 0

暂时还没有翻译