#P995E. Number Clicker
-
ID: 5336
Type: RemoteJudge
5000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 10
Uploaded By:
Hydro
Tags> Number Clicker
Description
Allen is playing Number Clicker on his phone.
He starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons.
- Turn $u \to u+1 \pmod{p}$.
- Turn $u \to u+p-1 \pmod{p}$.
- Turn $u \to u^{p-2} \pmod{p}$.
Allen wants to press at most 200 buttons and end up with $v$ on the screen. Help him!
The first line of the input contains 3 positive integers: $u, v, p$ ($0 \le u, v \le p-1$, $3 \le p \le 10^9 + 9$). $p$ is guaranteed to be prime.
On the first line, print a single integer $\ell$, the number of button presses. On the second line, print integers $c_1, \dots, c_\ell$, the button presses. For $1 \le i \le \ell$, $1 \le c_i \le 3$.
We can show that the answer always exists.
Input
The first line of the input contains 3 positive integers: $u, v, p$ ($0 \le u, v \le p-1$, $3 \le p \le 10^9 + 9$). $p$ is guaranteed to be prime.
Output
On the first line, print a single integer $\ell$, the number of button presses. On the second line, print integers $c_1, \dots, c_\ell$, the button presses. For $1 \le i \le \ell$, $1 \le c_i \le 3$.
We can show that the answer always exists.
1 3 5
3 2 5
2
1 1
1
3
Note
In the first example the integer on the screen changes as $1 \to 2 \to 3$.
In the second example the integer on the screen changes as $3 \to 2$.