题目描述

给出一个长度为 $n$ 的序列 $a$，定义一个区间 $[l,r]$ 的权值为 $\max_{l\le L\le R\le r}|\sum_{i=L}^Ra_i|$。

对于 $k=1,2,3,\dots,n$，求所有长度为 $k$ 的区间权值和。

输入格式

本题有多组测试数据，第一行输入一个正整数 $T$，代表数据组数。

对于每组数据，第一行输入一个正整数 $n$。

第二行输入 $n$ 个整数，代表序列 $a$。

输出格式

为了避免输出量过大，设长度为 $k$ 的区间权值和为 $ans_k$，对于每组测试数据，你只需要输出：

（其中 $\oplus$ 表示按位异或运算）

正解做法不依赖于该输出方式。

5
3
1 -1 2
7
1 -2 -3 4 5 -6 -7
7
-1 2 3 -4 -5 6 7
4
1 1 2 3
5
1 4 -5 -2 6

1
31
31
4
11

提示

【样例解释】

样例中五组数据的 $ans$ 分别为：

• $\{4,3,2\}$
• $\{28,39,41,36,31,22,13\}$
• $\{28,39,41,36,31,22,13\}$
• $\{7,10,10,7\}$
• $\{18,23,19,14,7\}$

其中，对于第一组数据，各个区间的权值分别如下：

• $[1,1]:1$
• $[2,2]:1$
• $[3,3]:2$
• $[1,2]:1$
• $[2,3]:2$
• $[1,3]:2$

其中，长度为 $1$ 的区间有 $[1,1],[2,2],[3,3]$，权值和为 $4$；长度为 $2$ 的区间有 $[1,2],[2,3]$，权值和为 $3$；长度为 $3$ 的区间有 $[1,3]$，权值和为 $2$。

【数据范围】

对于所有数据，保证：

• $1\le T\le10^4$
• $1\le n,\sum n\le10^6$
• $-10^6\le a_i\le10^6$

本题采用打包测试，各测试包描述如下：