Old Pigeon is a mythical OI contestant. He encountered a data structure exercise:

You are given $n$ numbers and a ternary comparator $compare(x, y, z)$, which takes in three numbers and returns the largest and smallest among them. The goal is to sort the $n$ numbers using as few comparisons as possible. Seeing this seemingly familiar problem, Old Pigeon became agitated: “I have a magical sorting pigeon. If you give it no more than $k$ numbers, it will return them sorted. It's leagues above that ternary comparator!”

ljt12138 wants to know: if you had such a sorting pigeon, how many comparisons would it take to sort $n$ numbers?

Task

You need to implement a function sort(int id, int n, int k, int *a):

• $1 \le id \le 3$ is the subtask ID passed in;
• $n$ is the length of the sequence;
• $k$ is the maximum number of items the sorting pigeon can sort at once;
• $a$ is the output array for the result.

You must store the position $0 \le p < n$ of the $i$-th smallest element (for all $1 \le i \le n$) from the original array into a[i - 1]. All indices are 0-based.

For example, if the array to be sorted is $A = [3, 2, 0, 1, 4]$, the sorted array is $A' = [0, 1, 2, 3, 4]$, then your returned array should be $a = [2, 3, 1, 0, 4]$.

In each test case, the interaction library will call the sort function exactly once.

You may call the function super_sort(int *a, int len, int *b) to ask the sorting pigeon to sort for you:

• len is the number of elements to be sorted. It must satisfy len \le k;
• a is an array containing the indices in the original array of the elements to be sorted, and $0 \le a[i] < n$;
• b is the output array containing the sorted indices (positions in the original array). That is, b is a permutation of a, and for all $i < j$, $A[b[i]] < A[b[j]]$.

Implementation Details

Only C++ is supported for this problem.

Your source code must include the header file sort.h.

You need to implement the function sort:

void sort(int id, int n, int k, int *a);

The interface for the super_sort function is:

void super_sort(int *a, int len, int *b);

How to Test Your Program

You need to compile the executable in this problem directory using the following command:

g++ grader.cpp sort.cpp -o sort -O2

The executable will read the following data format from standard input:

• The first line contains six integers: $id, n, k, L1, L2, L4$, where $1 \le id \le 3$ is the subtask ID, $n$ is the number of elements to sort, $k$ is the maximum length the sorting pigeon can handle per call, and $L1, L2, L4$ are scoring parameters, explained per subtask below.
• The second line contains $n$ integers: $A_0, A_1, \dots, A_{n-1}$, which is the array to be sorted. $A$ will be a permutation of ${0, 1, 2, \dots, n-1}$.

The interaction library will output the following information:

• If the array is successfully sorted, it will output a line like "cmp_cnt = cnt", where cnt is the number of times you called super_sort;
• Otherwise, it will output the corresponding error message.

If the input is invalid, the interaction library may not run properly.

You can refer to the provided interaction library for more information.

Sample Solution

You can compile it as described above to obtain an executable.

The sample source code is only provided to help you understand the problem. The result is not necessarily correct.

Since an interactive method is provided to verify correctness, this problem does not provide output samples.

Sample 1

input

0 8 2 100 1000 10000
2 1 0 3 4 6 5 7

Note: The sample has $id = 0$, which will not appear in actual test cases. This is only to demonstrate the input format.

Constraints

Subtask1 (8 points): $n = 1024$, $k = 4$, $L1 = 5700$, $L2 = 10000$, $L4 = 100000$

Subtask2 (24 points): $n = 1024$, $k = 16$, $L1 = 840$, $L2 = 1100$, $L4 = 3100$

Subtask3 (68 points): $n = 524288$, $k = 16$, $L1 = 562000$, $L2 = 800000$, $L4 = 1016000$

For each subtask, let c = cmp_cnt:

• If $c \le L1$, you will receive the full score for the subtask;
• If $L1 < c \le L2$, you will receive half the points;
• If $L2 < c \le L4$, you will receive a quarter of the points;
• If $L4 < c$ or sorting fails, you will receive no points, and be yelled at by the agitated sorting pigeon D.

Time Limit: $\texttt{2s}$

Memory Limit: $\texttt{512MB}$

The time and memory limits are shared between your code and the interaction library. We guarantee that for any valid data and any compliant use of the interface, any version of the interaction library (including both the released and final judging versions) will not exceed 0.5s in runtime and 12MB in memory usage. Therefore, the actual available time for contestants is at least 1.5s, and available memory is at least 500MB.