题目描述

设 $A$ 是一个包含 $N$ 个整数的数组，其中 $1 < N \leq 50000$ 且 $N$ 为偶数。我们用 $A[i]$ 表示数组的第 $i$ 个元素，因此数组包含元素 $A[0], A[1], \cdots, A[N - 1]$。数组 $A$ 中的每个元素都是一个范围在 $0$ 到 $9972$ 之间的非负整数。给定两个整数 $x$ 和 $y$，设 $(x \bmod y)$ 为 $x$ 除以 $y$ 的余数。实际上，对于某些整数 $a_1$、$a_2$ 和 $a_3$，有 $A[i] = (a_1 \times i \times i + a_2 \times i + a_3) \bmod 9973$。我们知道对于 $i = 1, 2, 3$，有 $1 \leq a_i \leq 50000$。例如，如果 $N = 6$，$a_1 = 1$，$a_2 = 1$ 且 $a_3 = 1$，那么我们有如下情况：

另外还有三个数组 $S$、$E$ 和 $R$。这三个数组每个都包含 $M$ 个整数，其中 $1 \leq M \leq 50000$。我们知道 $1 \leq S[i] \leq E[i] \leq N$。实际上，$S[i] = (s_1 \times i \times i + s_2 \times i + s_3) \bmod (N/2)$ 且 $E[i] = S[i] + [(e_1 \times i \times i + e_2 \times i + e_3) \bmod (N/2)]$。假设对于 $i = 1, 2, 3$，有 $1 \leq s_i, e_i \leq 50000$。我们还知道对于每个 $i$（$0 \leq i \leq M - 1$），$R[i] = \min\{A[S[i]], A[S[i] + 1], \cdots, A[E[i]]\}$。你的任务是找出最小的 $j$，使得 $R[j] = \max\{R[0], R[1], \cdots, R[M - 1]\}$。例如，如果 $A$ 如上述示例所给，$M = 3$，$s_1 = 1$，$s_2 = 1$，$s_3 = 1$，$e_1 = 1$，$e_2 = 1$ 且 $e_3 = 1$，那么我们有如下情况：

因此，$\max\{R[0], R[1], R[2]\} = 3$，并且 $R[0]$ 是值等于 $3$ 的元素中索引最小的。所以我们输出 $0$。

输入

第一行包含测试用例的数量 $w$。然后依次列出 $w$ 个测试用例。每个测试用例在一行中列出，两个整数之间用一个空格分隔：$N$、$a_1$、$a_2$、$a_3$、$M$、$s_1$、$s_2$、$s_3$、$e_1$、$e_2$、$e_3$。

输出

对于每个测试用例，在一行中输出最小的 $j$ 值，使得 $R[j] = \max\{R[0], R[1], R[2], \cdots, R[M - 1]\}$。

输入样例

1
6 1 1 1 3 1 1 1 1 1 1

输出样例

0

题目来源

台湾 2002 年竞赛题目