Problem Background

Some of us get dipped in flat, some in satin, some in gloss. But every once in a while you find someone who's iridescent, and when you do, nothing will ever compare. Flipped

Problem Description

This is an interactive problem and only supports C++ submissions.

Little $\delta$ needs to accompany little $\tau$ to go shopping. Little $\tau$ wants to buy a piece of clothing and a pair of pants. In the mall there are $n$ pieces of clothing with prices $a_0,a_1,\cdots,a_{n-1}$, and $m$ pairs of pants with prices $b_0,b_1,\cdots,b_{m-1}$.

Little $\tau$ hopes to buy clothes as expensive as possible, but in the end little $\delta$ pays, and little $\delta$ does not want to spend too much money. Therefore, the two decide to determine what to buy through a game before shopping.

This game is played with alternating moves; little $\tau$ moves first. Initially, the candidate list contains all clothes and pants in the mall. On each turn, the player chooses one piece of clothing or one pair of pants and permanently deletes it from the candidate list. The two agree in advance on a threshold $B$, which represents the maximum price little $\delta$ can accept. The winning conditions are as follows:

1. If at any moment there is no clothing left, or no pants left, then they can only choose not to shop. In this case little $\delta$ will not go bankrupt, but little $\tau$ does not get the clothes she wants, so little $\delta$ is considered the winner.
2. Otherwise, if at any moment, for all ways of choosing one remaining clothing and one remaining pair of pants, the sum of their prices satisfies $\le B$, then little $\delta$ can satisfy $\tau$ without going bankrupt, but little $\tau$ has to accept lower-quality clothes, so little $\delta$ is considered the winner.
3. Otherwise, if at any moment, for all ways of choosing one remaining clothing and one remaining pair of pants, the sum of their prices satisfies $>B$, then little $\delta$ realizes he cannot have enough money to satisfy little $\tau$. But since little $\tau$ is very important to him, he has to borrow money everywhere to pay, and little $\tau$ will be very happy, so little $\tau$ is considered the winner.

Formally, each move may choose an $a_i(0\le i < n)$ or a $b_i(0\le i < m)$ and delete it from the corresponding sequence (and decrease $n,m$ accordingly by $1$). If at any moment $n=0$ or $m=0$ or $\forall_{0\le i < n,0\le j < m} a_i+b_j\le B$, then little $\delta$ wins. Otherwise, if at any moment $\forall_{0\le i < n,0\le j < m} a_i+b_j>B$, then little $\tau$ wins.

Please note that if the initial position (before anyone makes a move) already satisfies a certain condition, then the game ends immediately according to that condition.

Now little $\delta$ has listed all $a_i$ and $b_i$. Before the game begins, he wants to know the minimum threshold $B$ that guarantees his victory, so he can prepare enough money in advance. Sometimes, he also wants you to provide a specific game process so that he can win the game.

Implementation Details

You need to include the header file flipped.h.

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

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

This function should return the minimum threshold $B$ for the given position. $a,b$ are the initial sequences ${a_i}$ and ${b_i}$ given in the statement. It is guaranteed that the given sequences are sorted in non-decreasing order.

You also need to implement:

void play(std::vector<int> a,std::vector<int> b,int B);

In this function, you need to play the game with the interactive library, where $a,b$ are the initial sequences ${a_i}$ and ${b_i}$, and $B$ is the given threshold. It is guaranteed that the given sequences are sorted in non-decreasing order.

You may call:

std::pair<int,int> move(int t,int x);

to perform one move and obtain the interactive library’s next move. Here $t=0$ means you choose from sequence $a$, $t=1$ means you choose from sequence $b$, and $x$ indicates the index (starting from $0$) in the chosen sequence. The interactive library returns a std::pair<int,int> $(t,x)$ with the following meaning:

1. If $(t,x)=(-1,-1)$, it means your operation is illegal, or the game has ended (whether it ends after your move or after the library’s move). In this case, you should return immediately.
2. Otherwise, $(t,x)$ (in the same format) represents the next move made by the first player. You need to continue interacting.

Note that after deleting an element, the remaining elements are concatenated in their original order to form a new sequence, and all subsequent indices refer to the latest sequence.

The interaction procedure is as follows:

First, you need to determine whether little $\delta$ (the second player) can win. If you think he cannot win, please call move(0,0) once and return (the return value of move does not matter). In particular, if little $\tau$ has already won before the game starts, it is also treated as this case.

Otherwise, please call move(1,0) once; the interactive library will return the library’s first move in the format described above. In particular, if little $\delta$ has already won before the game starts, the library will return $(-1,-1)$. In that case, return immediately after calling move(1,0).

After that, you need to keep calling move to interact with the library until the library returns $(-1,-1)$. Note that you do not need to judge whether the game ends; the library will automatically do so.

In a single test file, solve or play may be called multiple times, and modifications to global variables may persist between calls. Be careful to clear state between test cases.

A reference implementation flipped.cpp is provided in the distributed files. For the evaluation part it returns $114514$, and for the interactive part it always assumes a solution exists and deletes the last element of some sequence. You may refer to the sample program to understand the interaction.

How to Test

A reference implementation of the interactive library grader.cpp is provided in the distributed files. The interactive library used in the final tests is different, so your solution must not rely on the specific implementation details of the library.

You need to compile an executable in the problem directory using:

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

The sample interactive library tests in the following format:

First read a variable $o=0/1$, where $o=0$ means testing the evaluation part, and $o=1$ means testing the interactive part.

Next, if $o=0$:

• Read an integer $T$, the number of test cases. For each test case:
• Read two integers $n,m$, the sizes of the two sequences.
• Next line reads $n$ non-decreasing integers $a_1,a_2,\cdots,a_n$, the input sequence $a$.
• Next line reads $m$ non-decreasing integers $b_1,b_2,\cdots,b_m$, the input sequence $b$.
• The library will call solve(a,b) automatically and print the returned result to standard output.

If $o=1$:

• Read an integer $T$, the number of test cases. For each test case:
• Read four integers $n,m,B,t$, the sizes of the two sequences, the given threshold $B$, and $t=0/1$ indicating whether the current position is winning for the second player ($t=1$ means second player wins, $t=0$ means first player wins).
• Next line reads $n$ non-decreasing integers $a_1,a_2,\cdots,a_n$, the input sequence $a$.
• Next line reads $m$ non-decreasing integers $b_1,b_2,\cdots,b_m$, the input sequence $b$.
• The library will call play(a,b,B) and interact with you. For each test case, the library outputs:
• If you do not correctly judge whether the second player is winning in your first call, the library outputs Wrong Answer.
• If your operation is illegal, the library outputs Invalid Operation: MESSAGE, where MESSAGE explains the reason in English. If you do not understand English, please check grader.cpp.
• If all your operations are legal but you do not win in the end (including returning early before the game ends), the library outputs You didn't win.
• If all your operations are legal and you win in the end, the library outputs OK.

Please note that since the problem guarantees that the sequences passed into solve are sorted in increasing order, you should also ensure that the sequences you pass in are sorted in increasing order, otherwise unpredictable results may occur. Also, if you attempt illegal interactive behavior, unpredictable results may occur; all potential consequences are at your own risk.

The sample interactor uses a very simple strategy. You may modify the sample interactor strategy as needed. In the final evaluation, the interactor will use a different strategy, and note that the final interactor is not guaranteed to play optimally. Your code must be able to handle any moves the interactor may make.

Example

Here is a small sample for the evaluation part (the format is the same as the evaluation input format of the interactive library). The distributed files also include several larger evaluation samples (ex_flipped*.in/ans), and one input in the same format as the interactive part (ex_sample_interactor.in), which can help you understand the input format.

Sample Input

0 5
2 2
2 4
3 5
3 5
1 3 5
2 3 4 5 6
4 4
1 4 5 9
2 3 7 7
3 8
7 9 9
4 4 4 4 8 8 8 8
5 4
2 4 5 7 9
3 6 8 10

Sample Output

7
6
8
13
12

Constraints

Contestants should not obtain internal information of the interactive library by illegal means, nor attack the interactive library in any form (including but not limited to interacting with standard IO). Such behavior is considered cheating.

It is guaranteed that, with all operations legal, the interactive library will not use more than 0.5s of time nor more than 128MB of memory. That is, you have at least 1.5s of time and 384MB of memory available.

For all data: $1\le T\le 10^5,n,m\ge 1,2\le \sum n+m\le 5\times 10^5,1\le a_i,b_i\le 10^9,1\le B\le 2\times 10^9$.

The table below gives the data limits for all subtasks; the numbers in the table are the points for the corresponding subtasks. Among them:

• In subtasks of the “Evaluation” column, the interactor will only call solve, and you score points if and only if all solve calls in that subtask return correct results.
• In subtasks of the “Interactive” column, the interactor will only call play, and you score points if and only if all play calls in that subtask correctly judge the game result, and for the winnable cases, successfully complete the game and finally win.

This problem uses bundled subtasks with dependencies. Specifically, each subtask depends on all subtasks above and to the left of it. In particular, this means all interactive subtasks depend on the evaluation subtask with the same data scale.

In QOJ judging, subtasks are numbered from top-left to bottom-right as $1\sim 10$ (for example, the third-tier partial-score interactive subtask is numbered $6$).