Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

D. Fall Guys
time limit per test
4 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

$$$\textit{Fall Guys}$$$ is a recently popular game. There are at most 60 players participating in a game and only one player will win finally after passing through one level after another.

$$$\textit{Fall Guys}$$$ has a level named climbing competition. Players will reach the destination after crossing many obstacles. After reaching the destination, they have to grab the crown to be the winner. But the crown moves up and down, and the player can catch it when the crown is below $$$h$$$ m.

Now, there are $$$n$$$ players participating in the climbing competition level. The height of the crown is $$$0$$$ at the beginning of the game, and then the crown will move up at a speed of $$$1$$$ m/s. When the height increases to $$$H$$$ m, the crown will immediately move down at a speed of $$$1$$$ m/s until the height decreases to $$$0$$$, and then move up and move down repeatedly.

The time that the $$$i$$$-th player reaches the destination is $$$x_i$$$. When a player reaches the destination, if the height of the crown is greater than $$$h$$$ m he will wait in place, otherwise he will immediately jump and grab the crown. However, each player has a delay time $$$c_i$$$ because of the bad network. Assuming that a player grab the crown at the moment of $$$t$$$ s, the system will determine that the moment he grab the crown is $$$(t+c_i)$$$ s.

The first player who grab the crown will win. If multiple players grab the crown at the same time, the winner is the player with the lower number.

You are given the arrival time $$$x_i$$$ and the delay time $$$c_i$$$ of all players, please calculate who will be the final winner.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 20)$$$ — the number of test cases. The description of the test cases follows.

The first line contains three integers $$$n,h,H$$$ $$$(1 \leq n \leq 2*10^5,1 \leq h \leq H \leq 300)$$$.

The second line contains $$$n$$$ integers $$$x_1,x_2,\dots,x_n(1 \leq x_i \leq 2*10^5)$$$ — the arrival time of the $$$i$$$-th player.

The third line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n(1 \leq c_i \leq 2*10^5)$$$ — the delay time of the $$$i$$$-th player.

Output

For each test case, print the winner.

Example
Input
2
4 2 5
3 6 1 9
6 4 2 3
3 1 2 
1 2 3
4 5 6
Output
3
1