题目描述

有一个由 $N$ 行 $N$ 列的方格组成的城市街区。我们将从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子记为格子 $(i, j)$。每个格子内恰好有一家咖啡馆。

你正在筹划一次大型聚会。在所有参与者中，居住在格子 $(i, j)$ 的人数为 $(A_i \times B_j) \bmod M$。

一名居住在格子 $(s_r, s_c)$ 的参与者前往位于格子 $(t_r, t_c)$ 的咖啡馆时，所花费的交通费用为切比雪夫距离：

$$\max(|s_r - t_r|, |s_c - t_c|)$$

令 $f(i, j)$ 表示将所有参与者全部召集到位于格子 $(i, j)$ 的咖啡馆时所需的交通费总和。

请计算所有格子 $(i, j)$（$1 \le i, j \le N$）的以下数值的按位异或和（bitwise XOR sum）：

$$f(i, j) + (i - 1)N + (j - 1)$$

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$

输出格式

输出一个整数，表示所有格子的计算结果的按位异或和。

数据范围

• $1 \le N \le 1500$
• $2 \le M \le 2 \times 10^6$
• $1 \le A_i \le M - 1$ ($1 \le i \le N$)
• $1 \le B_j \le M - 1$ ($1 \le j \le N$)
• 所有输入的值均为整数。

样例

样例输入 1

4 19
2 3 1 1
3 4 4 10

样例输出 1

467

样例解释 1： 每个格子的居民人数为：

$$\begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix}$$

每个格子计算出的 $f(i, j)$ 如下：

$$\begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix}$$

对所有格子将 $f(i, j) + (i-1)N + (j-1)$ 进行异或后，最终答案为 $467$。

样例输入 2

1 100
5
12

样例输出 2

0

样例输入 3

6 37
12 5 29 1 18 31
22 17 8 14 36 3

样例输出 3

1566