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;
signed long long U, V, mo;
signed long long rev(signed long long a) {
  signed long long r = 1, n = mo - 2;
  a %= mo;
  while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a % mo, n >>= 1;
  return r;
}
map<signed long long, int> D[2];
map<signed long long, int> F[2];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> U >> V >> mo;
  D[0][U] = 0;
  D[1][V] = 0;
  for (i = 0; i < (2); i++) {
    queue<int> Q;
    Q.push(D[i].begin()->first);
    while (Q.size()) {
      x = Q.front();
      Q.pop();
      if (D[i][x] >= 15) continue;
      for (j = 0; j < (3); j++) {
        if ((j ^ i) == 0) y = (x + 1) % mo;
        if ((j ^ i) == 1) y = (x + mo - 1) % mo;
        if (j == 2) {
          if (x == 0) continue;
          y = rev(x);
        }
        if (D[i].count(y)) continue;
        D[i][y] = D[i][x] + 1;
        F[i][y] = j;
        Q.push(y);
      }
    }
  }
  for (auto& d0 : D[0])
    for (auto& d1 : D[1]) {
      int lef = 200 - d0.second - d1.second;
      if (min(abs(d0.first - d1.first), mo - abs(d0.first - d1.first)) <= lef) {
        vector<int> VV;
        int cur = d0.first;
        while (cur != U) {
          VV.push_back(F[0][cur] + 1);
          if (F[0][cur] == 0)
            cur = (cur + mo - 1) % mo;
          else if (F[0][cur] == 1)
            cur = (cur + 1) % mo;
          else if (F[0][cur] == 2)
            cur = rev(cur);
        }
        reverse((VV.begin()), (VV.end()));
        x = d0.first;
        y = d1.first;
        if (x < y && y - x > lef) x += mo;
        if (x > y && x - y > lef) y += mo;
        while (x != y) {
          if (y > x)
            VV.push_back(1), x++;
          else if (x > y)
            VV.push_back(2), x--;
        }
        cur = d1.first;
        while (cur != V) {
          VV.push_back(F[1][cur] + 1);
          if (F[1][cur] == 0)
            cur = (cur + 1) % mo;
          else if (F[1][cur] == 1)
            cur = (cur + mo - 1) % mo;
          else if (F[1][cur] == 2)
            cur = rev(cur);
        }
        cout << VV.size() << endl;
        for (auto& v : VV) cout << v << " ";
        cout << endl;
        return;
      }
    }
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}