#include <bits/stdc++.h>
using namespace std;
namespace {
int MOD;
class IntMod {
  int val;

 public:
  IntMod() : val(0) {}
  IntMod(int64_t x) : val(static_cast<int>(x % MOD)) {
    if (val < 0) val += MOD;
  }
  IntMod& operator+=(const IntMod& x) {
    val += x.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  IntMod operator+(const IntMod& x) const {
    IntMod res(*this);
    return res += x;
  }
  IntMod& operator-=(const IntMod& x) {
    val -= x.val;
    if (val < 0) val += MOD;
    return *this;
  }
  IntMod operator-(const IntMod& x) const {
    IntMod res(*this);
    return res -= x;
  }
  IntMod& operator*=(const IntMod& x) {
    val = static_cast<int>(static_cast<long long>(val) * x.val % MOD);
    return *this;
  }
  IntMod operator*(const IntMod& x) const {
    IntMod res(*this);
    return res *= x;
  }
  IntMod& operator/=(const IntMod& x) { return *this *= x.Inv(); }
  IntMod operator/(const IntMod& x) const {
    IntMod res(*this);
    return res /= x;
  }
  IntMod operator-() const {
    IntMod res(*this);
    if (res.val != 0) res.val = MOD - res.val;
    return res;
  }
  IntMod Power(int expon) const {
    IntMod ans(1), temp(*this);
    for (; expon > 0; expon >>= 1) {
      if (expon & 1) ans *= temp;
      temp *= temp;
    }
    return ans;
  }
  IntMod Inv() const {
    int64_t a = MOD, b = val, nx = 1, x = 0;
    while (b != 0) {
      tie(nx, x) = make_pair(x - (a / b) * nx, nx);
      tie(a, b) = make_pair(b, a % b);
    }
    return IntMod(x);
  }
  explicit operator int() const { return val; }
  friend ostream& operator<<(ostream& out, const IntMod& x) {
    return out << x.val;
  }
  bool operator==(const IntMod& x) const { return val == x.val; }
  bool operator!=(const IntMod& x) const { return val != x.val; }
  bool operator<(const IntMod& x) const { return val < x.val; }
};
void Solve(int) {
  int u, v;
  cin >> u >> v >> MOD;
  map<IntMod, pair<IntMod, bool>> pred;
  queue<pair<IntMod, bool>> que;
  vector<IntMod> seq;
  auto enq = [&](IntMod to, IntMod fr, bool dir) {
    auto it = pred.find(to);
    if (it == pred.end()) {
      que.emplace(to, dir);
      pred[to] = {fr, dir};
      return;
    }
    if (it->second.second == dir) return;
    vector<IntMod> path;
    for (IntMod x = to;; x = pred[x].first) {
      path.push_back(x);
      if (x == u or x == v) break;
    }
    reverse(path.begin(), path.end());
    for (IntMod x = fr;; x = pred[x].first) {
      path.push_back(x);
      if (x == u or x == v) break;
    }
    if (path.front() != u) reverse(path.begin(), path.end());
    vector<int> res;
    for (int i = 1, __i = ((int)(path.size())); i < __i; ++i) {
      if (path[i - 1] + 1 == path[i])
        res.push_back(1);
      else if (path[i - 1] - 1 == path[i])
        res.push_back(2);
      else
        res.push_back(3);
    }
    cout << ((int)(res.size())) << "\n";
    for (auto& r : res) cout << r << " ";
    cout << "\n";
    throw "vera";
  };
  que.emplace(u, true);
  que.emplace(v, false);
  pred[u] = {u, true};
  pred[v] = {v, false};
  try {
    while (true) {
      IntMod at;
      bool dir;
      tie(at, dir) = que.front();
      que.pop();
      enq(at + 1, at, dir);
      enq(at - 1, at, dir);
      enq(at.Inv(), at, dir);
    }
  } catch (...) {
  }
}
void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}  // namespace
int32_t main() {
  Init();
  int tests = 1;
  for (int test = 1, __test = tests + 1; test < __test; ++test) Solve(test);
  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;
namespace {
int MOD;
class IntMod {
  int val;

 public:
  IntMod() : val(0) {}
  IntMod(int64_t x) : val(static_cast<int>(x % MOD)) {
    if (val < 0) val += MOD;
  }
  IntMod& operator+=(const IntMod& x) {
    val += x.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  IntMod operator+(const IntMod& x) const {
    IntMod res(*this);
    return res += x;
  }
  IntMod& operator-=(const IntMod& x) {
    val -= x.val;
    if (val < 0) val += MOD;
    return *this;
  }
  IntMod operator-(const IntMod& x) const {
    IntMod res(*this);
    return res -= x;
  }
  IntMod& operator*=(const IntMod& x) {
    val = static_cast<int>(static_cast<long long>(val) * x.val % MOD);
    return *this;
  }
  IntMod operator*(const IntMod& x) const {
    IntMod res(*this);
    return res *= x;
  }
  IntMod& operator/=(const IntMod& x) { return *this *= x.Inv(); }
  IntMod operator/(const IntMod& x) const {
    IntMod res(*this);
    return res /= x;
  }
  IntMod operator-() const {
    IntMod res(*this);
    if (res.val != 0) res.val = MOD - res.val;
    return res;
  }
  IntMod Power(int expon) const {
    IntMod ans(1), temp(*this);
    for (; expon > 0; expon >>= 1) {
      if (expon & 1) ans *= temp;
      temp *= temp;
    }
    return ans;
  }
  IntMod Inv() const {
    int64_t a = MOD, b = val, nx = 1, x = 0;
    while (b != 0) {
      tie(nx, x) = make_pair(x - (a / b) * nx, nx);
      tie(a, b) = make_pair(b, a % b);
    }
    return IntMod(x);
  }
  explicit operator int() const { return val; }
  friend ostream& operator<<(ostream& out, const IntMod& x) {
    return out << x.val;
  }
  bool operator==(const IntMod& x) const { return val == x.val; }
  bool operator!=(const IntMod& x) const { return val != x.val; }
  bool operator<(const IntMod& x) const { return val < x.val; }
};
void Solve(int) {
  int u, v;
  cin >> u >> v >> MOD;
  map<IntMod, pair<IntMod, bool>> pred;
  queue<pair<IntMod, bool>> que;
  vector<IntMod> seq;
  auto enq = [&](IntMod to, IntMod fr, bool dir) {
    auto it = pred.find(to);
    if (it == pred.end()) {
      que.emplace(to, dir);
      pred[to] = {fr, dir};
      return;
    }
    if (it->second.second == dir) return;
    vector<IntMod> path;
    for (IntMod x = to;; x = pred[x].first) {
      path.push_back(x);
      if (x == u or x == v) break;
    }
    reverse(path.begin(), path.end());
    for (IntMod x = fr;; x = pred[x].first) {
      path.push_back(x);
      if (x == u or x == v) break;
    }
    if (path.front() != u) reverse(path.begin(), path.end());
    vector<int> res;
    for (int i = 1, __i = ((int)(path.size())); i < __i; ++i) {
      if (path[i - 1] + 1 == path[i])
        res.push_back(1);
      else if (path[i - 1] - 1 == path[i])
        res.push_back(2);
      else
        res.push_back(3);
    }
    cout << ((int)(res.size())) << "\n";
    for (auto& r : res) cout << r << " ";
    cout << "\n";
    throw "vera";
  };
  que.emplace(u, true);
  que.emplace(v, false);
  pred[u] = {u, true};
  pred[v] = {v, false};
  try {
    while (true) {
      IntMod at;
      bool dir;
      tie(at, dir) = que.front();
      que.pop();
      enq(at + 1, at, dir);
      enq(at - 1, at, dir);
      enq(at.Inv(), at, dir);
    }
  } catch (...) {
  }
}
void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}  // namespace
int32_t main() {
  Init();
  int tests = 1;
  for (int test = 1, __test = tests + 1; test < __test; ++test) Solve(test);
  return 0;
}

```