Important Notice: If you are new to interactive problems, please download the task package and read the beginner guide. Feel free to ask during the contest if you have any enquiries.

Given a $N \times M$ grid, where rows are numbered from $1$ to $N$ from top to bottom while columns are numbered from $1$ to $M$ from left to right. The cell on the $i^{\text{th}}$ row, $j^{\text{th}}$ column is denoted as $(i, j)$.

There is a treasure chest hidden somewhere in the grid which you don't know its position. Suppose it is located at cell $(X, Y)$.

To find the exact position of the treasure chest, you can perform the following operation any number of times:

• Choose a location $(X_0, Y_0)$ and teleport to cell $(X_0, Y_0)$.
• Then, you feel the row-distance between you and the chest. Let the distance be $A$. Formally, $A = |X - X_0|$.
• Similarly, you also feel the column-distance between you and the chest. Let the distance be $B$. Formally, $B = |Y - Y_0|$.
• However, due to some unknown limitations, the smaller value among $A$ and $B$ will be erased from your memory. All you get is the larger value among $A$ and $B$. That is, you only get to know the value of $max(A, B)$. Note that you do not know whether $A$ or $B$ is larger.

However, as you have limited stamina, you want to minimize the number of operations used to locate the treasure chest. The fewer operations you use, the higher score you get. Refer to "Scoring" section for further details.

Implementation Details

You should implement the procedure find_chest:

• This procedure will be called at most $10^3$ times per test case. You should implement your strategy, and return the answer here.
• $N$: The number of rows in the grid.
• $M$: The number of columns in the grid.
• It is guaranteed that the values of $X$ and $Y$ are fixed within a test case.
• When you are confident with your answer, you should return a pair $(X, Y)$, denoting the position of the treasure chest.

The above procedure can make use of (call) the following procedure:

• This procedure calculates the values of $A$ and $B$ based on the values of $X_0$ and $Y_0$ using the aforementioned mechanism and returns $max(A, B)$.
• $X_0$: The row number you want to teleport to. Note that $1 \le X_0 \le N$ must hold.
• $Y_0$: The column number you want to teleport to. Note that $1 \le Y_0 \le M$ must hold.
• This procedure can be called at most $10^4$ times per run. For a run, the fewer times this procedure is called, the higher score you can receive. Please refer to "Scoring" section for further details.

Example

Suppose $N = 3, M = 3$ and the treasure chest lies on cell $(2, 2)$. The procedure find_chest is called as follows:

Suppose you teleport to $(1, 2)$ and search for the chest. The procedure search is then called as follows:

The procedure calculates $A = |2 - 1| = 1$, $B = |2 - 2| = 0$ and returns $max(A, B) = 1$.

Then, you decided to teleport to $(2, 2)$ and search for the chest. search is then called as follows:

The procedure calculates $A = |2 - 2| = 0$, $B = |2 - 2| = 0$ and returns $max(A, B) = 0$.

Suppose you confirmed that the treasure chest lies on the cell $(2, 2)$. find_chest should return the following:

The total number of calls to search is $2$. Please note that this example might not conduct an optimal strategy.

Sample Grader

The sample grader reads the input in the following format:

• Line $1$: A single integer $T$, denoting the number of runs.
• Lines $2$ to $T+1$: Four integers $N$, $M$, $X$ and $Y$.

The grader will output $T$ lines, where the $i^{th}$ line denotes the verdict of the $i^{th}$ run for $1 \le i \le T$.

For a run, if your program is judged as incorrect, the error Wrong Answer: Reason will be outputted.

Otherwise, the grader outputs Accepted: $K$, where $K$ is the number of times search is called in a single run onfind_chest.

Reason can be one of the following:

• Incorrect Chest Location: This means when your program reports the answer, either $X$ or $Y$ is incorrect.
• Searched Out of Bounds: This means for at least one of your calls on search, either $1 \le X_0 \le N$ or $1 \le Y_0 \le M$ does not hold.
• Too Many Searches: This means your program called search for more than $10^4$ times for a run.

Please note that the sample grader does not check the validity of the input. Invalid input might cause unexpected behaviour.

Subtasks

For all test cases:

• $1 \le N, M \le 10^9$
• $1 \le X \le N$
• $1 \le Y \le M$

Subtask	Score	Additional Constraints
$1$	$18$	$N = 1$ $M \le 100$
$2$	$44$	$N = M \le 100$
$3$	$19$	$N = M$
$4$	$19$	No Additional Constraints

Scoring

For each run, you will receive zero score if your program does not exit correctly, violates any rules mentioned in the section "Implementation Details", makes more than $10^4$ calls on search in a single call to find_chest or does not report the coordinates of the treasure chest correctly.

Otherwise, let $K$ be the maximum number of times search is called over all calls to find_chest.

For subtask $1$, your score is calculated according to the following formula:

$$ \text{score} = \begin{cases} 18 & \text{if } K \le 1 \\ 11 & \text{if } K = 2 \\ 8 & \text{otherwise.} \end{cases} $$

For subtask $2$, your score is calculated according to the following formula:

$$ \text{score} = \begin{cases} 44 & \text{if } K \le 3 \\ 36 & \text{if } K = 4 \\ 32 & \text{if } K = 5 \\ 29 - 2(K - 6) & \text{if } 5 < K \le 8 \\ 25 - 1.6\sqrt{K - 8} & \text{if } 8 < K \le 50 \\ 14 & \text{if } 50 < K \le 400 \\ 4 & \text{otherwise.} \end{cases} $$

For subtasks $3$ and $4$, your score is calculated according to the following formula:

$$ \text{score} = \begin{cases} 19 & \text{if } K \le 3 \\ 12 & \text{if } K = 4 \\ 9.5 & \text{if } K = 5 \\ 7.5 - 1.5(K - 6) & \text{if } 5 < K \le 8 \\ 4 - 0.5\sqrt{K - 8} & \text{if } 8 < K \le 60 \\ 0 & \text{otherwise.} \end{cases} $$