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 Pow(long long a, long long b, long long p) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans *= a;
      ans %= p;
    }
    a *= a;
    a %= p;
    b >>= 1;
  }
  return ans;
}
long long gcd(long long a, long long b) { return b ? a : gcd(b, a % b); }
map<long long, int> s[2];
map<long long, int> s1[2];
map<long long, int> s2[2];
int main() {
  long long u, v, p;
  bool bl = 1;
  scanf("%lld %lld %lld", &u, &v, &p);
  for (int i = sqrt(p); i > 1; i--) {
    if (p % i == 0) {
      bl = 0;
      break;
    }
  }
  s[1].insert(make_pair(u, 0));
  s[0].insert(make_pair(v, 0));
  s1[1].insert(make_pair(u, 0));
  s1[0].insert(make_pair(v, 0));
  queue<pair<bool, long long> > q;
  q.push(make_pair(1, u));
  q.push(make_pair(0, v));
  while (!q.empty()) {
    pair<bool, long long> a = q.front();
    q.pop();
    if (a.first) {
      long long w1 = (a.second + 1) % p;
      long long w2 = (a.second - 1 + p) % p;
      long long w3 = (Pow(a.second, p - 2, p)) % p;
      if (s[1].find(w1) == s[1].end()) {
        s[1][w1] = 1;
        s1[1][w1] = s1[1][a.second] + 1;
        s2[1][w1] = a.second;
        if (s[0].find(w1) != s[0].end()) {
          stack<int> sw;
          queue<int> sq;
          printf("%d\n", s1[1][w1] + s1[0][w1]);
          for (long long i = w1; i != u; i = s2[1][i]) {
            int x = s[1][i];
            sw.push(x);
          }
          for (long long i = w1; i != v; i = s2[0][i]) {
            int x = s[0][i];
            sq.push(x);
          }
          while (!sw.empty()) {
            printf("%d ", sw.top());
            sw.pop();
          }
          while (!sq.empty()) {
            printf("%d ", sq.front());
            sq.pop();
          }
          return 0;
        }
        q.push(make_pair(a.first, w1));
      }
      if (s[1].find(w3) == s[1].end()) {
        s[1][w3] = 3;
        s1[1][w3] = s1[1][a.second] + 1;
        s2[1][w3] = a.second;
        if (s[0].find(w3) != s[0].end()) {
          stack<int> sw;
          queue<int> sq;
          printf("%d\n", s1[1][w3] + s1[0][w3]);
          for (long long i = w3; i != u; i = s2[1][i]) {
            int x = s[1][i];
            sw.push(x);
          }
          for (long long i = w3; i != v; i = s2[0][i]) {
            int x = s[0][i];
            sq.push(x);
          }
          while (!sw.empty()) {
            printf("%d ", sw.top());
            sw.pop();
          }
          while (!sq.empty()) {
            printf("%d ", sq.front());
            sq.pop();
          }
          return 0;
        }
        q.push(make_pair(a.first, w3));
      }
      if (s[1].find(w2) == s[1].end()) {
        s[1][w2] = 2;
        s1[1][w2] = s1[1][a.second] + 1;
        s2[1][w2] = a.second;
        if (s[0].find(w2) != s[0].end()) {
          stack<int> sw;
          queue<int> sq;
          printf("%d\n", s1[1][w2] + s1[0][w2]);
          for (long long i = w2; i != u; i = s2[1][i]) {
            int x = s[1][i];
            sw.push(x);
          }
          for (long long i = w2; i != v; i = s2[0][i]) {
            int x = s[0][i];
            sq.push(x);
          }
          while (!sw.empty()) {
            printf("%d ", sw.top());
            sw.pop();
          }
          while (!sq.empty()) {
            printf("%d ", sq.front());
            sq.pop();
          }
          return 0;
        }
        q.push(make_pair(a.first, w2));
      }
    } else {
      long long w1 = (a.second - 1 + p) % p;
      long long w2 = (a.second + 1) % p;
      long long w3 = (Pow(a.second, p - 2, p)) % p;
      if (bl && s[0].find(w3) == s[0].end()) {
        s[0][w3] = 3;
        s1[0][w3] = s1[0][a.second] + 1;
        s2[0][w3] = a.second;
        if (s[1].find(w3) != s[1].end()) {
          stack<int> sw;
          queue<int> sq;
          printf("%d\n", s1[1][w3] + s1[0][w3]);
          for (long long i = w3; i != u; i = s2[1][i]) {
            int x = s[1][i];
            sw.push(x);
          }
          for (long long i = w3; i != v; i = s2[0][i]) {
            int x = s[0][i];
            sq.push(x);
          }
          while (!sw.empty()) {
            printf("%d ", sw.top());
            sw.pop();
          }
          while (!sq.empty()) {
            printf("%d ", sq.front());
            sq.pop();
          }
          return 0;
        }
        q.push(make_pair(a.first, w3));
      }
      if (s[0].find(w1) == s[0].end()) {
        s[0][w1] = 1;
        s1[0][w1] = s1[0][a.second] + 1;
        s2[0][w1] = a.second;
        if (s[1].find(w1) != s[1].end()) {
          stack<int> sw;
          queue<int> sq;
          printf("%d\n", s1[1][w1] + s1[0][w1]);
          for (long long i = w1; i != u; i = s2[1][i]) {
            int x = s[1][i];
            sw.push(x);
          }
          for (long long i = w1; i != v; i = s2[0][i]) {
            int x = s[0][i];
            sq.push(x);
          }
          while (!sw.empty()) {
            printf("%d ", sw.top());
            sw.pop();
          }
          while (!sq.empty()) {
            printf("%d ", sq.front());
            sq.pop();
          }
          return 0;
        }
        q.push(make_pair(a.first, w1));
      }
      if (s[0].find(w2) == s[0].end()) {
        s[0][w2] = 2;
        s1[0][w2] = s1[0][a.second] + 1;
        s2[0][w2] = a.second;
        if (s[1].find(w2) != s[1].end()) {
          stack<int> sw;
          queue<int> sq;
          printf("%d\n", s1[1][w2] + s1[0][w2]);
          for (long long i = w2; i != u; i = s2[1][i]) {
            int x = s[1][i];
            sw.push(x);
          }
          for (long long i = w2; i != v; i = s2[0][i]) {
            int x = s[0][i];
            sq.push(x);
          }
          while (!sw.empty()) {
            printf("%d ", sw.top());
            sw.pop();
          }
          while (!sq.empty()) {
            printf("%d ", sq.front());
            sq.pop();
          }
          return 0;
        }
        q.push(make_pair(a.first, w2));
      }
    }
  }
  return 0;
}