题目描述

回旋加速器（$\text{Cyclotron}$）是利用磁场和电场使带电粒子作回旋运动并经高频电场反复加速的装置，是高能物理中的重要仪器。

我们来研究回旋加速器的一个简化模型。将回旋加速器视为一个环形的轨道，轨道上设置了 $n$ 个加速腔，依次编号为 $1$ 至 $n$。将一束质子从某个加速腔导入，在导入时，质子束的动能为零。第 $i$ 个加速腔能够为质子束提供 $e_i$ 的动能 ，质子束从第 $i$ 个加速腔运行到第 $i + 1$ 个加速腔会损失 $d_i$ 的动能（由于是环形轨道，编号为 $n$ 的加速腔后面是编号为 $1$ 的加速腔）。

给定每个加速腔能够提供的动能值以及质子束在各个加速腔之间运行所损失的动能值，试确定质子束能否绕环形轨道运行一周。如果能够成功，应该选择从哪个加速腔导入质子束。质子束在两个加速腔之间运行时，动能不能为零，但质子束刚到达加速腔时，动能可以为零，因为可以立即获得加速腔所提供的动能。

输入格式

输入包含多组测试数据。

输入第一行包含一个整数 $T$，表示测试数据的组数。接着是一个空行。

接下来是 $T$ 组数据，每组数据由三行构成。两组数据之间有一个空行。

每组数据的第一行是一个整数 $n$，表示加速腔的个数。第二行一共 $n$ 个整数，依次表示编号为 $i$ 的加速腔能够提供的动能 $e_i$。第三行一共 $n$ 个整数，依次表示质子束从第 $i$ 个加速腔运行到第 $i + 1$ 个加速腔所损失的动能 $d_i$。由于是环形轨道，第三行的第 $n$ 个整数表示的是从第 $n$ 个加速腔运行到第 $1$ 个加速腔时损失的动能。

输出格式

每组数据输出一行。如果质子束无法环绕加速器运行一周，输出 Failed!，否则输出导入质子束的加速腔编号，如果有多个加速腔可供选择，选择具有最小编号的加速腔。

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

提示

样例说明

输入 #1

该组输入共有 $3$ 个加速腔，依次能够提供的动能为 $1$、$2$、$3$。从第 $1$ 个加速腔运行到第 $2$ 个加速腔损失 $2$ 动能，从第 $2$ 个加速腔运行到第 $3$ 个加速腔损失 $3$ 动能，从第 $3$ 个加速腔运行到第 $1$ 个加速腔损失 $4$ 动能。不管从哪个加速腔导入质子束，都会使得质子束在两个加速腔运行过程中动能变为零，无法环绕轨道一周。

输入 #2

该组输入共有 $10$ 个加速腔，如果从第 $1$ 个加速腔导入质子束，将获得动能 $1$，但是在从第 $1$ 个加速腔运行到第 $2$ 个加速腔的过程中会损失 $3$ 动能，因此会使得质子束无法环绕轨道一周。而从第 $2$ 个到第 $10$ 个加速腔中的任意一个导入质子束，均能保证质子束在加速腔之间运行时动能不为零，因此都可作为导入质子束的加速腔，但编号为 $2$ 的加速腔具有最小的编号。需要注意，从第 $2$ 个加速腔导入质子束，当运行到第 $3$ 个加速腔时，动能恰为零，根据题意，这种情形是允许的。

数据范围

• Subtask $1$：$2 \le n \le 10$，$10$ 分。
• Subtask $2$：$2 \le n \le 10^3$，$30$ 分。
• Subtask $3$：$2 \le n \le 10^5$，$30$ 分。
• Subtask $4$：$2 \le n \le 10^6$，$30$ 分。

对于 $100\%$ 的数据，$1 \le T \le 20$，$0 \lt e_i \le 100$，$0 \lt d_i \le 100$。

约定

质子束的运行方向规定为：从第 $1$ 个加速腔到第 $2$ 个加速腔，从第 $2$ 个加速腔到第 $3$ 个加速腔$\cdots$从第 $n$ 个加速腔到第 $1$ 个加速腔。