D. Sum of XOR Functions

You are given an array $a$ of length $n$ consisting of non-negative integers.

You have to calculate the value of $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$, where $f(l, r)$ is $a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r$ (the character $\oplus$ denotes bitwise XOR).

Since the answer can be very large, print it modulo $998244353$.

Input

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9)$.

Output

Print the one integer — the value of $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$, taken modulo $998244353$.

Examples

Input

3
1 3 2

Output

Input

4
39 68 31 80

Output

Input

7
313539461 779847196 221612534 488613315 633203958 394620685 761188160

Output

257421502

Note

In the first example, the answer is equal to $f(1, 1) + 2 \cdot f(1, 2) + 3 \cdot f(1, 3) + f(2, 2) + 2 \cdot f(2, 3) + f(3, 3) = $ $= 1 + 2 \cdot 2 + 3 \cdot 0 + 3 + 2 \cdot 1 + 2 = 12$.

解题思路

　　如果涉及到位运算的话一般都是按位来考虑，并且每一位的计算是相互独立的。对于 $f(l,r) \cdot (r-l+1)$，我们把 $f(l,r)$ 看成是二进制转十进制的形式，例如有 $26 = (11010)_2 = 2^4 + 2^3 + 2^1$。由于 $a_i$ 的最大取值是 ${10}^9$，因此在二进制下最多有 $30$ 位，在按位的考虑的思想下，$\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} f(l, r) \cdot (r - l + 1)$ 的结果可以看成是 $2^0 \cdot x_0 + 2^1 \cdot x_1 + \cdots + 2^{29} \cdot x_{29}$ 的形式，其中 $x_k$ 表示考虑每个 $a_i$ 的第 $k$ 位时 $\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} f_k(l, r) \cdot (r - l + 1)$ 的结果，有 $f_k(l,r) = a_{l,k} \oplus a_{l+1,k} \oplus \dots \oplus a_{r-1,k} \oplus a_{r,k}$，$a_{l,k}$ 表示 $a_{l}$ 在二进制下第 $k$ 位的数值。

　　当我们考虑按位计算是，本质上是处理由 $a_{1,k}, a_{2,k}, \ldots, a_{n,k}$ 构成的 $01$ 串，因此 $f_k(l,r)$ 的值不是 $0$ 就是 $1$，而只有当 $f_k(l,r) = 1$ 时才有意义。为此我们应该统计所有 $f_k(l,r) = 1$ 的连续子串的长度总和。我们按右端点来对所有连续子串进行分类，当其右端点 $r$ 固定后，我们要找到所有满足 $f_k(l,r) = 1$ 的 $l$，其中 $l \in [1,r]$。为了方便这里定义前缀异或和 $s_i = a_{1,k} \oplus a_{2,k} \oplus \cdots \oplus a_{i,k}$，因此就等价于找到所有满足 $s_r \oplus s_l = 1, \, l \in [0,r-1]$ 的 $l$，然后再累加这些 $l$ 到 $r$ 的长度，也就是子串的长度。为此可以开个两个哈希表 $c_{0/1}$ 和 $g_{0/1}$，分别维护 $[0,r-1]$ 中 $s_i = 0/1$ 的下标数量，以及对应的下标的和。因此当 $r$ 固定后，满足 $f_k(l,r)=1$ 的子串长度总和就是 $r \cdot c_{s_r \oplus 1} - g_{s_r \oplus 1}$，对总的答案的贡献就是 $2^k \cdot (r \cdot c_{s_r \oplus 1} - g_{s_r \oplus 1})$。

　　 AC 代码如下，时间复杂度为 $O(n \log{A})$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 3e5 + 10, mod = 998244353;
 7 
 8 int a[N];
 9 
10 int main() {
11     int n;
12     scanf("%d", &n);
13     for (int i = 1; i <= n; i++) {
14         scanf("%d", a + i);
15     }
16     int ret = 0;
17     for (int k = 0; k <= 29; k++) {
18         int sum = 0, c[2] = {0}, s[2] = {0};
19         for (int i = 1; i <= n; i++) {
20             c[sum]++, s[sum] = (s[sum] + i - 1) % mod;
21             int x = a[i] >> k & 1;
22             sum ^= x;
23             ret = (ret + (1ll * c[sum ^ 1] * i % mod - s[sum ^ 1] + mod) % mod * (1 << k)) % mod;
24         }
25     }
26     printf("%d\n", ret);
27     
28     return 0;
29 }