该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

FFT太有趣啦

题目背景

Y同学在学习了快速傅里叶变换（FFT）之后，对“卷积”这个概念产生了浓厚的兴趣。他发现，许多看似无关的问题都可以转化为卷积的形式来解决。

普通的卷积通常与多项式乘法相关，其形式为 $h_k = \sum_{i+j=k} f_i g_j$。Y同学觉得这还不够有趣，他想：如果把下标的运算规则从加法换成其他二元运算会怎么样呢？

受此启发，他"定义"了一种全新的卷积——最大公约数（GCD）卷积，并想请你这位编程糕手帮忙实现它。

题目描述

定义两个长度为 $N$ 的序列 $f = \{f_1, f_2, \dots, f_N\}$ 和 $g = \{g_1, g_2, \dots, g_N\}$ 的 GCD 卷积 为一个新的长度为 $N$ 的序列 $h = \{h_1, h_2, \dots, h_N\}$。

其中 $h_k$ 的计算方式如下：

其中 $\gcd(i, j)$ 表示 $i$ 和 $j$ 的最大公约数。

现在，Y同学给定了序列 $f$ 和 $g$，你需要计算出序列 $h$。由于序列 $h$ 可能很长，你只需要输出所有 $h_k$（$1 \le k \le N$）对 $998244353$ 取模后的异或和。

输入格式

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

第二行，$N$ 个非负整数，表示序列 $f$ 的元素 $f_1, f_2, \dots, f_N$。

第三行，$N$ 个非负整数，表示序列 $g$ 的元素 $g_1, g_2, \dots, g_N$。

输出格式

输出一个整数，表示 $\left( \bigoplus_{k=1}^{N} (h_k \pmod{998244353}) \right)$ 的值。

其中 $\oplus$ 表示按位异或（XOR）运算。

样例

样例 1

样例输入 1

3
5 1 4
2 3 3

样例输出 1

78

样例解释 1

根据定义，我们计算 $h_1, h_2, h_3$：

• $h_1 = \sum_{\gcd(i,j)=1} f_i g_j = f_1 g_1 + f_1 g_2 + f_1 g_3 + f_2 g_1 + f_3 g_1 + f_2 g_3 + f_3 g_2 = 5 \cdot 2 + 5 \cdot 3 + 5 \cdot 3 + 1 \cdot 2 + 4 \cdot 2 + 1 \cdot 3 + 4 \cdot 3 = 10+15+15+2+8+3+12 = 65$。
• $h_2 = \sum_{\gcd(i,j)=2} f_i g_j = f_2 g_2 = 1 \cdot 3 = 3$。
• $h_3 = \sum_{\gcd(i,j)=3} f_i g_j = f_3 g_3 = 4 \cdot 3 = 12$。

所有计算均在模 $998244353$ 意义下进行，由于数值较小，取模后不变。 最终的异或和为 $65 \oplus 3 \oplus 12 = 78$。

样例 2

样例输入 2

4
7 1 8 0
6 2 9 1

样例输出 2

158

样例解释 2

计算可得：

• $h_1 = 213$
• $h_2 = 3$
• $h_3 = 72$
• $h_4 = 0$

异或和为 $213 \oplus 3 \oplus 72 \oplus 0 = 158$。

数据范围与约定

• 对于20%的测试点: $1 \le N \le 2000$。
• 对于100%的测试点: 无特殊限制。 对于所有测试数据，保证：
• $1 \le N \le 4 \times 10^5$。
• $0 \le f_i, g_i < 998244353$。