Problem C
Communicating The Strategy

This is an interactive problem.

During a Pokenom battle, a Pokenom trainer must come up with a strategy and communicate the strategy to his Pokenom in a very efficient way.

To become the best Pokenom trainer, Bash is practicing how to communicate the strategy to his Pokenom, Chikapu.

More formally, Bash’s strategy is a sequence of integers of length $n$ $(1 \le n \le 100)$. Bash needs to communicate this strategy to Chikapu. Let’s denote this sequence as $A_{1}, A_{2}, \ldots , A_{n}$ $(1 \le A_{i} \le 10^9)$.

First, Bash gives Chikapu the integer $n$. Then Chikapu can ask Bash multiple questions about the sequence. Bash answers each question immediately, before Chikapu asks another question. For each question Chikapu gives Bash $2$ indices $l$ and $r$ $(1 \leq l \leq r \leq n)$. Bash then selects an arbitrary integer $k$ $(1 \leq k \leq r - l + 1)$, and considers all subsets of size $k$ of the sequence $a_{l}, a_{l+1}, \ldots , a_{r}$ (there are ${r-l+1}\choose {k}$ such subsets). For each subset, Bash calculates the product of all elements. Finally, Bash gives Chikapu the number $S\bmod (10^9 + 7)$, where $S$ is the sum of all products; as well as the number $k$ he has chosen.

Note that Bash can select any values of $k$ that he wants, Chikapu only knows which numbers he chooses, Chikapu does not know how and why he chooses them.

Because the communication has to be as efficient as possible, Bash considers the weight of a $(l, r)$ query to be $\frac{1}{(r-l+1)^2}$. Chikapu must find the sequence after asking queries with total weight of at most $\frac{5}{3}$.

Chikapu can run fast and shoot thunderbolts, but Chikapu is not good with numbers. Please help Chikapu!

Interaction

First, your program reads the integer $n$ $(1 \leq n \leq 100)$ from the standard input. Then the following process repeats:

• Your program writes to the standard output in either format:

  • $1$ $l$ $r$, meaning that you want to ask a query with two indices $l$ and $r$ $(1 \leq l \leq r \leq n)$.

  • $2$ $A_{1} A_{2} \ldots A_{n}$, meaning that you want to guess the sequence $(1 \le A_ i \le 10^9)$.

• If your program asks a query, two integers $k$ $S$ will be available in the standard input. Your program then reads them.

• If your program guesses the sequence, your answer will be checked. Your program should terminate immediately after this.

The input guarantees that $S$ is not a multiple of $10^9 + 7$ for all possible $k, l, r$.

Communication example

Note

When you write the solution for the interactive problem it is important to keep in mind that if you output some data it is possible that this data is first placed to some internal buffer and may be not directly transferred to the interactor. In order to avoid such situation you have to use special ‘flush’ operation each time you output some data. There are these ‘flush’ operations in standard libraries of almost all languages. For example, in C++ you may use ‘fflush(stdout)’ or ‘cout << flush’ (it depends on what do you use for output data — ‘scanf/printf’ or ‘cout’). In Java you can use method ‘flush’ for output stream, for example, ‘System.out.flush()’. In Python you can use ‘stdout.flush()’.