#include <bits/stdc++.h>
using namespace std;
const int max_n = 101, log_n = 32, max_m = 111, mod = 1000000007,
          inf = 1011111111;
int u, v, p;
unordered_map<int, vector<char> > s1, s2;
int power(int a, int b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  int x = power(a, b / 2);
  if (b % 2 == 0) return 1LL * x * x % p;
  return (1LL * x * x % p) * a % p;
}
void op(int &u, int o) {
  if (o == 0) {
    u += 1;
    if (u >= p) u -= p;
  }
  if (o == 1) {
    u -= 1;
    if (u < 0) u += p;
  }
  if (o == 2) {
    u = power(u, p - 2);
  }
}
int get_paths(int u, unordered_map<int, vector<char> > &s, bool fin = 0) {
  vector<char> v;
  for (int i = 0; 1LL * i * i <= p || i <= 10000; ++i) {
    v.clear();
    int c = u;
    for (int q = 0; q < 100; ++q) {
      v.push_back(rand() % 3);
      op(c, v.back());
      s[c] = v;
      if (fin && s1.count(c)) {
        return c;
      }
    }
  }
  return -1;
}
char rev(int op) {
  if (op < 2) return 1 - op;
  return op;
}
bool check(vector<char> &v1, vector<char> &v2) {
  int c = u;
  for (int i = 0; i < v1.size(); ++i) {
    op(c, v1[i]);
  }
  for (int i = int(v2.size()) - 1; i >= 0; --i) {
    op(c, rev(v2[i]));
  }
  return c == v;
}
int main() {
  srand(time(0));
  cin >> u >> v >> p;
  get_paths(u, s1);
  int c = get_paths(v, s2, 1);
  assert(c != -1);
  if (!check(s1[c], s2[c])) {
    cout << "Fail" << endl;
    return 0;
  }
  cout << s1[c].size() + s2[c].size() << endl;
  for (int i = 0; i < s1[c].size(); ++i) {
    cout << s1[c][i] + 1 << " ";
  }
  for (int i = int(s2[c].size()) - 1; i >= 0; --i) {
    cout << rev(s2[c][i]) + 1 << " ";
  }
  return 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;
const int max_n = 101, log_n = 32, max_m = 111, mod = 1000000007,
          inf = 1011111111;
int u, v, p;
unordered_map<int, vector<char> > s1, s2;
int power(int a, int b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  int x = power(a, b / 2);
  if (b % 2 == 0) return 1LL * x * x % p;
  return (1LL * x * x % p) * a % p;
}
void op(int &u, int o) {
  if (o == 0) {
    u += 1;
    if (u >= p) u -= p;
  }
  if (o == 1) {
    u -= 1;
    if (u < 0) u += p;
  }
  if (o == 2) {
    u = power(u, p - 2);
  }
}
int get_paths(int u, unordered_map<int, vector<char> > &s, bool fin = 0) {
  vector<char> v;
  for (int i = 0; 1LL * i * i <= p || i <= 10000; ++i) {
    v.clear();
    int c = u;
    for (int q = 0; q < 100; ++q) {
      v.push_back(rand() % 3);
      op(c, v.back());
      s[c] = v;
      if (fin && s1.count(c)) {
        return c;
      }
    }
  }
  return -1;
}
char rev(int op) {
  if (op < 2) return 1 - op;
  return op;
}
bool check(vector<char> &v1, vector<char> &v2) {
  int c = u;
  for (int i = 0; i < v1.size(); ++i) {
    op(c, v1[i]);
  }
  for (int i = int(v2.size()) - 1; i >= 0; --i) {
    op(c, rev(v2[i]));
  }
  return c == v;
}
int main() {
  srand(time(0));
  cin >> u >> v >> p;
  get_paths(u, s1);
  int c = get_paths(v, s2, 1);
  assert(c != -1);
  if (!check(s1[c], s2[c])) {
    cout << "Fail" << endl;
    return 0;
  }
  cout << s1[c].size() + s2[c].size() << endl;
  for (int i = 0; i < s1[c].size(); ++i) {
    cout << s1[c][i] + 1 << " ";
  }
  for (int i = int(s2[c].size()) - 1; i >= 0; --i) {
    cout << rev(s2[c][i]) + 1 << " ";
  }
  return 0;
}

```