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

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

小C还知道，这些英灵暗自商量了一个整数 $m$ （$1\le m\le 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\mathrm{xor}88\mathrm{xor}79\mathrm{xor}60\mathrm{xor}40\mathrm{xor}20=94$。

样例二

input

6
5 19 7 10 16 7

output

85

样例三

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

样例四

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

限制与约定

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

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载