#include <bits/stdc++.h>
using namespace std;
struct p {
  int x, step;
};
int u, v, mod;
map<int, p> ma1, ma2;
queue<p> qu1, qu2;
int Pow(long long a, long long b) {
  long long ans = 1;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) ans = ans * a % mod;
  return ans;
}
int s1(int x) { return (x + 1) % mod; }
int s2(int x) { return (x - 1 + mod) % mod; }
int s3(int x) { return Pow(x, mod - 2); }
int bfs() {
  while (!qu1.empty() || !qu2.empty()) {
    p tt = qu1.front();
    qu1.pop();
    int S1 = s1(tt.x), S2 = s2(tt.x), S3 = s3(tt.x);
    if (!ma1[S1].x)
      ma1[S1] = (p){1, tt.step + 1}, qu1.push((p){S1, tt.step + 1});
    if (!ma1[S2].x)
      ma1[S2] = (p){2, tt.step + 1}, qu1.push((p){S2, tt.step + 1});
    if (!ma1[S3].x)
      ma1[S3] = (p){3, tt.step + 1}, qu1.push((p){S3, tt.step + 1});
    if (ma2[S1].x) return printf("%d\n", ma2[S1].step + tt.step + 1), S1;
    if (ma2[S2].x) return printf("%d\n", ma2[S2].step + tt.step + 1), S2;
    if (ma2[S3].x) return printf("%d\n", ma2[S3].step + tt.step + 1), S3;
    tt = qu2.front();
    qu2.pop();
    S1 = s2(tt.x), S2 = s1(tt.x), S3 = s3(tt.x);
    if (!ma2[S1].x)
      ma2[S1] = (p){1, tt.step + 1}, qu2.push((p){S1, tt.step + 1});
    if (!ma2[S2].x)
      ma2[S2] = (p){2, tt.step + 1}, qu2.push((p){S2, tt.step + 1});
    if (!ma2[S3].x)
      ma2[S3] = (p){3, tt.step + 1}, qu2.push((p){S3, tt.step + 1});
    if (ma1[S1].x) return printf("%d\n", ma1[S1].step + tt.step + 1), S1;
    if (ma1[S2].x) return printf("%d\n", ma1[S2].step + tt.step + 1), S2;
    if (ma1[S3].x) return printf("%d\n", ma1[S3].step + tt.step + 1), S3;
  }
}
void coutt1(int x) {
  int tt = ma1[x].x;
  if (tt == 4) return;
  if (tt == 1) coutt1(s2(x));
  if (tt == 2) coutt1(s1(x));
  if (tt == 3) coutt1(s3(x));
  printf("%d ", tt);
}
void coutt2(int x) {
  int tt = ma2[x].x;
  if (tt == 4) return;
  printf("%d ", tt);
  if (tt == 1) coutt2(s1(x));
  if (tt == 2) coutt2(s2(x));
  if (tt == 3) coutt2(s3(x));
}
void Print(int x) { coutt1(x), coutt2(x); }
int main() {
  scanf("%d%d%d", &u, &v, &mod);
  if (u == v) return printf("0"), 0;
  if (u < v && v - u <= 200) {
    printf("%d\n", v - u);
    for (int i = 1; i <= v - u; ++i, printf("1 "))
      ;
    return 0;
  }
  if (u > v && u - v <= 200) {
    printf("%d\n", u - v);
    for (int i = 1; i <= u - v; ++i, printf("2 "))
      ;
    return 0;
  }
  ma1[u].x = 4, ma2[v].x = 4, qu1.push((p){u, 0}), qu2.push((p){v, 0});
  return Print(bfs()), 0;
}

### Prompt

Generate a CPP solution to the following problem:

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.

  1. Turn u → u+1 \pmod{p}. 
  2. Turn u → u+p-1 \pmod{p}. 
  3. Turn u → 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 ≤ u, v ≤ p-1, 3 ≤ p ≤ 10^9 + 9). p is guaranteed to be prime.

Output

On the first line, print a single integer ℓ, the number of button presses. On the second line, print integers c_1, ..., c_ℓ, the button presses. For 1 ≤ i ≤ ℓ, 1 ≤ c_i ≤ 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 → 2 → 3.

In the second example the integer on the screen changes as 3 → 2. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct p {
  int x, step;
};
int u, v, mod;
map<int, p> ma1, ma2;
queue<p> qu1, qu2;
int Pow(long long a, long long b) {
  long long ans = 1;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) ans = ans * a % mod;
  return ans;
}
int s1(int x) { return (x + 1) % mod; }
int s2(int x) { return (x - 1 + mod) % mod; }
int s3(int x) { return Pow(x, mod - 2); }
int bfs() {
  while (!qu1.empty() || !qu2.empty()) {
    p tt = qu1.front();
    qu1.pop();
    int S1 = s1(tt.x), S2 = s2(tt.x), S3 = s3(tt.x);
    if (!ma1[S1].x)
      ma1[S1] = (p){1, tt.step + 1}, qu1.push((p){S1, tt.step + 1});
    if (!ma1[S2].x)
      ma1[S2] = (p){2, tt.step + 1}, qu1.push((p){S2, tt.step + 1});
    if (!ma1[S3].x)
      ma1[S3] = (p){3, tt.step + 1}, qu1.push((p){S3, tt.step + 1});
    if (ma2[S1].x) return printf("%d\n", ma2[S1].step + tt.step + 1), S1;
    if (ma2[S2].x) return printf("%d\n", ma2[S2].step + tt.step + 1), S2;
    if (ma2[S3].x) return printf("%d\n", ma2[S3].step + tt.step + 1), S3;
    tt = qu2.front();
    qu2.pop();
    S1 = s2(tt.x), S2 = s1(tt.x), S3 = s3(tt.x);
    if (!ma2[S1].x)
      ma2[S1] = (p){1, tt.step + 1}, qu2.push((p){S1, tt.step + 1});
    if (!ma2[S2].x)
      ma2[S2] = (p){2, tt.step + 1}, qu2.push((p){S2, tt.step + 1});
    if (!ma2[S3].x)
      ma2[S3] = (p){3, tt.step + 1}, qu2.push((p){S3, tt.step + 1});
    if (ma1[S1].x) return printf("%d\n", ma1[S1].step + tt.step + 1), S1;
    if (ma1[S2].x) return printf("%d\n", ma1[S2].step + tt.step + 1), S2;
    if (ma1[S3].x) return printf("%d\n", ma1[S3].step + tt.step + 1), S3;
  }
}
void coutt1(int x) {
  int tt = ma1[x].x;
  if (tt == 4) return;
  if (tt == 1) coutt1(s2(x));
  if (tt == 2) coutt1(s1(x));
  if (tt == 3) coutt1(s3(x));
  printf("%d ", tt);
}
void coutt2(int x) {
  int tt = ma2[x].x;
  if (tt == 4) return;
  printf("%d ", tt);
  if (tt == 1) coutt2(s1(x));
  if (tt == 2) coutt2(s2(x));
  if (tt == 3) coutt2(s3(x));
}
void Print(int x) { coutt1(x), coutt2(x); }
int main() {
  scanf("%d%d%d", &u, &v, &mod);
  if (u == v) return printf("0"), 0;
  if (u < v && v - u <= 200) {
    printf("%d\n", v - u);
    for (int i = 1; i <= v - u; ++i, printf("1 "))
      ;
    return 0;
  }
  if (u > v && u - v <= 200) {
    printf("%d\n", u - v);
    for (int i = 1; i <= u - v; ++i, printf("2 "))
      ;
    return 0;
  }
  ma1[u].x = 4, ma2[v].x = 4, qu1.push((p){u, 0}), qu2.push((p){v, 0});
  return Print(bfs()), 0;
}

```