小C与 Saber 签订契约之后达成了共同争夺圣杯的目标，然而他们赢得圣杯的道路并没有这么轻易，小C需要与其他的英灵进行决战。

小C通过一些交易得知，其他的英灵已经结盟了。大决战那天，其他的英灵站成了一排，从左到右依次编号为 $1$ 到 $n$，血量依次为 $\mathrm{HP}_1, \dots, \mathrm{HP}_n$。

小C还知道，这些英灵暗自商量了一个整数 $m$ （$1 \leq m \leq n$）。Saber 和这些英灵之间的战斗将会持续 $n - m + 1$ 轮，其中第 $i$ 轮 Saber 将与编号为 $i, i + 1, \dots, i + m - 1$ 的英灵进行战斗，所需要耗费的魔力值为这些战斗的英灵中的血量的最大值。而由于人多力量大等因素，每轮战斗后英灵的血量不会有任何变化。

所有战斗结束后，Saber 耗费的总魔力值为每轮战斗耗费的魔力值之和。

小C和 Saber 必须挺过这 $n - m + 1$ 轮，之后这些英灵将一而再，再而三，三而竭，闻风丧胆，望风而逃，三十六计走为上。小C很焦虑，于是就来向您求救。小C想要知道所有可能的 $m = 1， 2， \dots, n$ 中，Saber 需要耗费的总魔力值分别是多少。

为了避免一些奇怪的原因，你只要输出所有情况的总魔力值模 $998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数）后，逐个按位异或起来的结果。（异或即 C/C++ 中的 ^，Pascal 中的 xor）

输入格式

第一行一个正整数 $n$。

第二行包含了 $n$ 个整数 $\mathrm{HP}_1, \dots, \mathrm{HP}_n$，表示这 $n$ 个英灵的血量。

注意：由于本题目的输入可能很大，请选择较为快速的读入方式。

输出格式

输出一行，一个整数，表示所有情况的总魔力值取模后逐个按位异或起来的结果。

样例一

input

6
19 4 20 19 1 10

output

94

explanation

$m= 1, 2, 3, 4, 5, 6$ 时候的对应的每个值分别是 $73,88,79,60,40,20$。

答案是 $73 \mathbin{\mathrm{xor}} 88 \mathbin{\mathrm{xor}} 79 \mathbin{\mathrm{xor}} 60 \mathbin{\mathrm{xor}} 40 \mathbin{\mathrm{xor}} 20= 94$。

样例二

input

6
5 19 7 10 16 7

output

85

样例三

见样例数据下载，限制与约定跟第 $5$ 个测试点相同。

样例四

见样例数据下载，限制与约定跟第 $8$ 个测试点相同。

限制与约定

对于所有数据，$0 \leq \mathrm{HP}_i \leq 10^9$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载