This is an interactive problem.

Lavi is a star messenger who loves eating cakes. She believes the tastiness of each cake can be defined as a positive integer.

One day, her good friend Sally bought a cake. The tastiness of this cake is a positive integer $d$ not exceeding $W$, but Lavi only knows the value of $W$ at this moment. Now, Lavi wants to determine the value of $d$.

Using the power of a star messenger, Lavi can create at most $N$ cakes, each with a tastiness not exceeding $W + 200$, and inform Sally. Then, Sally will secretly mix the cake she bought into these cakes, and finally, Sally will sort all these cakes in ascending order of their tastiness. Since these cakes of different tastiness are indistinguishable in appearance, Lavi cannot immediately identify which cake Sally bought. However, Sally has a strong memory, so she clearly remembers the tastiness of each cake after sorting.

After the cakes are sorted, Lavi can make multiple queries to Sally: * Lavi selects several cakes and divides them into two disjoint groups, then Sally will inform Lavi of the relationship between the sum of the tastiness of the two groups of cakes.

Formally, suppose Lavi created $m$ cakes, and let $a_0, a_1, a_2, \dots, a_m$ be the tastiness of each cake after mixing in the cake Sally bought and sorting them. Lavi needs to provide two non-empty sets of indices $S_1, S_2$ such that $S_1, S_2 \subseteq \{0, 1, 2, \dots, m\}$ and $S_1 \cap S_2 = \emptyset$. Sally will inform Lavi of the relationship between $\sum_{i \in S_1} a_i$ and $\sum_{i \in S_2} a_i$.

Now Lavi needs your help! But she reminds you that too many queries will put a great test on Sally's memory, so Sally has placed a limit on the number of queries. Specifically, Sally will provide a positive integer $K$ before Lavi makes the cakes. If Lavi makes more than $K$ queries, your score will decrease as the number of queries increases.

Please assist Lavi in deciding the strategy for making the cakes and the subsequent query strategy.

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 cake.h by adding the following code at the beginning of your program:

#include "cake.h"

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

std::vector<int> bake_cakes(int N, int W, int K);

• $N$ represents the maximum number of cakes Lavi can create.
• $W$ represents the upper bound of the tastiness of the cake Sally bought.
• $K$ represents the query count threshold.
• This function needs to return an array of positive integers $c$, representing the tastiness of each cake Lavi creates, where:
  • The length $m$ of $c$ must not exceed $N$.
  • For all $0 \le i \le m - 1$, $1 \le c_i \le W + 200$.
• For each test case, this function will be called exactly once by the interactor, before any calls to the find_tastiness function.

int find_tastiness(int m, int W, int K);

• $m$ represents the number of cakes Lavi created, meaning the actual number of cakes after including the one Sally bought is $m + 1$.
• $W$ represents the upper bound of the tastiness of the cake Sally bought.
• $K$ represents the query count threshold.
• This function needs to return a positive integer $d$, representing the tastiness of the cake Sally bought as determined by Lavi.
• For each test case, this function may be called multiple times by the interactor, and each call is independent.

In this function, you can call the following function:

int compare_tastiness(std::vector<int> S1, std::vector<int> S2);

• $S_1, S_2$ are the sets of indices for the two groups of cakes. You must ensure $S_1, S_2$ are non-empty and contain distinct elements, i.e., $S_1, S_2 \subseteq \{0, 1, 2, \dots, m\}$ and $S_1 \cap S_2 = \emptyset$.
• This function returns an integer $r \in \{-1, 0, 1\}$ representing the relationship between $v_1 = \sum_{i \in S_1} a_i$ and $v_2 = \sum_{i \in S_2} a_i$, where $r = -1$ means $v_1 < v_2$, $r = 0$ means $v_1 = v_2$, and $r = 1$ means $v_1 > v_2$.
• In one call to find_tastiness, you can call this function at most 100 times.
• The grader is not adaptive; the tastiness $d$ of the cake Sally bought is determined before each call to find_tastiness.

Note: In any case, the time required for the interactor to run will not exceed 6 seconds.

Examples

Input 1

40 20 5 3
19 7 20

Output 1

Correct: found 19 in 4 compares
Correct: found 7 in 5 compares
Correct: found 20 in 5 compares
Correct. Max compare count is 5

Note 1

The interactor will perform the following call:

bake_cakes(40, 20, 5);

Lavi can create at most 40 cakes, the upper bound of the tastiness of the cake Sally bought is 20, and the query threshold is 5. One possible returned array is $[12, 1, 22, 9, 19, 1, 12, 12, 25]$. Next, the interactor will perform the following three calls:

find_tastiness(9, 20, 5);

In each call, the tastiness of the cake Sally bought is 19, 7, and 20, respectively. When the tastiness of the cake Sally bought is 19, the tastiness of all cakes after sorting is $[1, 1, 9, 12, 12, 12, 19, 19, 22, 25]$. At this time: If compare_tastiness([0, 2, 4], [1, 3, 5]) is called, the sum of tastiness in $S_1$ is $1 + 9 + 12 = 22$, and the sum of tastiness in $S_2$ is $1 + 12 + 12 = 25$, so the function returns $-1$. If compare_tastiness([8, 2, 6], [5, 0, 9]) is called, the sum of tastiness in $S_1$ is $22 + 9 + 19 = 50$, and the sum of tastiness in $S_2$ is $12 + 1 + 25 = 38$, so the function returns $1$. If compare_tastiness([0, 4, 7], [1, 3, 6]) is called, the sum of tastiness in $S_1$ is $1 + 12 + 19 = 32$, and the sum of tastiness in $S_2$ is $1 + 12 + 19 = 32$, so the function returns $0$. When the tastiness of the cake Sally bought is 7, the tastiness of all cakes after sorting is $[1, 1, 7, 9, 12, 12, 12, 19, 22, 25]$. At this time: If compare_tastiness([0, 1, 3], [6]) is called, the sum of tastiness in $S_1$ is $1 + 1 + 9 = 11$, and the sum of tastiness in $S_2$ is $19$, so the function returns $-1$.

Constraints

For all test data: $1 \le N \le 3 \times 10^3$, $1 \le W \le 10^9$, $1 \le K \le 100$, $1 \le T \le 2 \times 10^3$; For all $1 \le i \le T$, $1 \le d_i \le W$.

Subtasks

In any test case, if the return value of bake_cakes does not meet the constraints in the implementation details, or the call to compare_tastiness does not meet the constraints, or the return value of find_tastiness is incorrect, the subtask receives 0 points.

For each test case, let $Q$ be the maximum number of calls to compare_tastiness across all find_tastiness calls in that test case. The score for the program is calculated as follows: In test cases 1 and 2, if $Q \le K$, the score is the test case's full points; otherwise, the score is 0. In test case 3, the score is $\max(30 - 3 \cdot \max(Q - K, 0), 0)$. * In test case 4, the score is $\max(55 - 11 \cdot \max(Q - K, 0), 0)$.