#include <bits/stdc++.h>
using namespace std;
double const EPS = 1.0E-9;
int const MOD = (int)1e9 + 7;
inline int read(char* s) { return scanf("%s", s); }
inline int read(int& x) { return scanf("%d", &(x)); }
inline int read(long long& x) { return scanf("%lld", &x); }
inline int read(double& x) { return scanf("%lf", &x); }
inline int writeln(int x) { return printf("%d\n", x); }
inline int writeln(long long x) { return printf("%lld\n", x); }
inline int writeln(double x) { return printf("%.12f\n", x); }
template <typename... T>
int read(T&... args) {
  using swallow = int[];
  swallow w = {0, (read(args))...};
  return sizeof(w) / sizeof(w[0]) - 1;
}
template <typename T>
int read(std::vector<T>& v) {
  for (T& t : v) read(t);
  return (int)v.size();
}
inline long long gcd(long long x, long long y) {
  return y == 0 ? x : gcd(y, x % y);
}
inline long long lcm(long long x, long long y) {
  return x == 0 && y == 0 ? 0 : x / gcd(x, y) * y;
}
inline long long powmod(long long x, long long n, long long m = MOD) {
  long long r = 1;
  while (n) {
    if (n & 1) r = (r * x) % m;
    x = (x * x) % m;
    n /= 2;
  }
  return r;
}
static int leap(int y) { return y % 4 == 0 && y % 100 != 0 || y % 400 == 0; }
static int const month[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
static const int maxn = 1 << 19;
static const int maxm = 1 << 20;
int U, V, P;
std::vector<int> ans;
int do_op(int x, int o, int p) {
  switch (o) {
    case 0:
      return (x + 1) % p;
    case 1:
      return (x + p - 1) % p;
    case 2:
      return powmod(x, p - 2, p);
  }
  return 0;
}
struct node {
  int o;
  int len;
  int src;
};
static int solve() {
  read(U, V, P);
  set<std::pair<int, int> > q;
  map<int, node> mp;
  mp[U] = node{0, 0, 0};
  q.insert(std::pair<int, int>(0, U));
  while (!q.empty() && mp.size() < (int)3e5) {
    std::pair<int, int> xp = *q.begin();
    q.erase(q.begin());
    int x = xp.second;
    node p = mp[x];
    if (p.len >= 100) continue;
    for (int o = 0; o < 3; ++o) {
      int y = do_op(x, o, P);
      if (!mp.count(y)) {
        mp[y] = node{o, p.len + 1, x};
        q.insert(std::pair<int, int>(p.len + 1, y));
      }
    }
  }
  q.clear();
  map<int, node> mv;
  q.insert(std::pair<int, int>(0, V));
  mv[V] = node{0, 0, 0};
  int fx = -1;
  while (!q.empty()) {
    std::pair<int, int> xp = *q.begin();
    q.erase(q.begin());
    int x = xp.second;
    node p = mv[x];
    if (p.len >= 100) continue;
    if (mp.count(x)) {
      fx = x;
      break;
    }
    if (mv.size() > (int)3e5) continue;
    for (int o = 0; o < 3; ++o) {
      int y = do_op(x, o, P);
      if (!mv.count(y)) {
        mv[y] = node{o, p.len + 1, x};
        q.insert(std::pair<int, int>(p.len + 1, y));
      }
    }
  }
  assert(fx != -1);
  int rev[3] = {1, 0, 2};
  for (int i = fx; i != U;) {
    node p = mp[i];
    int o = p.o;
    ans.push_back(o + 1);
    i = p.src;
  }
  reverse((ans).begin(), (ans).end());
  for (int i = fx; i != V;) {
    node p = mv[i];
    int o = p.o;
    ans.push_back(rev[o] + 1);
    i = p.src;
  }
  writeln((int)ans.size());
  for (int e : ans) printf("%d ", e);
  return 0;
}
int main(int argc, char* argv[]) {
  solve();
  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;
double const EPS = 1.0E-9;
int const MOD = (int)1e9 + 7;
inline int read(char* s) { return scanf("%s", s); }
inline int read(int& x) { return scanf("%d", &(x)); }
inline int read(long long& x) { return scanf("%lld", &x); }
inline int read(double& x) { return scanf("%lf", &x); }
inline int writeln(int x) { return printf("%d\n", x); }
inline int writeln(long long x) { return printf("%lld\n", x); }
inline int writeln(double x) { return printf("%.12f\n", x); }
template <typename... T>
int read(T&... args) {
  using swallow = int[];
  swallow w = {0, (read(args))...};
  return sizeof(w) / sizeof(w[0]) - 1;
}
template <typename T>
int read(std::vector<T>& v) {
  for (T& t : v) read(t);
  return (int)v.size();
}
inline long long gcd(long long x, long long y) {
  return y == 0 ? x : gcd(y, x % y);
}
inline long long lcm(long long x, long long y) {
  return x == 0 && y == 0 ? 0 : x / gcd(x, y) * y;
}
inline long long powmod(long long x, long long n, long long m = MOD) {
  long long r = 1;
  while (n) {
    if (n & 1) r = (r * x) % m;
    x = (x * x) % m;
    n /= 2;
  }
  return r;
}
static int leap(int y) { return y % 4 == 0 && y % 100 != 0 || y % 400 == 0; }
static int const month[2][12] = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
static const int maxn = 1 << 19;
static const int maxm = 1 << 20;
int U, V, P;
std::vector<int> ans;
int do_op(int x, int o, int p) {
  switch (o) {
    case 0:
      return (x + 1) % p;
    case 1:
      return (x + p - 1) % p;
    case 2:
      return powmod(x, p - 2, p);
  }
  return 0;
}
struct node {
  int o;
  int len;
  int src;
};
static int solve() {
  read(U, V, P);
  set<std::pair<int, int> > q;
  map<int, node> mp;
  mp[U] = node{0, 0, 0};
  q.insert(std::pair<int, int>(0, U));
  while (!q.empty() && mp.size() < (int)3e5) {
    std::pair<int, int> xp = *q.begin();
    q.erase(q.begin());
    int x = xp.second;
    node p = mp[x];
    if (p.len >= 100) continue;
    for (int o = 0; o < 3; ++o) {
      int y = do_op(x, o, P);
      if (!mp.count(y)) {
        mp[y] = node{o, p.len + 1, x};
        q.insert(std::pair<int, int>(p.len + 1, y));
      }
    }
  }
  q.clear();
  map<int, node> mv;
  q.insert(std::pair<int, int>(0, V));
  mv[V] = node{0, 0, 0};
  int fx = -1;
  while (!q.empty()) {
    std::pair<int, int> xp = *q.begin();
    q.erase(q.begin());
    int x = xp.second;
    node p = mv[x];
    if (p.len >= 100) continue;
    if (mp.count(x)) {
      fx = x;
      break;
    }
    if (mv.size() > (int)3e5) continue;
    for (int o = 0; o < 3; ++o) {
      int y = do_op(x, o, P);
      if (!mv.count(y)) {
        mv[y] = node{o, p.len + 1, x};
        q.insert(std::pair<int, int>(p.len + 1, y));
      }
    }
  }
  assert(fx != -1);
  int rev[3] = {1, 0, 2};
  for (int i = fx; i != U;) {
    node p = mp[i];
    int o = p.o;
    ans.push_back(o + 1);
    i = p.src;
  }
  reverse((ans).begin(), (ans).end());
  for (int i = fx; i != V;) {
    node p = mv[i];
    int o = p.o;
    ans.push_back(rev[o] + 1);
    i = p.src;
  }
  writeln((int)ans.size());
  for (int e : ans) printf("%d ", e);
  return 0;
}
int main(int argc, char* argv[]) {
  solve();
  return 0;
}

```