Maximum Distance

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.