Malicious Frogs

In the lake there are ~N~ lily pads arranged in a row. Each one has a different name, a natural number from ~1~ to ~10^9~. You know the order of the lily pads, but during the night some frogs perform the following procedure to confuse you.

They choose a divisor of ~N~, say ~M~, with ~M \le \sqrt{N}~. Then, ~\frac{N}{M}~ times they select ~M~ lily pads that have not been selected before and place them in a circle, such that if you start from the lily pad that was earlier in the original sequence and continue clockwise, you obtain the previous relative order of the lily pads.

Then they start from the ~2~nd lily pad of the circle and, moving clockwise, they place them back into the row, each time filling the first empty position.

The next morning your colleague sees this and wants to give you a puzzle so that you can determine ~M~. You are allowed to ask him only ~200~ questions of the following type: "What is the name of the lily pad that is the ~k~-th in the sequence?"

Input (STDIN) - Output (STDOUT)

This problem is interactive, which means that you give instructions to the judge and it responds with information so you can continue.

1. The first line contains an integer ~N~: the number of lily pads. (~N \le 2 \cdot 10^4~)
2. The second line contains ~N~ integers: the names of the lily pads in the initial order.
3. You can make ~2~ types of queries:
   • 1 Κ - you ask which lily pad is at position ~K~ in the new sequence, and you receive the answer.
   • 2 Μ - you guess the number ~M~, the group size.

You are allowed to make ~200~ type ~1~ queries and only one query of type ~2~. Once you make it, the program terminates.

Example

Input (STDIN)

9
6 3 90 45 67 87 777 4 21

Possible questions and answers could be the following:

A possible grouping and rearrangement of the lily pads could be the following: ~1~ group: ~6, 4, 21~ ~2~ group: ~90, 87, 777~ ~3~ group: ~3, 45, 67~

Final order: 4 45 87 67 3 777 90 21 6

Subtasks

For ~25~% of the cases, the names of the lily pads are equal to their position in the initial sequence.

Note: In order for the interactive grader to work correctly, you must flush the lines that you print.

This can be done as follows:

• Python: print() does it automatically

print("1 8")

• C/C++ (cstdio): use printf as normal

  printf("1 8\n");
  

• C++ (iostream): use endl

  cout << "1 8" << endl;