#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
int mod;
int mul(int a, int b) { return (long long)a * b % mod; }
int my_pow(int a, int b) {
  int r = 1;
  while (b) {
    if (b % 2) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}
int my_inv(int a) { return my_pow(a, mod - 2); }
void gen(int start, unordered_set<int>& B, vector<pair<int, int>>& w) {
  B.reserve(10123123);
  w.push_back({start, -3});
  for (int i = 0; i < (int)w.size() && (int)w.size() <= 2000 * 1000; ++i) {
    int x = w[i].first;
    for (int y : {(x + 1) % mod, (x + mod - 1) % mod, my_inv(x)})
      if (!B.count(y)) {
        B.insert(y);
        w.push_back({y, x});
      }
  }
  debug() << " ["
          << "w"
             ": "
          << (w) << "] ";
}
vector<int> go(vector<pair<int, int>>& w, int A, int B) {
  vector<int> r;
  sort(w.begin(), w.end());
  while (A != B) {
    int i = lower_bound(w.begin(), w.end(), make_pair(B, -5)) - w.begin();
    int prv = w[i].second;
    if ((prv + 1) % mod == B)
      r.push_back(1);
    else if ((prv + mod - 1) % mod == B)
      r.push_back(2);
    else
      r.push_back(3);
    B = prv;
  }
  reverse(r.begin(), r.end());
  return r;
}
int main() {
  int A, B;
  scanf("%d%d%d", &A, &B, &mod);
  debug() << " ["
          << "my_inv(3)"
             ": "
          << (my_inv(3)) << "] ";
  unordered_set<int> one, two;
  vector<pair<int, int>> L, R;
  gen(A, one, L);
  gen(B, two, R);
  for (pair<int, int> p : L) {
    if (two.count(p.first)) {
      vector<int> a = go(L, A, p.first);
      vector<int> b = go(R, B, p.first);
      reverse(b.begin(), b.end());
      debug() << " ["
              << "p.first"
                 ": "
              << (p.first)
              << "] "
                 " ["
              << "a"
                 ": "
              << (a)
              << "] "
                 " ["
              << "b"
                 ": "
              << (b) << "] ";
      for (int& x : b) {
        if (x == 1)
          x = 2;
        else if (x == 2)
          x = 1;
      }
      for (int x : b) a.push_back(x);
      printf("%d\n", (int)a.size());
      for (int x : a) printf("%d ", x);
      puts("");
      return 0;
    }
  }
  assert(false);
}

### Prompt

Create a solution in cpp for 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>
#pragma GCC optimize("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
int mod;
int mul(int a, int b) { return (long long)a * b % mod; }
int my_pow(int a, int b) {
  int r = 1;
  while (b) {
    if (b % 2) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}
int my_inv(int a) { return my_pow(a, mod - 2); }
void gen(int start, unordered_set<int>& B, vector<pair<int, int>>& w) {
  B.reserve(10123123);
  w.push_back({start, -3});
  for (int i = 0; i < (int)w.size() && (int)w.size() <= 2000 * 1000; ++i) {
    int x = w[i].first;
    for (int y : {(x + 1) % mod, (x + mod - 1) % mod, my_inv(x)})
      if (!B.count(y)) {
        B.insert(y);
        w.push_back({y, x});
      }
  }
  debug() << " ["
          << "w"
             ": "
          << (w) << "] ";
}
vector<int> go(vector<pair<int, int>>& w, int A, int B) {
  vector<int> r;
  sort(w.begin(), w.end());
  while (A != B) {
    int i = lower_bound(w.begin(), w.end(), make_pair(B, -5)) - w.begin();
    int prv = w[i].second;
    if ((prv + 1) % mod == B)
      r.push_back(1);
    else if ((prv + mod - 1) % mod == B)
      r.push_back(2);
    else
      r.push_back(3);
    B = prv;
  }
  reverse(r.begin(), r.end());
  return r;
}
int main() {
  int A, B;
  scanf("%d%d%d", &A, &B, &mod);
  debug() << " ["
          << "my_inv(3)"
             ": "
          << (my_inv(3)) << "] ";
  unordered_set<int> one, two;
  vector<pair<int, int>> L, R;
  gen(A, one, L);
  gen(B, two, R);
  for (pair<int, int> p : L) {
    if (two.count(p.first)) {
      vector<int> a = go(L, A, p.first);
      vector<int> b = go(R, B, p.first);
      reverse(b.begin(), b.end());
      debug() << " ["
              << "p.first"
                 ": "
              << (p.first)
              << "] "
                 " ["
              << "a"
                 ": "
              << (a)
              << "] "
                 " ["
              << "b"
                 ": "
              << (b) << "] ";
      for (int& x : b) {
        if (x == 1)
          x = 2;
        else if (x == 2)
          x = 1;
      }
      for (int x : b) a.push_back(x);
      printf("%d\n", (int)a.size());
      for (int x : a) printf("%d ", x);
      puts("");
      return 0;
    }
  }
  assert(false);
}

```