#include <bits/stdc++.h>
const long long MAGIC = (1LL << 38);
long long t1, t2, t3;
int u, v, mod;
long long powmod(long long b, int e) {
  if (e == 1) return b;
  if (e & 1) return (powmod((b * b) % mod, e / 2) * b) % mod;
  return powmod((b * b) % mod, e / 2);
}
std::map<int, long long> m1, m2;
std::map<int, long long>::iterator it;
void dfs1(int t, long long mask, int m) {
  if (m) m1[t] = mask;
  if (mask > MAGIC) return;
  if ((mask & 3) != 2) {
    dfs1((t + 1) % mod, mask * 4 + 1, 0);
  }
  if ((mask & 3) != 1) {
    dfs1((t + mod - 1) % mod, mask * 4 + 2, 0);
  }
  if ((mask & 3) != 3) {
    dfs1(powmod(t, mod - 2), mask * 4 + 3, 1);
  }
}
void dfs2(int t, long long mask, int m) {
  if (m) m2[t] = mask;
  if (mask > MAGIC) return;
  if ((mask & 3) != 2) {
    dfs2((t + mod - 1) % mod, mask * 4 + 1, 0);
  }
  if ((mask & 3) != 1) {
    dfs2((t + 1) % mod, mask * 4 + 2, 0);
  }
  if ((mask & 3) != 3) {
    dfs2(powmod(t, mod - 2), mask * 4 + 3, 1);
  }
}
int main() {
  scanf("%d%d%d", &u, &v, &mod);
  if (mod < 200) {
    std::vector<int> ans;
    while (u != v) {
      u = (u + 1) % mod;
      ans.push_back(1);
    }
    printf("%d\n", ans.size());
    for (int i : ans) printf("%d ", i);
    return 0;
  }
  dfs1(u, 0, 1);
  dfs2(v, 0, 1);
  it = m2.begin();
  for (auto &p : m1) {
    while (it->first < p.first - 160) {
      ++it;
      if (it == m2.end()) {
        printf("fail\n");
        return 0;
      }
    }
    if (it->first > p.first + 160) continue;
    std::vector<int> ans, ans1, ans2, ans3;
    t1 = p.second;
    while (t1) {
      ans1.push_back(t1 & 3);
      t1 /= 4;
    }
    t1 = it->second;
    while (t1) {
      ans2.push_back(t1 & 3);
      t1 /= 4;
    }
    std::reverse(ans1.begin(), ans1.end());
    for (int i : ans1) ans.push_back(i);
    t1 = p.first - it->first;
    while (t1 > 0) {
      ans.push_back(2);
      t1--;
    }
    while (t1 < 0) {
      ans.push_back(1);
      t1++;
    }
    for (int i : ans2) ans.push_back(i);
    printf("%d\n", ans.size());
    for (int i : ans) {
      printf("%d ", i);
      if (i == 1) u = (u + 1) % mod;
      if (i == 2) u = (u + mod - 1) % mod;
      if (i == 3) u = powmod(u, mod - 2);
    }
    return 0;
  }
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
const long long MAGIC = (1LL << 38);
long long t1, t2, t3;
int u, v, mod;
long long powmod(long long b, int e) {
  if (e == 1) return b;
  if (e & 1) return (powmod((b * b) % mod, e / 2) * b) % mod;
  return powmod((b * b) % mod, e / 2);
}
std::map<int, long long> m1, m2;
std::map<int, long long>::iterator it;
void dfs1(int t, long long mask, int m) {
  if (m) m1[t] = mask;
  if (mask > MAGIC) return;
  if ((mask & 3) != 2) {
    dfs1((t + 1) % mod, mask * 4 + 1, 0);
  }
  if ((mask & 3) != 1) {
    dfs1((t + mod - 1) % mod, mask * 4 + 2, 0);
  }
  if ((mask & 3) != 3) {
    dfs1(powmod(t, mod - 2), mask * 4 + 3, 1);
  }
}
void dfs2(int t, long long mask, int m) {
  if (m) m2[t] = mask;
  if (mask > MAGIC) return;
  if ((mask & 3) != 2) {
    dfs2((t + mod - 1) % mod, mask * 4 + 1, 0);
  }
  if ((mask & 3) != 1) {
    dfs2((t + 1) % mod, mask * 4 + 2, 0);
  }
  if ((mask & 3) != 3) {
    dfs2(powmod(t, mod - 2), mask * 4 + 3, 1);
  }
}
int main() {
  scanf("%d%d%d", &u, &v, &mod);
  if (mod < 200) {
    std::vector<int> ans;
    while (u != v) {
      u = (u + 1) % mod;
      ans.push_back(1);
    }
    printf("%d\n", ans.size());
    for (int i : ans) printf("%d ", i);
    return 0;
  }
  dfs1(u, 0, 1);
  dfs2(v, 0, 1);
  it = m2.begin();
  for (auto &p : m1) {
    while (it->first < p.first - 160) {
      ++it;
      if (it == m2.end()) {
        printf("fail\n");
        return 0;
      }
    }
    if (it->first > p.first + 160) continue;
    std::vector<int> ans, ans1, ans2, ans3;
    t1 = p.second;
    while (t1) {
      ans1.push_back(t1 & 3);
      t1 /= 4;
    }
    t1 = it->second;
    while (t1) {
      ans2.push_back(t1 & 3);
      t1 /= 4;
    }
    std::reverse(ans1.begin(), ans1.end());
    for (int i : ans1) ans.push_back(i);
    t1 = p.first - it->first;
    while (t1 > 0) {
      ans.push_back(2);
      t1--;
    }
    while (t1 < 0) {
      ans.push_back(1);
      t1++;
    }
    for (int i : ans2) ans.push_back(i);
    printf("%d\n", ans.size());
    for (int i : ans) {
      printf("%d ", i);
      if (i == 1) u = (u + 1) % mod;
      if (i == 2) u = (u + mod - 1) % mod;
      if (i == 3) u = powmod(u, mod - 2);
    }
    return 0;
  }
}

```