Ever since Jan learned his numbers, he loved to make number riddles. Already as a small boy, he annoyed everyone with them. Right now, he made up a new guessing game and came to annoy you. You have to guess the numbers that Jan thinks.
Jan thinks of a sequence of N non-negative integers. Each of these integers has at most D digits. Your task is to guess the entire sequence using as few submits as possible. You can make two types of submits:
The scalar product of two sequences (X1, ..., XN) and (Y1, ..., YN) can be calculated as follows:
(X1, ..., XN) · (Y1, ..., YN) = X1.Y1 + ... + XN.YN
This means that Jan takes his first number and multiplies it by your first number, then he takes his second thought number and multiplies it by your second number and so on. In this way he will get N numbers. The scalar product of the two sequences is the sum of these N numbers.
The input file contains three positive integers: N, D and G separated by a single space. N is the length of the sequence that Jan is thinking of. D is the maximal number of digits of each of Jan's numbers. G is the maximal number of digits in the numbers you may use in your questions.
The output file you will be submitting must contain exactly N+1 rows. The first row must contain a zero (0) if the submit is a question, or a one (1) if the submit is a guess. The next N rows must contain the sequence you want to submit. More precisely, each of the next N rows must contain one non-negative integer. The integer must not contain unnecessary leading zeroes. If the submit is a question, each of the integers must contain at most G digits. If it is a guess, each of the integers must contain at most D digits.
For a malformed submit the evaluation result will be an appropriate error message.
For a question the answer will be one non-negative integer – the scalar product of Jan's sequence and the sequence you submitted. Note that the answer will always be exact and that it may contain more than G digits.
For an incorrect guess the evaluation result will be Wrong answer. For a correct guess the evaluation result will be OK, and you will receive points for solving the corresponding input.
Note that for each input you may only make ten (10) submits, i.e., at most 9 questions and a guess.
3 4 5Submits:
You: 0 7 3 5 Jan: 28 You: 0 6 4 1 Jan: 17 You: 0 0 2 2 Jan: 10 You: 1 1 2 3 Jan: OK
Note that for readability each of your submits was formatted to fit on a single line.
Problemsetter(s): misof (adapted from folklore)
Contest-related materials: Monika, misof, Mino