SPOJ Brasil

Pouca gente sabe, mas foi no Antigo Egito que surgiram os primeiros bancos, de uma forma muito semelhante ao que conhecemos hoje. O principal banco era do faraó, que decidia, de tempos em tempos, tomar para o Estado o conteúdo de algumas contas. Isso ocorria da seguinte forma. Dado N, o número de correntistas do Banco do Faraó (era esse o nome do banco), cada conta podia ter uma quantia em menés (moeda do Antigo Egito) que podia ser, inclusive, negativa (indicando que a pessoa devia aquela quantia ao banco), ou seja, o estado de cada conta era um inteiro a_i. O objetivo do faraó era fazer diversas consultas nas contas de seus súditos. Dado um intervalo [A,B] (correspondente as contas a_A, a_A+1, ... , a_B-1, a_B) o faraó desejava encontrar um subintervalo de soma máxima, ou seja, cujo sequestro pelo Estado renderia ao Faraó a maior quantia de dinheiro. Isso era explicado aos correntistas como sendo uma oferenda a Amon-Ahcid, o Deus egípcio do dinheiro. Fazendo regularmente tais oferendas o deus ficava satisfeito e permitia que o sistema econômico funcionasse perfeitamente. Isso durou surpreendentemente mais de 500 anos, até que num desses sequestros os correntistas se rebelaram, tomaram o palácio e mataram o faraó. O banco foi saqueado e o sistema ruiu. Só se ouviu falar de bancos novamente centenas de anos depois.
Sua tarefa é dado um registro de contas e uma série de consultas, determinar para cada consulta um intervalo de soma máxima.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira linha de cada instância contém um inteiro N, indicando o número de contas no Banco do Faraó, onde 1 ≤ N ≤ 100 000. A segunda linha de cada instância contém N inteiros, entre -10 000 até 10 000, indicando os saldos nas contas dos correntistas. A terceira linha contém um inteiro Q, onde 1 ≤ Q ≤ 100000, indicando o número de consultas que serão feitas. Cada uma das Q linhas seguintes contém dois inteiros A e B, onde 1 ≤ A,B ≤ N, indicando o intervalo que deve ser consultado.

Saída

Para cada instância seu programa deve produzir Q linhas na saída, sendo uma para cada consulta. Cada uma dessas linhas deve conter dois inteiros: o primeiro representa a soma do intervalo com maior soma, e o segundo, o número de elementos desse intervalo. Caso haja mais de um intervalo com maior soma, imprima o número de elementos naquele com maior número de elementos.

Exemplo

Entrada:
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

Saída:

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