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}.

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

Given five numbers a, b, c, d, e, their median med(a,b,c,d,e) is the value that would be in the middle if we sorted them. For example, med(1,5,2,3,4) = 3, med(1,1,2,2,3) = 2, and med(1,2,7,2,10) = 2.

Your task is to write a program that works as follows:

• It is guaranteed that at the beginning of the program the value M has the form (2^a * 3^b * 5^c * 7^d * 11^e) for some 0 <= a,b,c,d,e <= 100.
• Let m = med(a,b,c,d,e).
• Your program must eventually terminate, and when it does, the final value M must be equal to 47^m.

Your program must satisfy the following additional constraints:

• At most 99 instructions.
• At most 3,000 steps of execution for any valid starting value M.
• 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 some tests where 0 <= a,b,c,d,e <= L. In particular, for L = 2 (the example case) it will be tested on exactly three tests that are listed in the example annotation. If your program correctly solves the sample, it means that it output a valid program that solves at least those three tests correctly.