#include <bits/stdc++.h>
using namespace std;
long long pw(long long a, long long b, long long p) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % p)
    if (b & 1) res = res * a % p;
  return res;
}
queue<long long> q[2];
map<long long, pair<long long, int> > pre[2];
map<long long, int> vis[2];
void add(long long t, long long a, int d, int tg) {
  if (!vis[d][a]) {
    q[d].push(a);
    vis[d][a] = 1;
    pre[d][a] = make_pair(t, tg);
  }
}
void doit(const long long& u, const long long& v, const long long& t) {
  vector<int> ans;
  for (long long x = t; x != u; x = pre[0][x].first)
    ans.push_back(pre[0][x].second);
  reverse(ans.begin(), ans.end());
  for (long long x = t; x != v; x = pre[1][x].first)
    ans.push_back(pre[1][x].second);
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
  exit(0);
}
void bfs(const long long& u, const long long& v, const long long& p) {
  q[0].push(u);
  q[1].push(v);
  vis[0][u] = 1;
  vis[1][v] = 1;
  pre[0][u] = make_pair(u, 0);
  pre[1][v] = make_pair(v, 0);
  while (!q[0].empty() || !q[1].empty()) {
    int n = q[0].size();
    while (n--) {
      long long t = q[0].front();
      q[0].pop();
      if (vis[1].find(t) != vis[1].end()) doit(u, v, t);
      add(t, (t + 1) % p, 0, 1);
      add(t, (t - 1 + p) % p, 0, 2);
      add(t, pw(t, p - 2, p), 0, 3);
    }
    int m = q[1].size();
    while (m--) {
      long long t = q[1].front();
      q[1].pop();
      if (vis[0].find(t) != vis[0].end()) doit(u, v, t);
      add(t, (t + 1) % p, 1, 2);
      add(t, (t - 1 + p) % p, 1, 1);
      add(t, pw(t, p - 2, p), 1, 3);
    }
  }
}
int main() {
  long long u, v, p;
  scanf("%lld%lld%lld", &u, &v, &p);
  bfs(u, v, p);
  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;
long long pw(long long a, long long b, long long p) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % p)
    if (b & 1) res = res * a % p;
  return res;
}
queue<long long> q[2];
map<long long, pair<long long, int> > pre[2];
map<long long, int> vis[2];
void add(long long t, long long a, int d, int tg) {
  if (!vis[d][a]) {
    q[d].push(a);
    vis[d][a] = 1;
    pre[d][a] = make_pair(t, tg);
  }
}
void doit(const long long& u, const long long& v, const long long& t) {
  vector<int> ans;
  for (long long x = t; x != u; x = pre[0][x].first)
    ans.push_back(pre[0][x].second);
  reverse(ans.begin(), ans.end());
  for (long long x = t; x != v; x = pre[1][x].first)
    ans.push_back(pre[1][x].second);
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
  exit(0);
}
void bfs(const long long& u, const long long& v, const long long& p) {
  q[0].push(u);
  q[1].push(v);
  vis[0][u] = 1;
  vis[1][v] = 1;
  pre[0][u] = make_pair(u, 0);
  pre[1][v] = make_pair(v, 0);
  while (!q[0].empty() || !q[1].empty()) {
    int n = q[0].size();
    while (n--) {
      long long t = q[0].front();
      q[0].pop();
      if (vis[1].find(t) != vis[1].end()) doit(u, v, t);
      add(t, (t + 1) % p, 0, 1);
      add(t, (t - 1 + p) % p, 0, 2);
      add(t, pw(t, p - 2, p), 0, 3);
    }
    int m = q[1].size();
    while (m--) {
      long long t = q[1].front();
      q[1].pop();
      if (vis[0].find(t) != vis[0].end()) doit(u, v, t);
      add(t, (t + 1) % p, 1, 2);
      add(t, (t - 1 + p) % p, 1, 1);
      add(t, pw(t, p - 2, p), 1, 3);
    }
  }
}
int main() {
  long long u, v, p;
  scanf("%lld%lld%lld", &u, &v, &p);
  bfs(u, v, p);
  return 0;
}

```