你有一个长度为$n$的序列$a_1,a_2...a_n$。你可以进行无限次如下操作：选择一个$i\in [2,n-1]$，使$$a_{i-1}=a_{i-1}+a_i$$ $$a_{i+1}=a_{i+1}+a_i$$ $$a_i=-a_i$$
你需要最小化$$max_{i=1}^{n}|a_i|$$
输入格式
输入包含多组数据。
第一行一个正整数$T$表示数据组数。
对于每组数据。
第一行一个正整数$n$。
接下来一行$n$个数$a_1,a_2....a_n$。
输出格式
一共$T$行。
每行一个整数$ans$表示这组数据的答案。
样例一
input
3 3 5 -2 3 4 0 0 0 0 3 1 2 3
output
3 0 3
explanation
对于第一组数据： 对$i=2$进行操作后,$a_1=3$,$a_2=2$,$a_3=1$ 答案为$3$。 对于第二组数据： 不用操作。
样例二
input
3 4 -1 -2 -3 7 4 2 3 4 -8 5 -1 -1 6 -1 -1
output
5 7 4
样例三
见下发文件
限制与约定
本题共有25个测试点，每个测试点4分。
对于全部数据$T\leq 3$，$3\leq n\leq 3\times 10^5$，$|a_i|\leq 10^9$。
具体规模请见下表。
| 测试点编号 | $n$ | $|a_i|$ | 特殊限制 |
|---|---|---|---|
| $1$ | $=3$ | $\leq 1000$ | |
| $2$ | $\le 5$ | ||
| $3$ | |||
| $4$ | $\le 10$ | ||
| $5$ | |||
| $6$ | |||
| $7$ | |||
| $8$ | $\le 20$ | ||
| $9$ | |||
| $10$ | |||
| $11$ | $\le 100$ | $\leq 10^9$ | $a_i \geq 0$ |
| $12$ | |||
| $13$ | |||
| $14$ | |||
| $15$ | $\le 500$ | ||
| $16$ | |||
| $17$ | $a_i \geq 0$ | ||
| $18$ | $\le 5000$ | ||
| $19$ | |||
| $20$ | |||
| $21$ | $\le 10^5$ | $a_i \geq 0$ | |
| $22$ | |||
| $23$ | |||
| $24$ | $\le 3\times 10^5$ | ||
| $25$ |
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$
