1738: 怎么可能会后悔
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：13
题目描述
本题是D题的加强版本，题意一样，只有数据不同。
奇迹和魔法都是存在的，选择成为魔法少女就不能后悔了（怎么可能会后悔）。
现在小圆面前有n个魔法值，这n个魔法值组合成为一个集合，现在需要得到这个集合的所有子序列(每个元素都可选可不选，最后得到的集合)的异或的和，来触发奇迹(解释：对于每个子序列来说，子序列中所有的值进行异或得到该子序列的魔法值，，，对于不同的子序列，将所有子序列的魔法值相加得到最终答案)。
例如{1，2，2}的子序列是{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3} ，至于空集合由于元素异或值是0所以不影响结果，无论是否算上空集合。
奇迹和魔法都是存在的，选择成为魔法少女就不能后悔了（怎么可能会后悔）。
现在小圆面前有n个魔法值，这n个魔法值组合成为一个集合，现在需要得到这个集合的所有子序列(每个元素都可选可不选，最后得到的集合)的异或的和，来触发奇迹(解释：对于每个子序列来说，子序列中所有的值进行异或得到该子序列的魔法值，，，对于不同的子序列，将所有子序列的魔法值相加得到最终答案)。
例如{1，2，2}的子序列是{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3} ，至于空集合由于元素异或值是0所以不影响结果，无论是否算上空集合。
输入
第一行一个整数n
第二行n个整数,s1,s2,...,si,....sn代表小圆面临的n个魔法值。
数据范围 1<= n <= 1e5,1 <= si <= 1e9 .
第二行n个整数,s1,s2,...,si,....sn代表小圆面临的n个魔法值。
数据范围 1<= n <= 1e5,1 <= si <= 1e9 .
输出
一个整数，集合所有子序列的异或的和模以998244353
样例输入 复制
3
1 2 3样例输出 复制
12提示
样例解释
样例子序列有{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}，
每个子序列的异或值分别为1，2，3，3，2，1，0，所以答案就是1 + 2 + 3 + 3 + 2 + 1 = 12 .
样例子序列有{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}，
每个子序列的异或值分别为1，2，3，3，2，1，0，所以答案就是1 + 2 + 3 + 3 + 2 + 1 = 12 .