Statistics

The International Olympiad in Informatics (IOI) is currently in progress. To honor this competition, our problems for this round have IOI-flavored stories.

Sometimes an IOI task will use a different model of computation in order to bring the contestants out of their comfort zone. For example, in the IOI 2012 task "Odometer" the contestants were programming a simple robot on a grid to solve some algorithmic problems. This problem will also offer you such an experience.

In this problem, a valid program is a finite sequence of positive rational numbers. Let N and D be the sequence of their numerators and the sequence of their denominators, respectively.

The memory of our program consists of a single positive integer M.

When executing a program, each step looks as follows:

1. Find the smallest i such that M * (N[i] / D[i]) is an integer.
2. If such an i does not exist, the program terminates.
3. Otherwise, the new value of M is M * (N[i] / D[i]).

(Note: operations * and / used above are operations on reals. In the implementation of an interpreter we first multiply M by N[i] and then we divide the result by D[i].)

Example:

Consider the program {1/8, 9/4, 3/2}. For this program we have N = {1, 9, 3} and D = {8, 4, 2}.

Whenever we start this program with M = 2^x, it will eventually terminate and the value of M at the end of the computation will be 3^y where y = x mod 3.

E.g., if we start with M = 2¹⁰ = 1024, during the computation we will see the values M = 128, M = 16, M = 2, and finally M = 3. At this point the computation stops because none of 3/8, 27/4, and 9/2 is an integer.

Note that the order of fractions matters. E.g., the program {9/4, 3/2, 1/8} converts 2^x into 3^x instead.

Other programs that also convert 2^x into 3^{x mod 3} include {1/8, 3/2}, {3/2, 1/27}, and {1/27, 3/2}.

------------------------------------------------------------------------

Your task is to write a program in this model with the following property: if the value M at the beginning of the program has the value (2^x * 3^y * 7), the program must eventually terminate and when it does, the final value M must be equal to 5^x*y. Your program must satisfy the following additional constraints:

• At most 25 instructions (i.e., fractions in your program).
• At most 6,000 steps of execution for any valid starting M with x, y <= 20.
• Each numerator and denominator must be a positive integer that fits into a signed 32-bit integer variable.
• The value of M must never exceed 10^2500.

As our backend does not support this weird model, your actual task is to write a program in an ordinary programming language that produces the program { N[0] / D[0], N[1] / D[1], ... } and returns the int[] { N[0], D[0], N[1], D[1], ... }.

Your program is given a int L. The output of your actual program (i.e., the returned program for the weird model) will be tested on a subset of all possible cases in which 0 <= x, y <= L and accepted if it correctly solves all of them. In particular, for the value L = 2 (the example case) we will test all nine pairs (x, y), so your program solves the example correctly iff it passes those nine tests.