Данные пользователей ВКонтакте хранятся на десятках тысяч серверов. Для того, чтобы можно было определять ошибки при записи данных на диск, на диск регулярно записываются текущие контрольные суммы 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$$$ и $$$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.

Примечание

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

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

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

Examples