说明

一群小孩子在玩小石子游戏，游戏有两种玩法。

（1）路边玩法

有n堆石子堆放在路边，现要将石子有序地合并成一堆，规定每次只能移动相邻的两堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费（最小或最大）。

（2）操场玩法

一个圆形操场周围摆放着n堆石子，现要将石子有序地合并成一堆，规定每次只能移动相邻的两堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费（最小或最大）。

输入格式

第一行是一个整型数$m(m<100)$表示共有$m$组测试数据。

每组测试数据的第一行是一个整数$n(0<n<1000)$表示石子的堆数。

第2行为$n$个整数$a_i(0<a_i<1000)$，表示第$i$堆的石子数。

输出格式

对于每一组输入，输出4个数（路边玩法最小花费，路边玩法最大花费，操场玩法最小花费，操场玩法最大花费）。

每组的输出占一行。

样例

3
6
5 8 6 9 2 3
5
8 7 3 6 10 35
4
9 2 15 6

84 129 81 130
77 95 77 108
64 76 60 83

来源

《趣学算法》4.8节