Description

A cyclotron ($\text{Cyclotron}$) is a device that uses magnetic and electric fields to make charged particles move in circular paths and be repeatedly accelerated by a high-frequency electric field. It is an important instrument in high-energy physics.

We study a simplified model of a cyclotron. Consider the cyclotron as a circular track with $n$ accelerating cavities on it, numbered from $1$ to $n$ in order. A beam of protons is injected from one of the cavities. At the moment of injection, the beam’s kinetic energy is zero. The $i$-th cavity can provide the beam with $e_i$ kinetic energy. When the beam travels from cavity $i$ to cavity $i + 1$, it loses $d_i$ kinetic energy (since the track is circular, cavity $n$ is followed by cavity $1$).

Given the kinetic energy provided by each cavity and the kinetic energy lost when traveling between cavities, determine whether the beam can complete one full lap around the circular track. If it can, which cavity should be chosen for injection. While traveling between two cavities, the kinetic energy must not be zero. However, when the beam has just arrived at a cavity, its kinetic energy may be zero, because it can immediately obtain the kinetic energy provided by that cavity.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, the number of test cases. Then there is a blank line.

Next come $T$ test cases. Each test case consists of three lines. There is a blank line between two test cases.

The first line of each test case contains an integer $n$, the number of cavities. The second line contains $n$ integers, where the $i$-th integer is the kinetic energy $e_i$ that cavity $i$ can provide. The third line contains $n$ integers, where the $i$-th integer is the kinetic energy loss $d_i$ when the beam travels from cavity $i$ to cavity $i + 1$. Since the track is circular, the $n$-th integer on the third line represents the kinetic energy loss when traveling from cavity $n$ to cavity $1$.

Output Format

For each test case, output one line. If the beam cannot complete one full lap around the cyclotron, output Failed!. Otherwise, output the index of the cavity where the beam should be injected. If multiple cavities are possible, choose the one with the smallest index.

1

3
1 2 3
2 3 4

Failed!

1

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

2

Hint

Sample explanation.

Input #1.

This input has $3$ cavities, which can provide kinetic energies $1$, $2$, and $3$ in order. The loss from cavity $1$ to cavity $2$ is $2$, from cavity $2$ to cavity $3$ is $3$, and from cavity $3$ to cavity $1$ is $4$. No matter which cavity the beam is injected from, the kinetic energy becomes zero while traveling between two cavities, so it cannot complete one full lap.

Input #2.

This input has $10$ cavities. If the beam is injected from cavity $1$, it gains kinetic energy $1$, but it loses $3$ while traveling from cavity $1$ to cavity $2$, so it cannot complete one full lap. If it is injected from any cavity from $2$ to $10$, the kinetic energy can be kept non-zero while traveling between cavities, so any of them can be the injection cavity. However, cavity $2$ has the smallest index. Note that if the beam is injected from cavity $2$, when it reaches cavity $3$, its kinetic energy is exactly zero. According to the statement, this situation is allowed.

Constraints

• Subtask $1$: $2 \le n \le 10$, $10$ points.
• Subtask $2$: $2 \le n \le 10^3$, $30$ points.
• Subtask $3$: $2 \le n \le 10^5$, $30$ points.
• Subtask $4$: $2 \le n \le 10^6$, $30$ points.

For $100\%$ of the data, $1 \le T \le 20$, $0 \lt e_i \le 100$, $0 \lt d_i \le 100$.

Convention.

The direction of travel of the proton beam is defined as: from cavity $1$ to cavity $2$, from cavity $2$ to cavity $3$, $\cdots$ from cavity $n$ to cavity $1$.

Translated by ChatGPT 5