#include <bits/stdc++.h>
using namespace std;
bool f = false;
int front1, front2;
long long P;
vector<int> ans;
vector<long long> q1, q2;
map<long long, int> pre1, pre2;
void getans(long long mid) {
  int p = pre1[mid];
  long long cur = mid;
  while (p != -1) {
    long long pre = q1[p];
    if ((pre + 1) % P == cur)
      ans.push_back(1);
    else if ((pre + P - 1) % P == cur)
      ans.push_back(2);
    else
      ans.push_back(3);
    cur = pre;
    p = pre1[cur];
  }
  reverse(ans.begin(), ans.end());
  p = pre2[mid], cur = mid;
  while (p != -1) {
    long long pre = q2[p];
    if ((cur + 1) % P == pre)
      ans.push_back(1);
    else if ((cur + P - 1) % P == pre)
      ans.push_back(2);
    else
      ans.push_back(3);
    cur = pre;
    p = pre2[cur];
  }
}
long long quickpow(long long a, long long b) {
  long long ret = 1;
  for (; b; b >>= 1, a = a * a % P)
    if (b & 1) ret = a * ret % P;
  return ret;
}
void BFS1() {
  long long cur = q1[front1], a, b, c;
  a = (cur + 1) % P, b = (cur + P - 1) % P, c = quickpow(cur, P - 2);
  if (pre1.find(a) == pre1.end()) {
    q1.push_back(a);
    pre1[a] = front1;
  }
  if (pre1.find(b) == pre1.end()) {
    q1.push_back(b);
    pre1[b] = front1;
  }
  if (pre1.find(c) == pre1.end()) {
    q1.push_back(c);
    pre1[c] = front1;
  }
  if (pre2.find(a) != pre2.end()) {
    f = true;
    getans(a);
    return;
  }
  if (pre2.find(b) != pre2.end()) {
    f = true;
    getans(b);
    return;
  }
  if (pre2.find(c) != pre2.end()) {
    f = true;
    getans(c);
    return;
  }
  front1++;
}
void BFS2() {
  long long cur = q2[front2], a, b, c;
  a = (cur + P - 1) % P, b = (cur + 1) % P, c = quickpow(cur, P - 2);
  if (pre2.find(a) == pre2.end()) {
    q2.push_back(a);
    pre2[a] = front2;
  }
  if (pre2.find(b) == pre2.end()) {
    q2.push_back(b);
    pre2[b] = front2;
  }
  if (pre2.find(c) == pre2.end()) {
    q2.push_back(c);
    pre2[c] = front2;
  }
  if (pre1.find(a) != pre1.end()) {
    f = true;
    getans(a);
    return;
  }
  if (pre1.find(b) != pre1.end()) {
    f = true;
    getans(b);
    return;
  }
  if (pre1.find(c) != pre1.end()) {
    f = true;
    getans(c);
    return;
  }
  front2++;
}
void BFS() {
  while (!f) {
    while (!f && q1.size() > q2.size()) {
      BFS2();
    }
    while (!f && q1.size() <= q2.size()) {
      BFS1();
    }
  }
}
int main() {
  long long u, v;
  scanf("%lld%lld%lld", &u, &v, &P);
  if (u != v) {
    pre1[u] = -1, pre2[v] = -1;
    q1.push_back(u), q2.push_back(v);
    BFS();
    int size = ans.size();
    printf("%d\n", size);
    for (int i = 0; i < size; i++) {
      printf("%d%c", ans[i], i == size - 1 ? '\n' : ' ');
    }
  } else
    printf("0\n");
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
bool f = false;
int front1, front2;
long long P;
vector<int> ans;
vector<long long> q1, q2;
map<long long, int> pre1, pre2;
void getans(long long mid) {
  int p = pre1[mid];
  long long cur = mid;
  while (p != -1) {
    long long pre = q1[p];
    if ((pre + 1) % P == cur)
      ans.push_back(1);
    else if ((pre + P - 1) % P == cur)
      ans.push_back(2);
    else
      ans.push_back(3);
    cur = pre;
    p = pre1[cur];
  }
  reverse(ans.begin(), ans.end());
  p = pre2[mid], cur = mid;
  while (p != -1) {
    long long pre = q2[p];
    if ((cur + 1) % P == pre)
      ans.push_back(1);
    else if ((cur + P - 1) % P == pre)
      ans.push_back(2);
    else
      ans.push_back(3);
    cur = pre;
    p = pre2[cur];
  }
}
long long quickpow(long long a, long long b) {
  long long ret = 1;
  for (; b; b >>= 1, a = a * a % P)
    if (b & 1) ret = a * ret % P;
  return ret;
}
void BFS1() {
  long long cur = q1[front1], a, b, c;
  a = (cur + 1) % P, b = (cur + P - 1) % P, c = quickpow(cur, P - 2);
  if (pre1.find(a) == pre1.end()) {
    q1.push_back(a);
    pre1[a] = front1;
  }
  if (pre1.find(b) == pre1.end()) {
    q1.push_back(b);
    pre1[b] = front1;
  }
  if (pre1.find(c) == pre1.end()) {
    q1.push_back(c);
    pre1[c] = front1;
  }
  if (pre2.find(a) != pre2.end()) {
    f = true;
    getans(a);
    return;
  }
  if (pre2.find(b) != pre2.end()) {
    f = true;
    getans(b);
    return;
  }
  if (pre2.find(c) != pre2.end()) {
    f = true;
    getans(c);
    return;
  }
  front1++;
}
void BFS2() {
  long long cur = q2[front2], a, b, c;
  a = (cur + P - 1) % P, b = (cur + 1) % P, c = quickpow(cur, P - 2);
  if (pre2.find(a) == pre2.end()) {
    q2.push_back(a);
    pre2[a] = front2;
  }
  if (pre2.find(b) == pre2.end()) {
    q2.push_back(b);
    pre2[b] = front2;
  }
  if (pre2.find(c) == pre2.end()) {
    q2.push_back(c);
    pre2[c] = front2;
  }
  if (pre1.find(a) != pre1.end()) {
    f = true;
    getans(a);
    return;
  }
  if (pre1.find(b) != pre1.end()) {
    f = true;
    getans(b);
    return;
  }
  if (pre1.find(c) != pre1.end()) {
    f = true;
    getans(c);
    return;
  }
  front2++;
}
void BFS() {
  while (!f) {
    while (!f && q1.size() > q2.size()) {
      BFS2();
    }
    while (!f && q1.size() <= q2.size()) {
      BFS1();
    }
  }
}
int main() {
  long long u, v;
  scanf("%lld%lld%lld", &u, &v, &P);
  if (u != v) {
    pre1[u] = -1, pre2[v] = -1;
    q1.push_back(u), q2.push_back(v);
    BFS();
    int size = ans.size();
    printf("%d\n", size);
    for (int i = 0; i < size; i++) {
      printf("%d%c", ans[i], i == size - 1 ? '\n' : ' ');
    }
  } else
    printf("0\n");
  return 0;
}

```