This is a communication problem.

Given a positive integer $N$, pA has $N$ distinct integers $v_0, \dots, v_{N-1}$, and pB has $M$ intervals $[a_0, b_0], \dots, [a_{M-1}, b_{M-1}]$.

For each $i \in [0, M)$, pB wants to know the index of the maximum element in $v_{a_i}, v_{a_i+1}, \dots, v_{b_i}$. To achieve this, pA can send at most $2 \cdot 10^5$ bits of information to pB.

• Note that the upper bound on the amount of information pA sends to pB is only a hard limit used during evaluation. To obtain a full score, the information pA actually sends to pB must comply with the scoring rules of each subtask.

Write a program to implement the strategies for both pA and pB.

Implementation Details

You do not need to, and should not, implement a main() function, nor should you read or write any information to any file or standard input/output streams.

This problem only supports the C++ language. You need to implement two pieces of code to represent the strategies of pA and pB, respectively.

The first piece of code is save.cpp, which must include the header file save.h and implement the following function to describe pA's strategy:

void read_array(int subtask_id, const std::vector <int> &v);

• In each test case, this function will be called exactly once.
• The subtask_id parameter indicates the subtask number of the current test case.
• The v parameter represents the given sequence $v_0, \dots, v_{N-1}$.

You can call the following function:

void save_to_floppy(const std::string &bits);

• You can only call this function within the read_array function, and exactly once.
• The bits parameter is a string of 01s, representing the information pA sends to pB.

The second piece of code is load.cpp, which must include the header file load.h and implement the following function to describe pB's strategy:

std::vector <int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector <int> &a, const std::vector <int> &b);

• In each test case, this function will be called exactly once.
• The bits parameter is the string of 01s sent by pA.
• The a and b parameters describe $M$ queries, where $a_i$ and $b_i$ for the $i$-th query are a[i] and b[i] respectively.

Examples

In the provided files, you can find the sample interactor grader.cpp. You can use the implementation of the sample interactor to help you understand and implement this problem. Note that during final testing, the implementation of the interactor will differ from the sample interactor, so you should not rely on the implementation details of this interactor.

The sample interactor reads data from standard input in the following format:

• The first line contains an integer representing subtask_id.
• The second line contains two positive integers $N, M$.
• The third line contains $N$ integers $v_0, \dots, v_{N-1}$.
• The following $M$ lines each contain three non-negative integers, representing $a_i, b_i$, and the correct answer for that query, respectively.

When the program terminates successfully, the sample interactor will output the following information to standard output:

• If your answer is correct, it will output OK!.
• If your answer is incorrect, it will output the corresponding error message.

You can use the following command in your terminal to compile your program:

g++ grader.cpp save.cpp load.cpp -o prog -O2

Note that the command above compiles the grader together with the two programs you implemented; you must avoid naming conflicts for global variables or functions between different files.

Please do not share global variables between the two pieces of code. During final evaluation, the save process and the load process will be called in two different processes, and they cannot share any global variables or functions.

Examples

The following is a possible input for the sample interactor:

2
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3

The following is a valid interaction process: In the save program, the interactor makes the following call:

read_array(
  /* subtask_id = */ 2,
  /* v          = */ {40, 20, 30, 10});

The contestant's program makes the following call within that function:

save_to_floppy(
  /* bits = */ "001100");

Subsequently, in the load program, the interactor makes the following call:

solve_queries(
  /* subtask_id = */ 2,
  /* N          = */ 4,
  /* bits       = */ "001100",
  /* a          = */ {0, 0, 0, 0, 1, 1, 1, 2, 2, 3},
  /* b          = */ {0, 1, 2, 3, 1, 2, 3, 2, 3, 3});

This function needs to return an array of the following $M$ integers:

{0, 0, 0, 0, 1, 2, 2, 2, 2, 3}

During final evaluation, for any valid interaction process, it is guaranteed that the interactor will use no more than $0.2$ seconds and no more than $4\text{ MiB}$ of memory.

Subtasks

If you do not return a result within the time limit ($1.0$ second) and memory limit ($512\text{ MiB}$) for a test case, or if a runtime error occurs, or if the final returned answer is incorrect, your score for that test case will be $0$.

Otherwise, let $L$ be the length of the information sent by pA to pB. Each test case in each subtask will have different scoring methods.

In a subtask, your score is the minimum of the scores of all test cases.

For all data, $N \le 4 \cdot 10^4$, $M \le 8 \cdot 10^4$, $-10^9 \le v_i \le 10^9$, and all $v_i$ are distinct.