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. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long u, v, p, l, tot, sum, minn;
string ans;
char mark;
struct node {
  long long d, step, flag;
  string c;
};
queue<node> q;
map<long long, int> ha;
map<long long, string> ha1;
map<long long, int> ha2;
inline long long read() {
  long long x = 0, ff = 1;
  char c;
  while (c < '0' || c > '9') {
    if (c == '-') ff = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - 48;
    c = getchar();
  }
  return x * ff;
}
inline long long ksm(long long x, long long y) {
  if (y == 0) return 1;
  if (y == 1) return x;
  long long k = ksm(x, y / 2) % p;
  if (y & 1)
    return k * k % p * x % p;
  else
    return k * k % p;
}
int main() {
  u = read();
  v = read();
  p = read();
  if (u == v) {
    printf("0\n");
    return 0;
  }
  q.push((node){u, 0, 1, ""});
  q.push((node){v, 0, 2, ""});
  ha[u] = 1;
  ha[v] = 2;
  while (!q.empty()) {
    node tmp = q.front();
    q.pop();
    long long x1 = (tmp.d + 1) % p, x2 = (tmp.d - 1) % p,
              x3 = ksm(tmp.d, p - 2) % p;
    if (tmp.step >= 101) continue;
    if (tmp.flag == 1) {
      if (!ha[x1])
        ha[x1] = tmp.flag, ha1[x1] = tmp.c + "1 ", ha2[x1] = tmp.step + 1,
        q.push((node){x1, tmp.step + 1, 1, tmp.c + "1 "});
      else if (ha[x1] == 2) {
        printf("%lld\n", tmp.step + 1 + ha2[x1]);
        cout << tmp.c + "1 " + ha1[x1];
        return 0;
      }
      if (!ha[x2])
        ha[x2] = tmp.flag, ha1[x2] = tmp.c + "2 ", ha2[x2] = tmp.step + 1,
        q.push((node){x2, tmp.step + 1, 1, tmp.c + "2 "});
      else if (ha[x2] == 2) {
        printf("%lld\n", tmp.step + 1 + ha2[x2]);
        cout << tmp.c + "2 " + ha1[x2];
        return 0;
      }
      if (!ha[x3])
        ha[x3] = tmp.flag, ha1[x3] = tmp.c + "3 ", ha2[x3] = tmp.step + 1,
        q.push((node){x3, tmp.step + 1, 1, tmp.c + "3 "});
      else if (ha[x3] == 2) {
        printf("%lld\n", tmp.step + 1 + ha2[x3]);
        cout << tmp.c + "3 " + ha1[x3];
        return 0;
      }
    }
    if (tmp.flag == 2) {
      if (!ha[x1])
        ha[x1] = tmp.flag, ha1[x1] = "2 " + tmp.c, ha2[x1] = tmp.step + 1,
        q.push((node){x1, tmp.step + 1, 2, "2 " + tmp.c});
      else if (ha[x1] == 1) {
        printf("%lld\n", tmp.step + 1 + ha2[x1]);
        cout << ha1[x1] + "2 " + tmp.c;
        return 0;
      }
      if (!ha[x2])
        ha[x2] = tmp.flag, ha1[x2] = "1 " + tmp.c, ha2[x2] = tmp.step + 1,
        q.push((node){x2, tmp.step + 1, 2, "1 " + tmp.c});
      else if (ha[x2] == 1) {
        printf("%lld\n", tmp.step + 1 + ha2[x2]);
        cout << ha1[x2] + "1 " + tmp.c;
        return 0;
      }
      if (!ha[x3])
        ha[x3] = tmp.flag, ha1[x3] = "3 " + tmp.c, ha2[x3] = tmp.step + 1,
        q.push((node){x3, tmp.step + 1, 2, "3 " + tmp.c});
      else if (ha[x3] == 1) {
        printf("%lld\n", tmp.step + 1 + ha2[x3]);
        cout << ha1[x3] + "3 " + tmp.c;
        return 0;
      }
    }
  }
  return 0;
}