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