#include <bits/stdc++.h>
const int MX = 1e5 + 23;
long long MOD = 53;
int read() {
  char k = getchar();
  int x = 0;
  while (k < '0' || k > '9') k = getchar();
  while (k >= '0' && k <= '9') x = x * 10 + k - '0', k = getchar();
  return x;
}
long long qpow(long long a, long long b, long long p = MOD) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % p;
    a = a * a % p, b >>= 1;
  }
  return ans;
}
int dist(int x, int y) {
  return std::min((y - x + MOD) % MOD, (x - y + MOD) % MOD);
}
int s, t;
std::unordered_map<int, int> fr, dis, who;
int C[2][MX], CNT[2];
void getpath(int x, int aim, int *c, int &cnt) {
  if (x == aim) {
    c[++cnt] = x;
    return;
  }
  getpath(fr[x], aim, c, cnt);
  c[++cnt] = x;
}
int type(int x, int y) {
  if (y == (x + 1) % MOD) return 1;
  if (y == (x - 1 + MOD) % MOD) return 2;
  return 3;
}
void bfs() {
  std::queue<int> q[2];
  q[0].push(s);
  q[1].push(t);
  dis[s] = 0, fr[s] = s, who[s] = 1;
  dis[t] = 0, fr[t] = t, who[t] = 2;
  int o = 0;
  while (!q[0].empty() && !q[1].empty()) {
    o ^= 1;
    if (!q[o].empty()) {
      int x = q[o].front();
      q[o].pop();
      for (auto i : {((x) == 0 ? (int)MOD - 1 : (x)-1),
                     ((x) == MOD - 1 ? 0 : (x) + 1), (int)qpow(x, MOD - 2)}) {
        int st = who[i];
        if (st == 0) {
          fr[i] = x;
          dis[i] = dis[x] + 1;
          who[i] = o + 1;
          q[o].push(i);
        } else if (st != o + 1) {
          getpath(x, o ? t : s, C[o], CNT[o]);
          getpath(i, o ? s : t, C[o ^ 1], CNT[o ^ 1]);
          goto out;
        }
      }
    }
  }
out:
  printf("%d\n", CNT[0] + CNT[1] - 1);
  for (int i = 2; i <= CNT[0]; ++i) {
    printf("%d ", type(C[0][i - 1], C[0][i]));
  }
  printf("%d ", type(C[0][CNT[0]], C[1][CNT[1]]));
  for (int i = CNT[1] - 1; i; --i) {
    printf("%d ", type(C[1][i + 1], C[1][i]));
  }
}
int main() {
  s = read(), t = read(), MOD = read();
  if (s == t) {
    puts("0");
    return 0;
  }
  bfs();
  return 0;
}

### Prompt

Your task is to create 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>
const int MX = 1e5 + 23;
long long MOD = 53;
int read() {
  char k = getchar();
  int x = 0;
  while (k < '0' || k > '9') k = getchar();
  while (k >= '0' && k <= '9') x = x * 10 + k - '0', k = getchar();
  return x;
}
long long qpow(long long a, long long b, long long p = MOD) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % p;
    a = a * a % p, b >>= 1;
  }
  return ans;
}
int dist(int x, int y) {
  return std::min((y - x + MOD) % MOD, (x - y + MOD) % MOD);
}
int s, t;
std::unordered_map<int, int> fr, dis, who;
int C[2][MX], CNT[2];
void getpath(int x, int aim, int *c, int &cnt) {
  if (x == aim) {
    c[++cnt] = x;
    return;
  }
  getpath(fr[x], aim, c, cnt);
  c[++cnt] = x;
}
int type(int x, int y) {
  if (y == (x + 1) % MOD) return 1;
  if (y == (x - 1 + MOD) % MOD) return 2;
  return 3;
}
void bfs() {
  std::queue<int> q[2];
  q[0].push(s);
  q[1].push(t);
  dis[s] = 0, fr[s] = s, who[s] = 1;
  dis[t] = 0, fr[t] = t, who[t] = 2;
  int o = 0;
  while (!q[0].empty() && !q[1].empty()) {
    o ^= 1;
    if (!q[o].empty()) {
      int x = q[o].front();
      q[o].pop();
      for (auto i : {((x) == 0 ? (int)MOD - 1 : (x)-1),
                     ((x) == MOD - 1 ? 0 : (x) + 1), (int)qpow(x, MOD - 2)}) {
        int st = who[i];
        if (st == 0) {
          fr[i] = x;
          dis[i] = dis[x] + 1;
          who[i] = o + 1;
          q[o].push(i);
        } else if (st != o + 1) {
          getpath(x, o ? t : s, C[o], CNT[o]);
          getpath(i, o ? s : t, C[o ^ 1], CNT[o ^ 1]);
          goto out;
        }
      }
    }
  }
out:
  printf("%d\n", CNT[0] + CNT[1] - 1);
  for (int i = 2; i <= CNT[0]; ++i) {
    printf("%d ", type(C[0][i - 1], C[0][i]));
  }
  printf("%d ", type(C[0][CNT[0]], C[1][CNT[1]]));
  for (int i = CNT[1] - 1; i; --i) {
    printf("%d ", type(C[1][i + 1], C[1][i]));
  }
}
int main() {
  s = read(), t = read(), MOD = read();
  if (s == t) {
    puts("0");
    return 0;
  }
  bfs();
  return 0;
}

```