Данные пользователей ВКонтакте хранятся на десятках тысяч серверов. Для того, чтобы можно было определять ошибки при записи данных на диск, на диск регулярно записываются текущие контрольные суммы 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=16, q=8\), который вы можете скачать по этой ссылке. Ваше решение не обязано проходить тесты из условия, и не будет на них протестировано. Если вы хотите проверить ваше решение на тестах из условия, отправляйте его в задачу E3, где первые два теста соответствуют примерам из условия.
Выходные данные
Для каждого запроса выведите четыре целых числа \(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
|
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
|
0 0 0 0
200 47 47 0
0 0 0 0
|