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 a1,a2,…,an 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≤k,p≤r
∣∣i=l∑kai−j=p∑raj∣∣ is maximum.
Here, ∣x∣ denotes the absolute value of x.
Input
The first line of the input contains an integer t(1≤t≤104) denotes the number of testcases.
The first line of each testcase contains an integer n(1≤n≤105).
The second line contains n space separated integers a1,a2,…,an(−109≤ai≤109).
The third line contains an integer q(1≤q≤105) denotes the number of queries.
The next q lines contain 2 space separated integers l,r(1≤l≤r≤n).
It is guaranteed that sum of n and sum of q over all testcases won’t exceed 105 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: ∣i=1∑2ai−j=3∑5aj∣=∣−2−17∣=∣−19∣=19
Query 2: ∣i=2∑2ai−j=3∑4aj∣=∣−3−8∣=∣−11∣=11
Query 3: ∣i=3∑3ai−j=3∑3aj∣=∣−3−(−3)∣=∣−3+3∣=0
These are the maximum possible distances in the given range.