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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Random;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.Map;
import java.math.BigInteger;
import java.io.BufferedReader;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskE {
		Random random = new Random(0);

		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int u = in.nextInt();
			int v = in.nextInt();
			int p = in.nextInt();
			boolean stress = false;
//		boolean stress = true;
			if (stress) {
				Random random = new Random();
				p = BigInteger.probablePrime(30, random).intValue();
				u = random.nextInt(p);
				v = random.nextInt(p);
				System.out.println(u + " " + v + " " + p);
			}
			Map<Integer, Integer> prev1 = new HashMap<>();
			Map<Integer, Integer> prev2 = new HashMap<>();
			Map<Integer, Integer> dist1 = new HashMap<>();
			Map<Integer, Integer> dist2 = new HashMap<>();
			int common = -1;
			outer:
			for (int step = 0; ; step++) {
				generateRandom(u, p, prev1, dist1);
				generateRandom(v, p, prev2, dist2);
				for (int x : prev1.keySet()) {
					if (prev2.containsKey(x)) {
						common = x;
						if (stress) {
							System.out.printf("found common %d in %d steps\n", common, step);
						}
						break outer;
					}
				}
			}
			List<Integer> us = path(u, common, p, prev1);
			List<Integer> vs = path(v, common, p, prev2);
			Collections.reverse(vs);
			for (int i = 0; i < vs.size(); i++) {
				int cmd = vs.get(i);
				if (cmd != 3) {
					vs.set(i, 3 - cmd);
				}
			}
			us.addAll(vs);
			check(us, u, v, p);
			out.println(us.size());
			for (int i = 0; i < us.size(); i++) {
				if (i > 0) {
					out.print(" ");
				}
				out.print(us.get(i));
			}
		}

		private void generateRandom(int s, int mod, Map<Integer, Integer> prev, Map<Integer, Integer> dist) {
			int x = s;
			prev.put(s, s);
			dist.put(s, 0);
			for (int step = 0; step < 200; step++) {
				int distX = dist.get(x);
				if (distX >= 100) {
					break;
				}
				int cmd = random.nextInt(3);
				int nx;
				if (cmd == 0) {
					nx = (x + 1) % mod;
				} else if (cmd == 1) {
					nx = (x + mod - 1) % mod;
				} else {
					nx = inv(x, mod);
				}
				if (dist.containsKey(nx) && dist.get(nx) <= dist.get(x)) {
					continue;
				}
				prev.put(nx, x);
				dist.put(nx, distX + 1);
				x = nx;
			}
		}

		private List<Integer> path(int src, int dst, int mod, Map<Integer, Integer> prev) {
			List<Integer> res = new ArrayList<>();
			int i = dst;
			while (i != src) {
				int pi = prev.get(i);
				if ((pi + 1) % mod == i) {
					res.add(1);
				} else if ((pi + mod - 1) % mod == i) {
					res.add(2);
				} else {
					if (pi != inv(i, mod)) throw new AssertionError();
					res.add(3);
				}
				i = pi;
			}
			Collections.reverse(res);
			return res;
		}

		private void check(List<Integer> us, int u, int v, int mod) {
			for (int cmd : us) {
				if (cmd == 1) {
					u = (u + 1) % mod;
				} else if (cmd == 2) {
					u = (u + mod - 1) % mod;
				} else {
					u = inv(u, mod);
				}
			}
			if (u != v) {
				throw new AssertionError();
			}
		}

		private int inv(int x, int p) {
			return pow(x, p - 2, p);
		}

		private int pow(long a, long n, long p) {
			long r = 1;
			while (n > 0) {
				if (n % 2 == 1) {
					r = r * a % p;
				}
				a = a * a % p;
				n /= 2;
			}
			return (int) r;
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}