| Codeforces Round 453 (Div. 1) |
|---|
| Закончено |
Сеньор Стрижай Пинозаддо разработал инновационный метод шифрования последовательностей чисел длины n. Чтобы применить его, нужно выбрать секретную последовательность 
, которая будет выступать шифратором.
Стрижай проводит строгий отбор шифраторов, поэтому шифратором может стать только такая последовательность bi, что её циклические сдвиги линейно независимы, то есть, не существует ненулевого набора коэффициентов x0, x1, ..., xn - 1 такого, что 
для всех k одновременно.
После этого для последовательности чисел 
, вы сопоставляете следующий шифр:
Иначе говоря, считаете квадратичное отклонение каждого циклического сдвига последовательности bi от последовательности ai, это и есть шифр сеньора Пинозаддо. Шифр ещё только в разработке и Стрижаю нужен способ дешифровать последовательность после того, как он был применён к ней. Эта задача ложится на ваши плечи. Вам известны последовательности ci и bi. Вам необходимо найти все возможные последовательности ai.
Первая строка содержит единственное целое число n (
).
Вторая строка содержит n целых чисел — последовательность b0, b1, ..., bn - 1 (
).
Третья строка содержит n целых чисел — последовательность c0, c1, ..., cn - 1 (
).
Гарантируется, что циклические сдвиги bi линейно независимы.
Выведите число k — количество целочисленных последовательностей ai таких, что при применении шифратора bi вы получите последовательность ci.
Далее в каждой из k последующих строк выведите n целых чисел a0, a1, ..., an - 1. Последовательности нужно выводить в лексикографическом порядке.
Обратите внимание, что k может быть равно 0.
1
1
0
1
1
1
100
81
2
91
109
3
1 1 3
165 185 197
2
-6 -9 -1
8 5 13
