← 返回题目列表

Codeforces · 995/E

E. 数字答题器

中文机器翻译题面 查看原题

Allen 正在手机上玩 Number Clicker。

他以屏幕上的整数 $$$u$$$ 开始。每一秒,他都可以按下 3 个按钮之一。

1. 将 $$$u \ 转为 u+1 \pmod{p}$$$。
2. 将 $$$u \ 转为 u+p-1 \pmod{p}$$$。
3. 将 $$$u \ 转为 u^{p-2} \pmod{p}$$$。

Allen 想要按最多 200 个按钮,最终屏幕上会显示 $$$v$$$。帮助他!

输入

输入的第一行包含 3 个正整数:$$$u, v, p$$$ ($$$0 \le u, v \le p-1$$$, $$$3 \le p \le 10^9 + 9$$$)。 $$$p$$$ 保证是素数。

输出

在第一行,打印一个整数 $$$\ell$$$,即按钮按下的次数。在第二行,打印整数 $$$c_1, \dots, c_\ell$$$,按下按钮。对于$$$1 \le i \le \ell$$$,$$$1 \le c_i \le 3$$$。

我们可以证明答案总是存在的。

示例

输入 #1

1 3 5

输出 #1

2
1 1

输入 #2

3 2 5

输出 #2

1
3

注意

在第一个示例中,屏幕上的整数更改为 $$$1 \to 2 \to 3$$$。

在第二个示例中,屏幕上的整数更改为 $$$3 \ 到 2$$$。