#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return {i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
using ld = long double;
using ll = long long;
int mod = 1000 * 1000 * 1000 + 7;
void OdejmijOd(int& a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
int Odejmij(int a, int b) {
  OdejmijOd(a, b);
  return a;
}
void DodajDo(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int Dodaj(int a, int b) {
  DodajDo(a, b);
  return a;
}
int Mnoz(int a, int b) { return (ll)a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) {
  int res = 1;
  while (b) {
    if (b % 2 == 1) MnozDo(res, a);
    a = Mnoz(a, a);
    b /= 2;
  }
  return res;
}
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) {
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
template <typename T>
T Maxi(T& a, T b) {
  return a = max(a, b);
}
template <typename T>
T Mini(T& a, T b) {
  return a = min(a, b);
}
int Ruch(int a, int b) {
  if (Dodaj(a, 1) == b) return 1;
  if (Odejmij(a, 1) == b) return 2;
  if (Odw(a) == b) return 3;
  assert(false);
}
vector<int> Generuj(int u) {
  vector<int> v;
  v.reserve(101);
  v.push_back(u);
  for (int i = 1; i <= 100; i++) {
    switch (rand() % 3) {
      case 0:
        v.push_back(Odw(v.back()));
        break;
      case 1:
        v.push_back(Dodaj(v.back(), 1));
        break;
      case 2:
        v.push_back(Odejmij(v.back(), 1));
        break;
      default:
        assert(false);
    }
  }
  return v;
}
int ile0, ile1;
void Odpowiedz(vector<int>& ciag) {
  cout << ciag.size() - 1 << endl;
  for (int i = 1; i < (int)ciag.size(); i++) {
    cout << Ruch(ciag[i - 1], ciag[i]) << ' ';
  }
  cout << endl;
  exit(0);
}
int main() {
  srand(0x89328);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int u, v;
  cin >> u >> v >> mod;
  map<int, vector<int>> mapa;
  ile0 = 0;
  for (int i = 0; i * i * 50 <= mod; i++) {
    ile0++;
    auto vec = Generuj(u);
    while (!vec.empty()) {
      auto& x = mapa[vec.back()];
      if (x.empty()) {
        x = vec;
      }
      vec.pop_back();
    }
  }
  ile1 = 0;
  while (true) {
    ile1++;
    auto vec = Generuj(v);
    auto it = mapa.find(vec.back());
    if (it != mapa.end()) {
      vector<int> res = it->second;
      reverse(vec.begin(), vec.end());
      assert(res.back() == vec[0]);
      res.pop_back();
      for (int x : vec) res.push_back(x);
      assert(res[0] == u);
      assert(res.back() == v);
      Odpowiedz(res);
    }
  }
  return 0;
}

### Prompt

Please create a solution in CPP 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 GCC optimize("O3")
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return {i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
using ld = long double;
using ll = long long;
int mod = 1000 * 1000 * 1000 + 7;
void OdejmijOd(int& a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
int Odejmij(int a, int b) {
  OdejmijOd(a, b);
  return a;
}
void DodajDo(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int Dodaj(int a, int b) {
  DodajDo(a, b);
  return a;
}
int Mnoz(int a, int b) { return (ll)a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) {
  int res = 1;
  while (b) {
    if (b % 2 == 1) MnozDo(res, a);
    a = Mnoz(a, a);
    b /= 2;
  }
  return res;
}
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) {
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
template <typename T>
T Maxi(T& a, T b) {
  return a = max(a, b);
}
template <typename T>
T Mini(T& a, T b) {
  return a = min(a, b);
}
int Ruch(int a, int b) {
  if (Dodaj(a, 1) == b) return 1;
  if (Odejmij(a, 1) == b) return 2;
  if (Odw(a) == b) return 3;
  assert(false);
}
vector<int> Generuj(int u) {
  vector<int> v;
  v.reserve(101);
  v.push_back(u);
  for (int i = 1; i <= 100; i++) {
    switch (rand() % 3) {
      case 0:
        v.push_back(Odw(v.back()));
        break;
      case 1:
        v.push_back(Dodaj(v.back(), 1));
        break;
      case 2:
        v.push_back(Odejmij(v.back(), 1));
        break;
      default:
        assert(false);
    }
  }
  return v;
}
int ile0, ile1;
void Odpowiedz(vector<int>& ciag) {
  cout << ciag.size() - 1 << endl;
  for (int i = 1; i < (int)ciag.size(); i++) {
    cout << Ruch(ciag[i - 1], ciag[i]) << ' ';
  }
  cout << endl;
  exit(0);
}
int main() {
  srand(0x89328);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int u, v;
  cin >> u >> v >> mod;
  map<int, vector<int>> mapa;
  ile0 = 0;
  for (int i = 0; i * i * 50 <= mod; i++) {
    ile0++;
    auto vec = Generuj(u);
    while (!vec.empty()) {
      auto& x = mapa[vec.back()];
      if (x.empty()) {
        x = vec;
      }
      vec.pop_back();
    }
  }
  ile1 = 0;
  while (true) {
    ile1++;
    auto vec = Generuj(v);
    auto it = mapa.find(vec.back());
    if (it != mapa.end()) {
      vector<int> res = it->second;
      reverse(vec.begin(), vec.end());
      assert(res.back() == vec[0]);
      res.pop_back();
      for (int x : vec) res.push_back(x);
      assert(res[0] == u);
      assert(res.back() == v);
      Odpowiedz(res);
    }
  }
  return 0;
}

```