In a small town, there's a ritual where each day, every resident takes a series of steps, either to the right or left, over $N$ days. Starting at the town center, each day, they move according to the guidance of a mystical scroll: a list of values, $X$ which determines their direction. On the $i^{th}$ day, a positive $X[i]$ sends them to the right by $X[i]$ steps, a negative $X[i]$ sends them to the left by $X[i]$ steps, and a zero means they stay where they are. Over time, the townsfolk became curious about their wanderings.

They posed $M$ queries, each asking: on which days did residents find themselves at least $W$ steps away from the town center, both for the first time and the last time? If residents are never at least $W$ steps away from the town center, the answer is $-1$.

Input format

• The first line contains a single integer $T$, which denotes the number of test cases.
• For each test case:
  • The first line contains $N$ denoting the number of days.
  • The second line contains $N$ space-separated integers, denoting the values of scroll $X$.
  • The next line contains $M$ denoting the number of queries.
  • The next $M$ lines contain an integer, denoting $W$.

Output format

For each test case, answer all the $M$ queries. For each query, print two days on which residents are at least a $W$ steps away from the town center, the first and last time in a new line.  If residents are never at least $W$ steps away from the town center, print $-1$ in a new line. 

Constraints

$1 \leq T \leq 10^5 \\ 1 ≤ N ≤ 10^6 \\ -10^{12} ≤ X[i] ≤ 10^{12}\ ∀\ i∈[1,N] \\ 1 ≤ M ≤ 10^6 \\ 1 ≤ W ≤ 10^{18} \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6 \\ \text{The sum of all values of M over all test cases doesn't exceed } 10^6$