#2409. 「THUPC 2017」小 L 的计算题 / Sum

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yanQval

题目描述

现有一个长度为 n (1 \le n\le 2\times 10^5) 的非负整数数组 \{a_i\} 。小 L 定义了一种神奇变换:

f_k=\sum_{i=1}^{n}{a_i}^k\pmod{ 998244353 }

小 L 计划用变换生成的序列 f 做一些有趣的事情,但是他并不擅长算乘法,所以来找你帮忙,希望你能帮他尽快计算出 f_1\sim f_n

输入格式

输入包含多组数据。

输入的第一行包含一个整数 T (1\le T\le 20) , 表示数据组数。

接下来 2T 行,每两行代表一组测试数据。

每组数据的第一行包含一个整数 n ,表示数组 \{a_i\} 的长度。接下来一行 n 个整数,描述数组 \{a_i\}

保证输入的 a_i 满足 0\le a_i\le 10^9 。在一个测试文件中,保证有 \sum n\le 4\times 10^5

输出格式

我们不想让你输出过多的数。因此,令 \text{ans}=f_1\oplus f_2\oplus\dots\oplus f_n ,其中 \oplus 表示异或操作,在 C++ / Java / Python 中,它可以表示为 ^

对每组数据,你需要输出一行一个整数,表示 \text{ans}

样例

样例输入

2
3
2 3 3
5
1 2 3 4 5

样例输出

32
4675