URI Online Judge | 2071

Pharaoh's Bank

By XIV Maratona de Programação IME-USP, 2010 BR Brazil

Timelimit: 1

Only a few people know that, but the first banks appeared in Ancient Egypt, and they were very similar to the ones we have nowadays. The main bank was the Pharaoh, who decided, from time to time, to take to the State the content of some accounts. This would occur this way: Given N, the number of account holders at the Pharaoh's Bank (this was the bank's name), each account could have an amount of menes (currency in Ancient Egypt) which could be, as well, negative (indicating the person owed that amount to the bank), in other words, the state of each account was an integer ai. The Pharaoh's objective was to make a series of checks on his sudits' accounts. Given an interval [A, B] (corresponding to the accounts aA, aA+1, ... , aB-1, aB) the Pharaoh wanted to find the sub-interval which had the max sum, in other words, which's acquisition by the State would yield the Pharaoh the greater amount of money. This was explained to the account holders as being an offerend to Amon-Ahcid, the egypt God of money. Making these offerends regularly, the god would be satisfied and would allow the economic system to work perfectly. This lasted surprisingly more than 500 years, until in one of these acquisitions the account holders rebelled, took over the palace and killed the Pharaoh. The bank was robbed and the system fell down to pieces. It was only heard about banks hundreds of years later.

Your task is, given a register of accounts and a series of checks, determine for each check an interval of max sum.

Input

The input is composed of many instances. The first line of the input contains an integer T, indicating the number of instances. The first line of each instance contains an integer N, indicating the number of accounts at the Pharaoh's Bank, considering 1 ≤ N ≤ 100 000. The second line of each instance contains N integers, between -10 000 and 10 000, indicating the balance in the accounts. The third line contains an integer Q, considering 1 ≤ Q ≤ 100 000, indicating the number of checks that will be done. Each one of the Q following lines contains two integers A and B, considering 1 ≤ A, BN, indicating the interval that is going to be checked.

Output

For each instance, your program must generate Q lines in the output, one for each check. Each one of these lines must contain two integers: the first represents the sum of the interval with the biggest sum, and the second, the number of elements in this interval. If there's more than one interval with the biggest sum, print the number of elements in the one that has more elements.

Sample Input Sample Output

3
3
-1 -2 -3
1
1 1
8
1 2 -1 4 9 8 -1 2
4
1 3
1 4
2 5
7 8
3
0 0 0
1
1 3

-1 1
3 2
6 4
14 4
2 1
0 3