This is an interactive problem.

Little Y's bank has $N$ customers, numbered from $0$ to $N-1$. Customer $i$ has $W_i$ amount of money in their account, and the deposit amounts of all customers are distinct.

Little P is a close partner of Little Y and wants to know which customer has the most money. Little P cannot directly access the deposit amounts, but he can send a series of requests. Each request contains several queries, where each query is a pair $(i, j)$ representing that Little P wants to know which of customer $i$ or customer $j$ has more money. If $W_i > W_j$, Little Y will answer $i$; otherwise, Little Y will answer $j$.

There are upper limits on the number of requests $t$ and the total number of queries $s$ across all requests. Your task is to help him write a program to find the customer with the most money.

Implementation Details

Please ensure that your submitted program starts with #include "richest.h".

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

You need to implement the following function:

int richest(int N, int T, int S);

• $N$ is the number of customers;
• $T$ is the maximum number of requests $t$ allowed for the current function call;
• $S$ is the maximum total number of queries $s$ allowed for the current function call;
• The function must return the index of the customer with the most money;
• For each test case, this function will be called exactly 10 times by the interactor.

You can send a request to the interactor by calling the following function:

std::vector<int> ask(std::vector<int> a, std::vector<int> b);

• When calling the ask function, you must ensure that the input vectors $a$ and $b$ have the same length, and every element in them must be a non-negative integer less than $N$, representing all the queries in this request;
• The function returns a std::vector<int> c of the same length as $a$ and $b$, where $c[i]$ is the index of the customer with the larger deposit amount between customer $a[i]$ and customer $b[i]$.

It is guaranteed that the interactor will run within 10 seconds under the specified limits for requests and queries. The memory used by the interactor is fixed and does not exceed 256 MiB.

Testing Your Program

The grader.cpp provided in the problem directory is a reference implementation of the interactor. The interactor used for final evaluation is different from this reference implementation, so your solution should not rely on the specific implementation of the interactor.

You can compile your program using the following command in the problem directory:

g++ grader.cpp richest.cpp -o richest -O2 -std=c++14 -static

For the compiled executable:

• The executable will read data from standard input in the following format:
  • The first line contains four non-negative integers $N, T, S, R$, where $R$ is the random seed used by the interactor to generate test data.
• After reading the input, the interactor will call the richest function 10 times to test your solution with the generated data. After the richest function returns, the interactor will output the following information:
  • The first 10 lines of output each contain three integers $r, t, s$, where $r$ is the return value of the richest function, and $t$ and $s$ are as defined in the problem description, followed by information regarding the correctness of that run.
  • The 11th line contains the summary information for all 10 runs.

Examples

Input 1

4 100 100

Output 1

1 2 5

Note

Suppose the test data generated by the executable is $N = 4$, $W = [101, 103, 102, 100]$, $T = 100$, $S = 100$. The interaction process: 1. Call richest(4,100,100) 2. Call ask([0,2],[1,3]), returns [1,2] ($W_0 < W_1, W_2 > W_3$) 3. Call ask([0,2,3],[1,1,1]), returns [1,1,1] ($W_0 < W_1, W_2 < W_1, W_3 < W_1$) 4. Return 1

In this example, $r = 1$, $t = 2$, $s = 5$, which satisfies the limits on requests and queries.

Provided Files

In the problem directory:

1. grader.cpp is the provided reference interactor.
2. richest.h is the header file; you do not need to worry about its contents.
3. template_richest.cpp is the provided example code, which you can use as a base for your implementation.

Participants should back up all provided files. Only richest.cpp in the problem directory will be tested during the final evaluation; modifications to other files will not affect the evaluation results.

Constraints

This problem has 2 test cases. The scores and data ranges for each test case are shown in the table below.

| :---: | :---: | :---: | :---: | :---: | | Test Case ID | Score | $N=$ | $T=$ | $S=$ | | $1$ | $15$ | $1\,000$ | $1$ | $499\,500$ | | $2$ | $85$ | $1\,000\,000$ | $20$ | $2\,000\,000$ |

Scoring

Note:

• Participants should not attempt to obtain internal information of the interactor through illegal means, such as trying to directly read the values of array $W$ or interacting directly with standard input/output streams. Such behavior will be considered cheating.
• The final evaluation interactor is different from the sample interactor and may be adaptive: it may dynamically adjust the values of $W$ as long as it does not contradict the results previously returned by ask.

This problem is subject to the same standard constraints as traditional problems. For example, compilation errors will result in 0 points for the entire problem, while runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test case. Participants may only access variables they have defined and those provided by the interactor within their allocated memory space; attempting to access other memory may result in compilation or runtime errors.

In each richest function call, the number of requests $t$ and the total number of queries $s$ used by the participant's program must be within the corresponding limits; otherwise, it will receive 0 points.

Based on the above conditions:

• In Test Case 1, the program receives full marks if and only if all ask function calls are valid and the answer returned by richest is correct.
• In Test Case 2, the score is calculated as follows:
  • If any ask function call is invalid, the score is 0.
  • If all ask function calls are valid, let $\max t$ be the maximum value of $t$ across all 10 calls to richest, and $\max s$ be the maximum value of $s$. The program will receive $\lfloor 85 \cdot f(\max t) \cdot g(\max s) \rfloor$ points, where $f$ and $g$ are calculated as shown in the tables below:

| :---: | :---: | | $\max t$ | $f(\max t)$ | | $\max t \leq 8$ | $1$ | | $9 \leq \max t \leq 20$ | $1-\frac{1}{4}\sqrt{\max t-8}$ |

| :---: | :---: | | $\max s$ | $g(\max s)$ | | $\max s \leq 1\,099\,944$ | $1$ | | $1\,099\,945 \leq \max s \leq 1\,100\,043$ | $1-\frac{1}{6} \log_{10} (\max s-1\,099\,943)$ | | $1\,100\,044 \leq \max s \leq 2\,000\,000$ | $\dfrac{2}{3}-\frac{1}{1\,500}\sqrt{\max s-1\,100\,043}$ |

The following table provides examples of how different values of $t$ and $s$ affect the score in Test Case 2:

| :---: | :---: | :---: | | $\max t$ | $\max s$ | Test Case 2 Score | | $=20$ | $\leq 1\,099\,944$ | $11$ | | $=19$ | | $14$ | | $=18$ | | $17$ | | $=17$ | | $21$ | | $=16$ | | $24$ | | $=15$ | | $28$ | | $=14$ | | $32$ | | $=13$ | | $37$ | | $=12$ | | $42$ | | $=11$ | | $48$ | | $=10$ | | $54$ | | $=9$ | | $63$ | | $\leq 8$ | $\in [1\,099\,974, 1\,099\,978]$ | $63$ | | $\leq 8$ | $\in [1\,099\,969, 1\,099\,973]$ | $64$ | | $\leq 8$ | $\in [1\,099\,965, 1\,099\,968]$ | $65$ | | $\leq 8$ | $\in [1\,099\,962, 1\,099\,964]$ | $66$ | | $\leq 8$ | $\in [1\,099\,959, 1\,099\,961]$ | $67$ | | $\leq 8$ | $\in [1\,099\,957, 1\,099\,958]$ | $68$ | | $\leq 8$ | $\in [1\,099\,955, 1\,099\,956]$ | $69$ | | $\leq 8$ | $\in [1\,099\,953, 1\,099\,954]$ | $70$ | | $\leq 8$ | $=1\,099\,952$ | $71$ | | $\leq 8$ | $=1\,099\,951$ | $72$ | | $\leq 8$ | $\in [1\,099\,949, 1\,099\,950]$ | $73$ | | $\leq 8$ | $=1\,099\,948$ | $75$ | | $\leq 8$ | $=1\,099\,947$ | $76$ | | $\leq 8$ | $=1\,099\,946$ | $78$ | | $\leq 8$ | $=1\,099\,945$ | $80$ | | $\leq 8$ | $\leq 1\,099\,944$ | $85$ |