This is an interactive problem.

Description

Little H and Little L are playing a game of guessing a permutation.

Little H has a permutation $p = [p_0, p_1, \dots, p_{n-1}]$ of $0 \sim n-1$. Little L knows the length $n$ of the permutation and wishes to guess the permutation $p$ by asking specific queries. Specifically, Little L can ask Little H queries of the following form: * Given non-negative integers $l, r$ such that $0 \le l \le r \le n-1$, find the smallest non-negative integer that does not appear in $p_l, \dots, p_r$.

However, Little H and Little L discovered that even with an arbitrary number of queries, it is sometimes not enough to uniquely determine the permutation $p$. Therefore, they agreed: assuming Little H's answer is $p$ and Little L's guessed permutation is $q$, if for any $0 \le l \le r \le n-1$, the smallest non-negative integer not appearing in the interval $p_l, \dots, p_r$ is always equal to the smallest non-negative integer not appearing in the interval $q_l, \dots, q_r$, then Little L's guess is considered correct.

To increase the difficulty of the game, Little H has limited the number of queries Little L can make. You need to help Little L guess Little H's permutation.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file perm.h by adding the following code at the beginning of your program:

#include "perm.h"

You need to implement the following two functions in your source file perm.cpp:

void init(int c, int t);

• $c$ and $t$ represent the test case ID and the number of test data groups, respectively. $c = 0$ indicates that the test case is a sample.
• For each test case, this function will be called exactly once by the interactor when the program starts.

std::vector<int> perm(int n);

• $n$ represents the length of the permutation.
• This function needs to return a permutation of $0 \sim n-1$, representing Little L's guess.
• For each test case, this function will be called exactly $t$ times by the interactor.

You can make a query by calling the following function:

int query(int l, int r);

• $l, r$ represent the query interval. You must ensure $0 \le l \le r \le n-1$.
• This function returns the smallest non-negative integer that does not appear in $p_l, \dots, p_r$.
• You must ensure that for each call to perm, the number of times this function is called does not exceed $6 \times 10^5$.

Note: In any case, the running time of the interactor during final testing will not exceed 0.1 seconds, and the memory used is of a fixed size, not exceeding 64 MiB.

Testing

The grader.cpp in the problem directory is a reference implementation of the interactor. The interactor used during final testing differs from this reference implementation, so your solution should not rely on the implementation details of the interactor.

You can compile the executable using the following command in the problem directory:

g++ grader.cpp perm.cpp -o perm -std=gnu++14 -O2 -static

For the compiled executable: The executable will read data from standard input in the following format: The first line of input contains two non-negative integers $c, t$, representing the test case ID and the number of test data groups. The following lines contain each test data group. For each test data group: The first line contains a positive integer $n$, representing the length of the permutation. The second line contains $n$ non-negative integers $p_0, p_1, \dots, p_{n-1}$, representing Little H's permutation. The executable will output data to standard output in the following format: For each test data group: The first line contains a string representing the test result. Among them: Correct. indicates that the result returned by the contestant is correct; Wrong answer. indicates that the result returned by the contestant is incorrect; Invalid operation. indicates that the contestant's call to the query function is invalid. If the result is Correct., the second line contains a non-negative integer representing the maximum number of query function calls made by the contestant across all test data.

Examples

Input 1

0 1
6
4 2 3 5 0 1

Output 1

Correct.
4

Note 1

This sample contains one test data group. For the first test data group, Little H's permutation is $p = [4, 2, 3, 5, 0, 1]$. One possible interaction process is as follows: Call query(0, 3), the interactor returns the smallest non-negative integer not appearing in $4, 2, 3, 5$, which is $0$. Call query(3, 4), the interactor returns the smallest non-negative integer not appearing in $5, 0$, which is $1$. Call query(1, 5), the interactor returns the smallest non-negative integer not appearing in $2, 3, 5, 0, 1$, which is $4$. Call query(3, 5), the interactor returns the smallest non-negative integer not appearing in $5, 0, 1$, which is $2$. * Return $q = [4, 2, 5, 3, 0, 1]$. It can be proven that the permutation $q$ is considered correct.

Examples 2

See perm/perm2.in and perm/perm2.ans in the contestant directory. This sample satisfies the constraints for test cases $4 \sim 8$.

Implementation Details

In this problem directory: 1. grader.cpp is the provided reference implementation of the interactor. 2. perm.h is the header file; you do not need to worry about its specific content. 3. template_perm.cpp is the provided sample code; you can refer to it to implement your own code.

Contestants should ensure they have backups of all provided files. During final evaluation, only the perm.cpp in the problem directory will be tested; modifications to files other than this program will not affect the evaluation results.

Constraints

For all test data: $t = 10$; $2 \le n \le 3 \times 10^4$; * For all $0 \le i \le n-1$, $0 \le p_i \le n-1$, and $p$ is a permutation of $0 \sim n-1$.

Special Property A: $p_0 = 0$. Special Property B: There exists a non-negative integer $k \in [0, n-1]$ such that $p_0, \dots, p_k$ is monotonically decreasing, and $p_k, \dots, p_{n-1}$ is monotonically increasing. Special Property C: $p$ is generated independently and uniformly at random from all permutations of $0 \sim n-1$.

Scoring

Note: Contestants should not obtain internal information about the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating; The final evaluation interactor is different from the sample interactor.

This problem is subject to the same constraints as traditional problems, such as compilation errors resulting in 0 points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded resulting in 0 points for the corresponding test case. Contestants can only access variables defined in their own program and variables provided by the interactor; attempting to access other address spaces may lead to compilation or runtime errors.

Each time the perm function is called, if the returned permutation is not considered correct, or the query function call is invalid, or the number of query function calls exceeds $6 \times 10^5$, the corresponding test case receives 0 points.

Based on the above conditions: In test cases $1 \sim 3$, the program receives full marks if and only if for each call to the perm function, the number of query function calls does not exceed $10^2$. In test cases $4 \sim 8$, let $m$ be the maximum number of queries per call to the perm function, then the program will receive $5 \cdot f(m)$ points, where $f$ is calculated as follows:

• In test cases $9 \sim 20$, let $m$ be the maximum number of queries per call to the perm function, then the program will receive $5 \cdot g(m)$ points, where $g$ is calculated as follows: