#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int pw(int x, int n, int mod) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % mod;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % mod;
  }
}
int inv(int x, int mod) { return pw(x, mod - 2, mod); }
vector<int> ans;
map<int, int> prv[2];
queue<pair<int, int> > q;
int invop(int x) { return x == 3 ? 3 : 3 - x; }
pair<int, vector<int> > reconstruct(int at, map<int, int> &prv, int p) {
  vector<int> path;
  while (true) {
    int op = prv[at];
    if (op == 0) {
      reverse(path.begin(), path.end());
      return make_pair(at, path);
    }
    path.push_back(op);
    int iop = invop(op);
    int to = iop == 1 ? (at + 1) % p : iop == 2 ? (at + p - 1) % p : inv(at, p);
    at = to;
  }
}
bool solve(int s, int t, int p) {
  ans.clear();
  prv[0].clear();
  prv[1].clear();
  q = queue<pair<int, int> >();
  if (s == t) return true;
  prv[0][s] = 0, prv[1][t] = 0;
  q.push(make_pair(0, s));
  q.push(make_pair(1, t));
  while (!q.empty()) {
    int side = q.front().first, at = q.front().second;
    q.pop();
    for (int op = (1); op <= (3); ++op) {
      int to = op == 1 ? (at + 1) % p : op == 2 ? (at + p - 1) % p : inv(at, p);
      if (prv[side].count(to)) continue;
      if (prv[1 - side].count(to)) {
        pair<int, vector<int> > a = reconstruct(at, prv[side], p);
        pair<int, vector<int> > b = reconstruct(to, prv[1 - side], p);
        bool swapped = false;
        if (a.first == t) swap(a, b), swapped = true;
        assert(a.first == s && b.first == t);
        for (int i = (0); i < (((int)(a.second).size())); ++i)
          ans.push_back(a.second[i]);
        ans.push_back(!swapped ? op : invop(op));
        for (int i = ((int)(b.second).size()) - 1; i >= 0; --i)
          ans.push_back(invop(b.second[i]));
        return true;
      }
      prv[side][to] = op;
      q.push(make_pair(side, to));
    }
  }
  return false;
}
void run() {
  int s, t, p;
  scanf("%d%d%d", &s, &t, &p);
  assert(solve(s, t, p));
  int x = s;
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    int op = ans[i];
    x = op == 1 ? (x + 1) % p : op == 2 ? (x + p - 1) % p : inv(x, p);
  }
  fprintf(stderr, "have=%d want=%d\n", x, t);
  printf("%d\n", ((int)(ans).size()));
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    if (i != 0) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
}
int main() {
  run();
  return 0;
}

### Prompt

Please formulate 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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int pw(int x, int n, int mod) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % mod;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % mod;
  }
}
int inv(int x, int mod) { return pw(x, mod - 2, mod); }
vector<int> ans;
map<int, int> prv[2];
queue<pair<int, int> > q;
int invop(int x) { return x == 3 ? 3 : 3 - x; }
pair<int, vector<int> > reconstruct(int at, map<int, int> &prv, int p) {
  vector<int> path;
  while (true) {
    int op = prv[at];
    if (op == 0) {
      reverse(path.begin(), path.end());
      return make_pair(at, path);
    }
    path.push_back(op);
    int iop = invop(op);
    int to = iop == 1 ? (at + 1) % p : iop == 2 ? (at + p - 1) % p : inv(at, p);
    at = to;
  }
}
bool solve(int s, int t, int p) {
  ans.clear();
  prv[0].clear();
  prv[1].clear();
  q = queue<pair<int, int> >();
  if (s == t) return true;
  prv[0][s] = 0, prv[1][t] = 0;
  q.push(make_pair(0, s));
  q.push(make_pair(1, t));
  while (!q.empty()) {
    int side = q.front().first, at = q.front().second;
    q.pop();
    for (int op = (1); op <= (3); ++op) {
      int to = op == 1 ? (at + 1) % p : op == 2 ? (at + p - 1) % p : inv(at, p);
      if (prv[side].count(to)) continue;
      if (prv[1 - side].count(to)) {
        pair<int, vector<int> > a = reconstruct(at, prv[side], p);
        pair<int, vector<int> > b = reconstruct(to, prv[1 - side], p);
        bool swapped = false;
        if (a.first == t) swap(a, b), swapped = true;
        assert(a.first == s && b.first == t);
        for (int i = (0); i < (((int)(a.second).size())); ++i)
          ans.push_back(a.second[i]);
        ans.push_back(!swapped ? op : invop(op));
        for (int i = ((int)(b.second).size()) - 1; i >= 0; --i)
          ans.push_back(invop(b.second[i]));
        return true;
      }
      prv[side][to] = op;
      q.push(make_pair(side, to));
    }
  }
  return false;
}
void run() {
  int s, t, p;
  scanf("%d%d%d", &s, &t, &p);
  assert(solve(s, t, p));
  int x = s;
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    int op = ans[i];
    x = op == 1 ? (x + 1) % p : op == 2 ? (x + p - 1) % p : inv(x, p);
  }
  fprintf(stderr, "have=%d want=%d\n", x, t);
  printf("%d\n", ((int)(ans).size()));
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    if (i != 0) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
}
int main() {
  run();
  return 0;
}

```