#include <bits/stdc++.h>
using namespace std;
bool home = 1;
signed realMain();
signed main() {
  home = 0;
  if (home) {
    freopen("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0);
    cin.tie(0);
  }
  realMain();
}
int mod;
int add(int a, int b) {
  a += b;
  if (a >= mod) return a - mod;
  if (a < 0) return a + mod;
  return a;
}
int mul(int a, int b) { return a * (long long)b % mod; }
int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}
int dv(int a, int b) { return mul(a, pw(b, mod - 2)); }
int f1(int a) { return add(a, 1); }
int f2(int a) { return add(a, -1); }
int f3(int a) { return pw(a, mod - 2); }
int f(int x, int type) {
  if (type == 1) return f1(x);
  if (type == 2) return f2(x);
  if (type == 3) return f3(x);
  assert(0);
}
mt19937 rng(2);
vector<int> get_rng(int x, map<int, vector<int>> &to) {
  vector<int> steps, gen = {x};
  for (int j = 0; j <= 100; j++) {
    int type = rng() % 3 + 1;
    if (!to.count(x)) {
      to[x] = steps;
    }
    steps.push_back(type);
    x = f(x, type);
    gen.push_back(x);
  }
  return gen;
}
signed realMain() {
  vector<int> a(2);
  map<int, vector<int>> t[2];
  cin >> a[0] >> a[1] >> mod;
  int it = 0;
  while (1) {
    auto now = get_rng(a[it], t[it]);
    it ^= 1;
    for (auto &x : now) {
      if (t[it].count(x)) {
        vector<int> ret, suf;
        for (auto &tp : t[0][x]) ret.push_back(tp);
        for (auto &tp : t[1][x]) {
          if (tp == 3) {
            suf.push_back(tp);
          } else {
            suf.push_back(3 - tp);
          }
        }
        reverse(suf.begin(), suf.end());
        for (auto &tp : suf) ret.push_back(tp);
        cout << (int)ret.size() << "\n";
        for (auto &x : ret) {
          cout << x << " ";
        }
        cout << "\n";
        exit(0);
      }
    }
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
bool home = 1;
signed realMain();
signed main() {
  home = 0;
  if (home) {
    freopen("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0);
    cin.tie(0);
  }
  realMain();
}
int mod;
int add(int a, int b) {
  a += b;
  if (a >= mod) return a - mod;
  if (a < 0) return a + mod;
  return a;
}
int mul(int a, int b) { return a * (long long)b % mod; }
int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}
int dv(int a, int b) { return mul(a, pw(b, mod - 2)); }
int f1(int a) { return add(a, 1); }
int f2(int a) { return add(a, -1); }
int f3(int a) { return pw(a, mod - 2); }
int f(int x, int type) {
  if (type == 1) return f1(x);
  if (type == 2) return f2(x);
  if (type == 3) return f3(x);
  assert(0);
}
mt19937 rng(2);
vector<int> get_rng(int x, map<int, vector<int>> &to) {
  vector<int> steps, gen = {x};
  for (int j = 0; j <= 100; j++) {
    int type = rng() % 3 + 1;
    if (!to.count(x)) {
      to[x] = steps;
    }
    steps.push_back(type);
    x = f(x, type);
    gen.push_back(x);
  }
  return gen;
}
signed realMain() {
  vector<int> a(2);
  map<int, vector<int>> t[2];
  cin >> a[0] >> a[1] >> mod;
  int it = 0;
  while (1) {
    auto now = get_rng(a[it], t[it]);
    it ^= 1;
    for (auto &x : now) {
      if (t[it].count(x)) {
        vector<int> ret, suf;
        for (auto &tp : t[0][x]) ret.push_back(tp);
        for (auto &tp : t[1][x]) {
          if (tp == 3) {
            suf.push_back(tp);
          } else {
            suf.push_back(3 - tp);
          }
        }
        reverse(suf.begin(), suf.end());
        for (auto &tp : suf) ret.push_back(tp);
        cout << (int)ret.size() << "\n";
        for (auto &x : ret) {
          cout << x << " ";
        }
        cout << "\n";
        exit(0);
      }
    }
  }
  return 0;
}

```