#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a, T p) {
  return a * a % p;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T, typename P>
static constexpr T power(T a, P b, T p) {
  return b == 0    ? T(1)
         : (b % 2) ? power(a, b - 1, p) * a % p
                   : sqr(power(a, b / 2, p), p);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return power(a, m - 2, m);
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  long long u, v, p;
  cin >> u >> v >> p;
  unordered_map<long long, pair<long long, int>> forw, rev;
  queue<long long> fq, rq;
  forw[u] = make_pair(-1LL, -1LL);
  rev[v] = make_pair(-1LL, -1LL);
  fq.push(u);
  rq.push(v);
  auto apply = [&](long long x, int op) {
    if (op == 1)
      return (x + 1) % p;
    else if (op == 2)
      return (x + p - 1) % p;
    else
      return inverse(x, p);
  };
  long long mid = -1;
  while (!fq.empty() || !rq.empty()) {
    auto advance = [&](unordered_map<long long, pair<long long, int>> &forw,
                       unordered_map<long long, pair<long long, int>> &rev,
                       queue<long long> &fq) {
      if (!fq.empty()) {
        long long cur = fq.front();
        fq.pop();
        if (rev.count(cur)) {
          mid = cur;
          return true;
        }
        for (int op = 1; op <= 3; op++) {
          long long nxt = apply(cur, op);
          if (!forw.count(nxt)) {
            forw[nxt] = make_pair(cur, op);
            fq.push(nxt);
          }
        }
      }
      return false;
    };
    if (advance(forw, rev, fq)) break;
    if (advance(rev, forw, rq)) break;
  }
  long long cur = mid;
  vector<int> ops;
  while (cur != u) {
    const auto &item = forw[cur];
    ops.push_back(item.second);
    cur = item.first;
  }
  reverse(begin(ops), end(ops));
  cur = mid;
  while (cur != v) {
    const auto &item = rev[cur];
    int op = item.second;
    if (op != 3) op = 3 - op;
    ops.push_back(op);
    cur = item.first;
  }
  cout << ((long long)(ops).size()) << '\n';
  for (int op : ops) {
    cout << op << ' ';
  }
  cout << '\n';
  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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a, T p) {
  return a * a % p;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T, typename P>
static constexpr T power(T a, P b, T p) {
  return b == 0    ? T(1)
         : (b % 2) ? power(a, b - 1, p) * a % p
                   : sqr(power(a, b / 2, p), p);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return power(a, m - 2, m);
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  long long u, v, p;
  cin >> u >> v >> p;
  unordered_map<long long, pair<long long, int>> forw, rev;
  queue<long long> fq, rq;
  forw[u] = make_pair(-1LL, -1LL);
  rev[v] = make_pair(-1LL, -1LL);
  fq.push(u);
  rq.push(v);
  auto apply = [&](long long x, int op) {
    if (op == 1)
      return (x + 1) % p;
    else if (op == 2)
      return (x + p - 1) % p;
    else
      return inverse(x, p);
  };
  long long mid = -1;
  while (!fq.empty() || !rq.empty()) {
    auto advance = [&](unordered_map<long long, pair<long long, int>> &forw,
                       unordered_map<long long, pair<long long, int>> &rev,
                       queue<long long> &fq) {
      if (!fq.empty()) {
        long long cur = fq.front();
        fq.pop();
        if (rev.count(cur)) {
          mid = cur;
          return true;
        }
        for (int op = 1; op <= 3; op++) {
          long long nxt = apply(cur, op);
          if (!forw.count(nxt)) {
            forw[nxt] = make_pair(cur, op);
            fq.push(nxt);
          }
        }
      }
      return false;
    };
    if (advance(forw, rev, fq)) break;
    if (advance(rev, forw, rq)) break;
  }
  long long cur = mid;
  vector<int> ops;
  while (cur != u) {
    const auto &item = forw[cur];
    ops.push_back(item.second);
    cur = item.first;
  }
  reverse(begin(ops), end(ops));
  cur = mid;
  while (cur != v) {
    const auto &item = rev[cur];
    int op = item.second;
    if (op != 3) op = 3 - op;
    ops.push_back(op);
    cur = item.first;
  }
  cout << ((long long)(ops).size()) << '\n';
  for (int op : ops) {
    cout << op << ' ';
  }
  cout << '\n';
  return 0;
}

```