#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
const int N = 35000, M = 100;
int u, v, p;
int nxtpos[N + 7][M + 7], path[M + 7];
vector<array<int, 2>> endings;
int step(int r, int val, bool flag = false) {
  if (r == 1) {
    if (flag) return (val + p - 1) % p;
    return (val + 1) % p;
  }
  if (r == 2) {
    if (flag) return (val + 1) % p;
    return (val + p - 1) % p;
  }
  return (int)bigmod((long long)val, (long long)p - 2, (long long)p);
}
void generate() {
  srand(clock());
  for (int i = (1); i < (N + 1); i++) {
    int curr = u;
    for (int j = (1); j < (M + 1); j++) {
      int r = rand() % 3 + 1;
      curr = step(r, curr);
      nxtpos[i][j] = r;
    }
    endings.push_back({curr, i});
  }
  sort(endings.begin(), endings.end());
}
void printPath(int chain) {
  cout << 2 * M << "\n";
  int l = u;
  for (int i = 1; i <= M; i++) {
    cout << nxtpos[chain][i] << " ";
  }
  cout << "\n";
  for (int i = M; i >= 1; i--) {
    cout << path[i] << " ";
  }
  cout << "\n";
}
bool meets(int curr) {
  array<int, 2> t = {curr, 1};
  int where = lower_bound(endings.begin(), endings.end(), t) - endings.begin();
  if (where < N && endings[where][0] == curr) {
    printPath(endings[where][1]);
    return true;
  }
  return false;
}
void solve() {
  while (true) {
    int curr = v;
    for (int j = (1); j < (M + 1); j++) {
      int r = rand() % 3 + 1;
      curr = step(r, curr, true);
      path[j] = r;
    }
    if (meets(curr)) return;
  }
}
int main() {
  int test, cases = 1;
  cin >> u >> v >> p;
  if (u == v) {
    cout << 0 << "\n";
    return 0;
  }
  generate();
  solve();
  return 0;
}

### Prompt

Your challenge is to write 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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
const int N = 35000, M = 100;
int u, v, p;
int nxtpos[N + 7][M + 7], path[M + 7];
vector<array<int, 2>> endings;
int step(int r, int val, bool flag = false) {
  if (r == 1) {
    if (flag) return (val + p - 1) % p;
    return (val + 1) % p;
  }
  if (r == 2) {
    if (flag) return (val + 1) % p;
    return (val + p - 1) % p;
  }
  return (int)bigmod((long long)val, (long long)p - 2, (long long)p);
}
void generate() {
  srand(clock());
  for (int i = (1); i < (N + 1); i++) {
    int curr = u;
    for (int j = (1); j < (M + 1); j++) {
      int r = rand() % 3 + 1;
      curr = step(r, curr);
      nxtpos[i][j] = r;
    }
    endings.push_back({curr, i});
  }
  sort(endings.begin(), endings.end());
}
void printPath(int chain) {
  cout << 2 * M << "\n";
  int l = u;
  for (int i = 1; i <= M; i++) {
    cout << nxtpos[chain][i] << " ";
  }
  cout << "\n";
  for (int i = M; i >= 1; i--) {
    cout << path[i] << " ";
  }
  cout << "\n";
}
bool meets(int curr) {
  array<int, 2> t = {curr, 1};
  int where = lower_bound(endings.begin(), endings.end(), t) - endings.begin();
  if (where < N && endings[where][0] == curr) {
    printPath(endings[where][1]);
    return true;
  }
  return false;
}
void solve() {
  while (true) {
    int curr = v;
    for (int j = (1); j < (M + 1); j++) {
      int r = rand() % 3 + 1;
      curr = step(r, curr, true);
      path[j] = r;
    }
    if (meets(curr)) return;
  }
}
int main() {
  int test, cases = 1;
  cin >> u >> v >> p;
  if (u == v) {
    cout << 0 << "\n";
    return 0;
  }
  generate();
  solve();
  return 0;
}

```