다이아몬드 채굴 이익

강에서 다이아몬드를 캐는 사업을 한다. 정부는 채굴기를 강에 한 번만 넣도록 허가하고, 허가 기간이 끝나기 전에 채굴기를 반드시 빼야 한다. 채굴기를 넣은 뒤에는 원하는 날 아무 때나 뺄 수 있다.

채굴기는 다이아몬드를 드릴 날로 쓰기 때문에, 돌리려면 다이아몬드가 든다. 회사에는 성능이 좋은 탐지기가 있어서 허가 기간의 첫날부터 마지막 날까지 하루하루 얻거나 잃을 다이아몬드 개수를 미리 알려준다.

회사가 다이아몬드를 가장 많이 버는 기간을 찾는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. ($1 \le N \le 2000$)

다음 $N$개 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스는 수 $M + 1$개로 이루어진다. 첫 번째 수는 정부가 허가한 전체 일수 $M$이다. ($1 \le M \le 500$) 이어지는 $M$개의 수는 각 날에 얻거나 잃을 다이아몬드 개수의 예측값이고, 모두 $-100$ 이상 $100$ 이하의 정수이다.

테스트 케이스마다 한 줄씩, 모두 $N$개 줄을 출력한다. 각 줄에는 시작한 날, 끝낸 날, 최대 이익을 순서대로 출력한다. 입력의 첫날이 1번 날이고 마지막 날이 $M$번 날이다.

이익이 양수인 기간이 하나도 없으면 0 0 0을 출력한다. 이익이 같은 기간이 여럿이면 더 짧은 기간을 고르고, 길이까지 같으면 더 먼저 시작하는 기간을 고른다.