Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Number Clicker

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAllen 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!

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.

Examples

Input

1 3 5

Output

2

1 1

Input

3 2 5

Output

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$$$.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/28/2022 02:15:30 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|