Аллен играет в Number Clicker на телефоне.
Он начинает с целого числа \(u\) на экране. Каждую секунду он нажимает одну из трех кнопок:
- Изменить \(u \to u+1 \pmod{p}\).
- Изменить \(u \to u+p-1 \pmod{p}\).
- Изменить \(u \to u^{p-2} \pmod{p}\).
Аллен хочет нажать на кнопки не более 200 раз так, чтобы получить на экране число \(v\). Помогите ему!
Выходные данные
В первой строке выведите одно целое число \(\ell\) — количество нажатий кнопок. Во второй строке выведите целые числа \(c_1, \dots, c_\ell\) — кнопки, которые должен нажать Аллен. Для всех \(1 \le i \le \ell\) должно выполняться \(1 \le c_i \le 3\).
Можно показать, что ответ всегда существует.
Примечание
В первом примере число на экране меняется следующим образом: \(1 \to 2 \to 3\).
Во втором примере число на экране меняется следующим образом: \(3 \to 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 3 5
|
2
1 1
|
|
2
|
3 2 5
|
1
3
|