Let p to be a prime number. P-adic number (a_{0}, a_{1}, ...)_p is defined as formal sum a_{0} p^{0} + a_{1} p^{1} + ..., where a_{i} are integers, 0 ≤ a_{i} ≤ p-1.
The section of p-adic number A=(a_{0}, a_{1}, ...)_p of length n is defined as non-negative integer A_{n} = a_{0} p^{0} + a_{1} p^{1} + ... + a_{n} p^{n}. The sum of p-adic numbers A and B is another p-adic number C = A + B such for any n, the equality C_{n} = A_{n} + B_{n} (mod p^{n+1}) holds. Similarly, the product of two p-adic numbers can be defined.

Let's name p-adic number E=(1,0,0,0,...)_p as "one". For each natural number n, let's assign a p-adic number N that is equal to E+E+E .. + E (n items). For example, for natural number 14, in 3-adic notation, we'll assign (2,1,1,0,0,...)_3.

Let a and b to be natural numbers, A and B correspondent p-adic numbers. For rational number a/b, let's assign a p-adic number X, that is the root of equation B * X = A. If a and b are mutually disjoint with p, the equation has the single solution, and p-adic notation (x_{0}, x_{1}, ...)_p of the number X is periodic. For instance, for the fraction 1/2 is associated with 3-adic number (2,1,1,1,1,1,...)_3.
Given the fraction, you are to find its p-adic notation.

Input
The first line contains three natural numbers a, b, p, that do not exceed 30000.
a and b are mutually disjoint with p.

Output
The first line should contain two integers — the length of the smallest pre-period and the length of the period of p-adic notation of the required X.
The second and the third line should contain figures of pre-period and period.