Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given an array of N positive integers. Your task is to find a subarray of length exactly K such that the sum of its elements is divisible by D and the product of the elements is maximum among all such subarrays.

If there are multiple subarrays satisfying this condition with the same maximum product, print the Lexicographically smallest starting index of K length subarray.

If no such subarray exists, print -1.

Input

• First line t (1<=t<=2000)- the number of test cases.

• In each test case :

  • The first line contains three integers N, K, and D — (\(1<=N<=2 * 10^5\)), (\(1<=D,K<=N\)) the size of the array, required subarray length, and divisor respectively.
  • The second line contains N space-separated integers \(A₁, A₂, ..., A_N\) — the elements of the array . Array A contains only 0 and 1.

• Sum of N over all test case doesn't exceed \(2 * 10^5\)

Output

• In each test case :
  • Print the starting index (1-based) of the subarray with maximum product whose sum is divisible by D.
  • If no such subarray exists, print -1.

Sample

3
7 3 3
1 0 1 0 1 1 1
6 4 2
1 0 0 0 0 1
4 2 2
0 1 0 1

5
2
-1

Explanation

For 1st case, Subarrays of length 3:

• [1 0 1] → sum = 2 → not divisible by 3
• [0 1 0] → sum = 1 → not divisible by 3
• [1 0 1] → sum = 2 → not divisible by 3
• [0 1 1] → sum = 2 → not divisible by 3
• [1 1 1] → sum = 3 → divisible by 3, product = 1 (1* 1* 1)
  The maximum product among valid subarrays is 1, found at indice 5

For 2nd case, Subarrays of length 4:

• [1 0 0 0] → sum = 1 → not divisible by 2
• [0 0 0 0] → sum = 0 → divisible by 2, product = 0 (0 * 0 * 0 * 0)
• [0 0 0 1] → sum = 1 → not divisible by 2
  The maximum product among valid subarrays is 0, found at indice 2

For 3rd case, Subarrays of length 2:

• [0 1] → sum = 1 → not divisible by 2
• [1 0] → sum = 1 → not divisible by 2
• [0 1] → sum = 1 → not divisible by 2
  No subarray of length 2 has a sum divisible by 2. Therefore, no valid subarray exists.