#include <bits/stdc++.h>
std::unordered_map<int, int> d1, d2, p1, p2;
std::queue<int> q1, q2;
int mod, u, v;
int inv(int x) {
  int y = mod - 2, res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % mod;
    x = 1ll * x * x % mod, y >>= 1;
  }
  return res;
}
int add(int x) {
  ++x;
  if (x == mod) x = 0;
  return x;
}
int sub(int x) {
  --x;
  if (x == -1) x = mod - 1;
  return x;
}
int main() {
  scanf("%d%d%d", &u, &v, &mod);
  if (u == v) return puts("0"), 0;
  d1[u] = 0, d2[v] = 0;
  q1.push(u), q2.push(v);
  int ans = 0;
  for (int d = 0;; d++) {
    while (!q1.empty() && d1[q1.front()] == d) {
      int x = q1.front();
      q1.pop();
      int nxt = add(x);
      if (!d1.count(nxt)) {
        p1[nxt] = x;
        d1[nxt] = d + 1;
        if (d2.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q1.push(nxt);
      }
      nxt = sub(x);
      if (!d1.count(nxt)) {
        p1[nxt] = x;
        d1[nxt] = d + 1;
        if (d2.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q1.push(nxt);
      }
      nxt = inv(x);
      if (!d1.count(nxt)) {
        p1[nxt] = x;
        d1[nxt] = d + 1;
        if (d2.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q1.push(nxt);
      }
    }
    while (!q2.empty() && d2[q2.front()] == d) {
      int x = q2.front();
      q2.pop();
      int nxt = add(x);
      if (!d2.count(nxt)) {
        p2[nxt] = x;
        d2[nxt] = d + 1;
        if (d1.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q2.push(nxt);
      }
      nxt = sub(x);
      if (!d2.count(nxt)) {
        p2[nxt] = x;
        d2[nxt] = d + 1;
        if (d1.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q2.push(nxt);
      }
      nxt = inv(x);
      if (!d2.count(nxt)) {
        p2[nxt] = x;
        d2[nxt] = d + 1;
        if (d1.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q2.push(nxt);
      }
    }
  }
pr:
  printf("%d\n", d1[ans] + d2[ans]);
  static int k[210], cnt;
  cnt = d1[ans];
  int p = ans;
  while (cnt) {
    int d = p;
    p = p1[p];
    if (d == add(p))
      k[--cnt] = 1;
    else if (d == sub(p))
      k[--cnt] = 2;
    else
      k[--cnt] = 3;
  }
  cnt = d1[ans];
  p = ans;
  int maxcnt = cnt + d2[ans];
  while (cnt < maxcnt) {
    int d = p;
    p = p2[p];
    if (p == add(d))
      k[cnt++] = 1;
    else if (p == sub(d))
      k[cnt++] = 2;
    else
      k[cnt++] = 3;
  }
  for (int i = 0; i < maxcnt; i++) printf("%d ", k[i]);
  return 0;
}

### Prompt

Please formulate 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>
std::unordered_map<int, int> d1, d2, p1, p2;
std::queue<int> q1, q2;
int mod, u, v;
int inv(int x) {
  int y = mod - 2, res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % mod;
    x = 1ll * x * x % mod, y >>= 1;
  }
  return res;
}
int add(int x) {
  ++x;
  if (x == mod) x = 0;
  return x;
}
int sub(int x) {
  --x;
  if (x == -1) x = mod - 1;
  return x;
}
int main() {
  scanf("%d%d%d", &u, &v, &mod);
  if (u == v) return puts("0"), 0;
  d1[u] = 0, d2[v] = 0;
  q1.push(u), q2.push(v);
  int ans = 0;
  for (int d = 0;; d++) {
    while (!q1.empty() && d1[q1.front()] == d) {
      int x = q1.front();
      q1.pop();
      int nxt = add(x);
      if (!d1.count(nxt)) {
        p1[nxt] = x;
        d1[nxt] = d + 1;
        if (d2.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q1.push(nxt);
      }
      nxt = sub(x);
      if (!d1.count(nxt)) {
        p1[nxt] = x;
        d1[nxt] = d + 1;
        if (d2.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q1.push(nxt);
      }
      nxt = inv(x);
      if (!d1.count(nxt)) {
        p1[nxt] = x;
        d1[nxt] = d + 1;
        if (d2.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q1.push(nxt);
      }
    }
    while (!q2.empty() && d2[q2.front()] == d) {
      int x = q2.front();
      q2.pop();
      int nxt = add(x);
      if (!d2.count(nxt)) {
        p2[nxt] = x;
        d2[nxt] = d + 1;
        if (d1.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q2.push(nxt);
      }
      nxt = sub(x);
      if (!d2.count(nxt)) {
        p2[nxt] = x;
        d2[nxt] = d + 1;
        if (d1.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q2.push(nxt);
      }
      nxt = inv(x);
      if (!d2.count(nxt)) {
        p2[nxt] = x;
        d2[nxt] = d + 1;
        if (d1.count(nxt)) {
          ans = nxt;
          goto pr;
        }
        q2.push(nxt);
      }
    }
  }
pr:
  printf("%d\n", d1[ans] + d2[ans]);
  static int k[210], cnt;
  cnt = d1[ans];
  int p = ans;
  while (cnt) {
    int d = p;
    p = p1[p];
    if (d == add(p))
      k[--cnt] = 1;
    else if (d == sub(p))
      k[--cnt] = 2;
    else
      k[--cnt] = 3;
  }
  cnt = d1[ans];
  p = ans;
  int maxcnt = cnt + d2[ans];
  while (cnt < maxcnt) {
    int d = p;
    p = p2[p];
    if (p == add(d))
      k[cnt++] = 1;
    else if (p == sub(d))
      k[cnt++] = 2;
    else
      k[cnt++] = 3;
  }
  for (int i = 0; i < maxcnt; i++) printf("%d ", k[i]);
  return 0;
}

```