题目描述

小Q学习位运算时发现了异或的秘密。

小Q是一个热爱学习的人，他经常去维基百科学习计算机科学。

就在刚才，小Q认真地学习了一系列位运算符，其中按位异或的 运算符 $\oplus$ 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即 $i \oplus j = j \oplus i$。

他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为 $0$，否则为 $1$，例如 $1(01) \oplus 2(10) = 3(11)$。 他还发现，按位异或可以理解成数字的每个二进制位进行了不进位的加法，例如 $3(11) \oplus 3(11) = 0(00)$。

于是他想到了两个关于异或的问题，这两个问题基于一个给定的非负整数序列$A_1, A_2, \dots, A_n$，其中 $n$ 是该序列的长度。

第一个问题是，如果用 $f_{i,j}$ 表示 $A_i \oplus A_{i+1} \oplus \dots \oplus A_j$，则任意的 $1\le i\le j\le n$ 的 $f_{i,j}$ 相加是多少。

第二个问题是，如果用 $g_{i,j}$ 表示 $A_i + A_{i+1} + \dots + A_j$，则任意的 $1\le i\le j\le n$ 的 $g_{i,j}$ 异或在一起是多少。

比如说，对于序列 ${1,2}$，所有的 $f$ 是 {$1, 2, 1 \oplus 2$}，加起来是 $6$；所有的 $g$ 是 {$1, 2, 1 + 2$}，异或起来是 $0$。

他觉得这两个问题都非常的有趣，所以他找到了你，希望你能快速解决这两个问题，其中第一个问题的答案可能很大，你只需要输出它对 $998244353$（一个质数）取模的值即可。

输入格式

第一行一个正整数 $n$，表示序列的长度。

第二行 $n$ 个非负整数 $A_1, A_2, \dots, A_n$，表示这个序列。

输出格式

两个整数，表示两个问题的答案，空格隔开，其中第一个问题的答案要对 $998244353$（一个质数）取模。

2
1 2

6 0

数据范围

对于 $100\%$ 的数据满足 $n\le 10^5$,$A_i\le 10^6$。