You know it’s hard seeing your favorite person being interested in another one instead of you. At that time, you can do nothing rather than maximize the distance.

Swachha has a sequence of $n$ integers ${a_1, a_2, \dots, a_n}$ and Sumaiya has $q$ queries.

In a query, Sumaiya will give you $2$ integers $l$ and $r$. You have to find a pair of integers $k$ and $p$ such that $-$

• ${l \le k, p \le r}$

• $\Big| \sum\limits_{i = l}^{k} a_i - \sum\limits_{j = p}^{r} a_j \Big|$ is maximum.

Here, $|x|$ denotes the absolute value of $x$.

Input

The first line of the input contains an integer $t$ ${(1 \le t \le 10^4)}$ denotes the number of testcases.

The first line of each testcase contains an integer $n$ ${(1 \le n \le 10^5)}$.

The second line contains $n$ space separated integers ${a_1, a_2, \dots, a_n}$ ${(-10^9 \le a_i \le 10^9)}$.

The third line contains an integer $q$ ${(1 \le q \le 10^5)}$ denotes the number of queries.

The next $q$ lines contain $2$ space separated integers ${l, r}$ ${(1 \le l \le r \le n)}$.

It is guaranteed that sum of $n$ and sum of $q$ over all testcases won’t exceed $10^5$ respectively.

Output

For each query, print a pair of integers ${k, p}$ which fulfills the given conditions. If there are multiple possible pairs, you can print any one.

Sample

Input	Output
1 5 1 -3 2 6 9 5 1 5 2 4 3 3 1 3 2 5	2 3 2 3 3 3 2 3 2 3
Query $1$: $| \sum\limits_{i = 1}^{2} a_i - \sum\limits_{j = 3}^{5} a_j |$ ${= | - 2 - 17 | = |-19| = 19}$ Query $2$: $| \sum\limits_{i = 2}^{2} a_i - \sum\limits_{j = 3}^{4} a_j | = | - 3 - 8 | = |-11| = 11$ Query $3$: $| \sum\limits_{i = 3}^{3} a_i - \sum\limits_{j = 3}^{3} a_j | = | - 3 - (-3) | = |-3 + 3| = 0$ These are the maximum possible distances in the given range.