Problem Description

给定一个序列 $a[1],a[2],a[3]......a[n]$，你的任务是计算其连续子段的最大和。例如，给定 $(6,-1,5,4,-7)$，该序列中的最大和为 $6+(-1)+5+4=14$。

Input

第一行输入包含一个整数 $T(1≤T≤10000)$ 表示后续测试数据的组数。接下来 $T$ 行每行由一个整数 $N(1≤N≤100000)$ 开始，接下来 $N$ 个整数 $A_i(-1000≤A_i≤1000)$。

每个测试点的 $\sum N≤2×10^5$。

Output

对每组测试数据，输出最大的子段和、该子段的起点位置和终点位置。

如果存在多个子段，请输出长度最短的，如果仍有多个，请输出其中起点位置最靠前的。

Sample

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

14 1 4
7 6 6