   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
The Strongest Subchains
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 800 Accepted: 177

Description

Let A be an array of N , 1 < N <= 50000 and N is even, integers.We use A[i] to denote the ith element of the array.Hence the array contains elements A, A ? ? ? A[N − 1]. Each element of A is a nonnegative integer in the range of 0 through 9972. Given two integers x and y, let (x mod y) be the integer that is the remainder of y dividing x. It happens that A[i] = (a1*i *i + a2*i + a3) mod 9973 for some integers a1, a2, and a3. We know 1 <= ai <= 50000 for i = 1, 2, 3. For example, if N = 6, a1= 1, a2= 1, and a3= 1, then we have the following: There are three additional arrays S, E and R. Each of the three arrays has M , 1 <= M <= 50000, integers. We know 1 <= S[i] <= E[i] <= N . It happens that S[i] = (s1*i*i+ s2*i + s3) mod (N/2) and E[i] = S[i] + [(e1*i*i+ e2*i + e3) mod (N/2)]. Assume 1 <= si, ei<= 50000 for i = 1, 2, 3. We also know R[i] = min{A[S[i]], A[S[i] + 1], ... , A[E[i]]} for each i where 0 <= i <= M − 1. Your task is to find the smallest j such that R[j] = max{R, R, ... , R[M − 1]}. For example, if A is given as the above example, M = 3, s1= 1, s2= 1, s3= 1, e1= 1, e2= 1, and e3= 1, then we have the following: Hence max{R, R, R} = 3 and R has the smallest index with its value equaling 3. Thus we output 0.

Input

The first line contains the number of test cases w. Then the w test cases are listed one by one. Each test case is listed as follows in one line with a space between two integers: N , a1, a2, a3, M ,s1, s2, s3, e1, e2, e3.

Output

For each test case, output the smallest value j such that R[j] = max{R, R, R, . . . , R[M − 1]} in one line.

Sample Input

```1
6 1 1 1 3 1 1 1 1 1 1
```

Sample Output

`0`

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top