题目背景

作为新人训练家,$red$除了在冒险路上收集道馆徽章之外,大木博士还交给他一个任务—收集宝可梦图鉴。然而,冒险家$red$却没有足够的钱去购买精灵球,为了尽快攒够购买精灵球的钱,$red$铤而走险,决定去和赌徒玩一场位运算游戏。具体来说赌徒会给你一个长度为$n (1\le n \le 10^5)$的数组,你需要从or 和 and 两个位运算操作里选择一个去计算所有区间的区间or(按位或)之和与区间and(按位与)之和。现在$red$想知道选择哪一个操作得到的结果最大,但是$red$自己太笨了,所以他把问题交给了你,你需要分别计算出这两种操作下的结果。

形式化来说,你需要分别计算出$\sum_{i=1,j=i}^{n,n} a_i \& a _{i+1}...\&a_j$ 和 $\sum_{i=1,j=i}^{n,n} a_i|a_{i+1}...|a_j$

由于答案可能很大,需要你输出答案对998244353取模后的结果

【名词解释】

$\hspace{22pt}$$\operatorname{or}$：即按位或(Bitwise OR),指对两个整数的二进制表示按位进行或运算。

$\hspace{15pt}$$\operatorname{and}$：即按位与（Bitwise AND），指对两个整数的二进制表示按位进行与运算。

题目描述

如题目背景里所说,你需要分别计算出$\sum_{i=1,j=i}^{n,n} a_i \& a _{i+1}...\&a_j$ 和 $\sum_{i=1,j=i}^{n,n} a_i|a_{i+1}...|a_j$

输入格式

第一行输入一个数$n(1\le n \le 10^5)$,表示数组的长度.

第二行输入$n$个整数$a_1,a_2...,a_n(0\le a_i \le 10^9)$,表示数组中的元素。

输出格式

输入两个结果对998244353取模后的结果第一个数表示所有区间$and$之和第二个数表示所有区间$or$之和,用空格隔开。

输入输出样例

输入 #1

2
9 7

输出 #1

17 31

解释 #1

9的二进制为:1001

7的二进制为:0111

所有区间[1,1] [1,2] [2,2]

9&7=1 9|7=15

所有区间的区间与结果为 9+1+7=17

所有区间的区间或结果为 9+15+7=31