{"raw_statement":[{"iden":"statement","content":"Allen is playing Number Clicker on his phone.\n\nHe starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons.\n\n1.  Turn $u \\to u+1 \\pmod{p}$.\n2.  Turn $u \\to u+p-1 \\pmod{p}$.\n3.  Turn $u \\to u^{p-2} \\pmod{p}$.\n\nAllen wants to press at most 200 buttons and end up with $v$ on the screen. Help him!"},{"iden":"input","content":"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."},{"iden":"output","content":"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$.\n\nWe can show that the answer always exists."},{"iden":"examples","content":"Input\n\n1 3 5\n\nOutput\n\n2\n1 1\n\nInput\n\n3 2 5\n\nOutput\n\n1\n3"},{"iden":"note","content":"In the first example the integer on the screen changes as $1 \\to 2 \\to 3$.\n\nIn the second example the integer on the screen changes as $3 \\to 2$."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"Allen 正在玩手机上的《数字点击器》游戏。\\n\\n他初始时屏幕上有一个整数 $u$。每一秒，他可以按下三个按钮中的一个。\\n\\nAllen 希望按下至多 200 个按钮后，屏幕上出现整数 $v$。请帮助他！\\n\\n输入的第一行包含三个正整数：$u, v, p$（$0 lt.eq u, v lt.eq p -1$，$3 lt.eq p lt.eq 10^9 + 9$）。$p$ 保证为质数。\\n\\n第一行输出一个整数 $ell$，表示按钮按下的次数。第二行输出 $c_1, dots.h, c_ell$，表示按钮的按下序列。对于 $1 lt.eq i lt.eq ell$，有 $1 lt.eq c_i lt.eq 3$。\\n\\n我们可以证明答案一定存在。\\n\\n在第一个例子中，屏幕上的整数变化为 $1 arrow.r 2 arrow.r 3$。\\n\\n在第二个例子中，屏幕上的整数变化为 $3 arrow.r 2$。 \"},{\"iden\":\"input\",\"content\":\"输入的第一行包含三个正整数：$u, v, p$（$0 lt.eq u, v lt.eq p -1$，$3 lt.eq p lt.eq 10^9 + 9$）。$p$ 保证为质数。\"},{\"iden\":\"output\",\"content\":\"第一行输出一个整数 $ell$，表示按钮按下的次数。第二行输出 $c_1, dots.h, c_ell$，表示按钮的按下序列。对于 $1 lt.eq i lt.eq ell$，有 $1 lt.eq c_i lt.eq 3$。我们可以证明答案一定存在。\"},{\"iden\":\"examples\",\"content\":\"输入\\n1 3 5\\n输出\\n2\\n1 1\\n\\n输入\\n3 2 5\\n输出\\n1\\n3\"},{\"iden\":\"note\",\"content\":\"在第一个例子中，屏幕上的整数变化为 $1 arrow.r 2 arrow.r 3$。在第二个例子中，屏幕上的整数变化为 $3 arrow.r 2$。 \"}]*","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ u, v \\in \\mathbb{Z} $ be the initial and target integers, respectively.  \nLet $ p $ be a prime modulus with $ p \\geq 3 $.  \nLet $ x_0 = u $, and for each move $ i \\in \\{1, \\dots, \\ell\\} $, the state evolves as:  \n- If $ c_i = 1 $: $ x_i = (x_{i-1} + 1) \\bmod p $  \n- If $ c_i = 2 $: $ x_i = (x_{i-1} - 1) \\bmod p $  \n- If $ c_i = 3 $: $ x_i = (x_{i-1} \\cdot x_{i-1}) \\bmod p $  \n\n**Constraints**  \n1. $ 0 \\leq u, v < p $  \n2. $ 3 \\leq p \\leq 10^9 + 9 $, $ p $ prime  \n3. $ \\ell \\leq 200 $  \n4. For all $ i \\in \\{1, \\dots, \\ell\\} $, $ c_i \\in \\{1, 2, 3\\} $  \n5. $ x_\\ell \\equiv v \\pmod{p} $  \n\n**Objective**  \nFind a sequence $ (c_1, c_2, \\dots, c_\\ell) $ of button presses such that applying the above operations starting from $ u $ yields $ v \\mod p $, with $ \\ell \\leq 200 $.","simple_statement":null,"has_page_source":false}