K. Permutation
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden permutation of $$$n$$$. Recall that a permutation of $$$n$$$ is a sequence where each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once. Piggy wants to unravel the permutation with some queries.

Each query must consist of a sequence (not necessarily a permutation) with $$$n$$$ integers ranging from $$$1$$$ to $$$n$$$ (both inclusive). Each query is answered with an integer $$$x$$$, indicating the number of the positions where the corresponding element in Piggy's query sequence matches that of the hidden permutation. For example, if the hidden permutation is $$$\{1, 3, 4, 2, 5\}$$$ and the sequence Piggy asks is $$$\{2, 3, 5, 2, 5\}$$$, he'll receive $$$3$$$ as the answer.

As Piggy is busy recently, he gives this problem to you. Find the permutation with no more than $$$6666$$$ queries.

Input

There is only one test case in each test file.

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 10^3$$$) indicating the length of the hidden permutation.

Interaction

To ask a query, output one line. First output 0 followed by a space, then print a sequence of $$$n$$$ integers ranging from $$$1$$$ to $$$n$$$ separated by a space. After flushing your output, your program should read a single integer $$$x$$$ indicating the answer to your query.

If you want to guess the permutation, output one line. First output 1 followed by a space, then print a permutation of $$$n$$$ separated by a space. After flushing your output, your program should exit immediately.

Note that the answer for each test case is pre-determined. That is, the interactor is not adaptive. Also note that your guess does not count as a query.

To flush your output, you can use:

  • fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
  • System.out.flush() in Java.
  • stdout.flush() in Python.
Example
Input
5

3

4

2
Output

0 3 1 3 2 2

0 3 1 5 2 2

0 3 5 4 4 4

1 3 1 5 2 4
Note

Please note that if you receive a Time Limit Exceeded verdict, it is possible that your query is invalid or the number of queries exceeds the limit.