#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long inf64 = 1e18;
inline int _sum(int a, int b, int mod) {
  return a + b < mod ? a + b : a + b - mod;
}
inline int _sub(int a, int b, int mod) { return a >= b ? a - b : a - b + mod; }
inline int _mul(int a, int b, int mod) { return (1ll * a * b) % mod; }
inline int _binpow(int x, int pw, int mod) {
  int res = 1;
  int tmp = x;
  while (pw > 0) {
    if (pw & 1) {
      res = _mul(res, tmp, mod);
    }
    tmp = _mul(tmp, tmp, mod);
    pw >>= 1;
  }
  return res;
}
inline int _rev(int x, int mod) { return _binpow(x, mod - 2, mod); }
const int ITER = 5e4 + 5;
void gen_ways(vector<int> *way, int s, int p) {
  for (int iter = 0; iter < ITER; iter++) {
    int x = s;
    for (int j = 0; j < 100; j++) {
      way[iter].push_back(x);
      int ty = rand() % 3;
      if (ty == 0) {
        x = _sum(x, 1, p);
      } else if (ty == 1) {
        x = _sub(x, 1, p);
      } else {
        x = _rev(x, p);
      }
    }
  }
}
void print(vector<int> *wa, vector<int> *wb, int i, int j, int both, int p) {
  int si = 0;
  int sj = 0;
  while (wa[i][si] != both) si++;
  while (wb[j][sj] != both) sj++;
  vector<int> way;
  for (int q = 0; q <= si; q++) way.push_back(wa[i][q]);
  for (int q = sj - 1; q >= 0; q--) way.push_back(wb[j][q]);
  printf("%d\n", (int)way.size() - 1);
  for (int q = 0; q + 1 < (int)way.size(); q++) {
    int now = way[q];
    int nxt = way[q + 1];
    if (_sum(now, 1, p) == nxt) {
      printf("1 ");
    } else if (_sub(now, 1, p) == nxt) {
      printf("2 ");
    } else {
      printf("3 ");
    }
  }
  printf("\n");
}
int main() {
  int u, v, p;
  scanf("%d %d %d", &u, &v, &p);
  if (u == v) {
    puts("0");
    return 0;
  }
  vector<int> wa[ITER], wb[ITER];
  gen_ways(wa, u, p);
  gen_ways(wb, v, p);
  unordered_map<int, int> um;
  for (int iter = 0; iter < ITER; iter++) {
    for (int j = 0; j < (int)wa[iter].size(); j++) {
      um[wa[iter][j]] = iter;
    }
  }
  for (int iter = 0; iter < ITER; iter++) {
    for (int j = 0; j < (int)wb[iter].size(); j++) {
      if (!um.count(wb[iter][j])) continue;
      print(wa, wb, um[wb[iter][j]], iter, wb[iter][j], p);
      return 0;
    }
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;
const int inf = 1e9;
const long long inf64 = 1e18;
inline int _sum(int a, int b, int mod) {
  return a + b < mod ? a + b : a + b - mod;
}
inline int _sub(int a, int b, int mod) { return a >= b ? a - b : a - b + mod; }
inline int _mul(int a, int b, int mod) { return (1ll * a * b) % mod; }
inline int _binpow(int x, int pw, int mod) {
  int res = 1;
  int tmp = x;
  while (pw > 0) {
    if (pw & 1) {
      res = _mul(res, tmp, mod);
    }
    tmp = _mul(tmp, tmp, mod);
    pw >>= 1;
  }
  return res;
}
inline int _rev(int x, int mod) { return _binpow(x, mod - 2, mod); }
const int ITER = 5e4 + 5;
void gen_ways(vector<int> *way, int s, int p) {
  for (int iter = 0; iter < ITER; iter++) {
    int x = s;
    for (int j = 0; j < 100; j++) {
      way[iter].push_back(x);
      int ty = rand() % 3;
      if (ty == 0) {
        x = _sum(x, 1, p);
      } else if (ty == 1) {
        x = _sub(x, 1, p);
      } else {
        x = _rev(x, p);
      }
    }
  }
}
void print(vector<int> *wa, vector<int> *wb, int i, int j, int both, int p) {
  int si = 0;
  int sj = 0;
  while (wa[i][si] != both) si++;
  while (wb[j][sj] != both) sj++;
  vector<int> way;
  for (int q = 0; q <= si; q++) way.push_back(wa[i][q]);
  for (int q = sj - 1; q >= 0; q--) way.push_back(wb[j][q]);
  printf("%d\n", (int)way.size() - 1);
  for (int q = 0; q + 1 < (int)way.size(); q++) {
    int now = way[q];
    int nxt = way[q + 1];
    if (_sum(now, 1, p) == nxt) {
      printf("1 ");
    } else if (_sub(now, 1, p) == nxt) {
      printf("2 ");
    } else {
      printf("3 ");
    }
  }
  printf("\n");
}
int main() {
  int u, v, p;
  scanf("%d %d %d", &u, &v, &p);
  if (u == v) {
    puts("0");
    return 0;
  }
  vector<int> wa[ITER], wb[ITER];
  gen_ways(wa, u, p);
  gen_ways(wb, v, p);
  unordered_map<int, int> um;
  for (int iter = 0; iter < ITER; iter++) {
    for (int j = 0; j < (int)wa[iter].size(); j++) {
      um[wa[iter][j]] = iter;
    }
  }
  for (int iter = 0; iter < ITER; iter++) {
    for (int j = 0; j < (int)wb[iter].size(); j++) {
      if (!um.count(wb[iter][j])) continue;
      print(wa, wb, um[wb[iter][j]], iter, wb[iter][j], p);
      return 0;
    }
  }
  return 0;
}

```