AT_abc476_f.Chebyshev Cafe

There is a city represented by a grid with $N$ rows and $N$ columns. The cell at the $i$-th row from the top and $j$-th column from the left is denoted as cell $(i,j)$. Each cell has one cafe.

You are planning a meeting. Among the participants, the number of people living in cell $(i, j)$ is $(A_i \times B_j) \bmod M$. The travel cost for one participant living in cell $(s_r,\ s_c)$ to go to the cafe at cell $(t_r,\ t_c)$ is $\max(|s_r - t_r|,\ |s_c - t_c|)$.

Let $f(i, j)$ be the total travel cost incurred when gathering all the participants at the cafe at cell $(i, j)$.

For each cell $(i,j)$, find the following value, and output the bitwise XOR of these values over all cells.

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

What is the bitwise XOR operation?

The bitwise XOR of non-negative integers $A$ and $B$ (denoted $A \oplus B$) is defined as follows.

• The digit in the $2^k$'s place ($k \geq 0$) of $A \oplus B$ written in binary is $1$ if exactly one of the digits in the $2^k$'s place of $A$ and $B$ written in binary is $1$, and $0$ otherwise.

For example, $3 \oplus 5 = 6$ (in binary: $011_{(2)} \oplus 101_{(2)} = 110_{(2)}$).
More generally, the bitwise XOR of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, p_3, \dots, p_k$.

有一座由 $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)$，计算如下值，并输出所有格子对应值的**按位异或（bitwise XOR）**结果：

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

什么是按位异或（bitwise XOR）运算？

非负整数 $A$ 与 $B$ 的按位异或（记作 $A \oplus B$）定义如下：

• 将 $A \oplus B$ 写成二进制后，其 $2^k$ 位（$k \geq 0$）上的数字为 $1$，当且仅当 $A$ 和 $B$ 的二进制表示中，该位上恰好有一个为 $1$；否则该位为 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011_{(2)} \oplus 101_{(2)} = 110_{(2)}$）。
更一般地，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位异或定义为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，且可以证明该结果与 $p_1, p_2, p_3, \dots, p_k$ 的顺序无关。

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $\dots$ $A_N$
$B_1$ $\dots$ $B_N$

输入从标准输入中按以下格式给出：

$N$ $M$
$A_1$ $\dots$ $A_N$
$B_1$ $\dots$ $B_N$

Output the answer.

输出答案。

Sample 1 Explanation:
The number of participants living in each cell is as follows: $\displaystyle \begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix}$.

For example, the value of $f(1,2)$ is obtained as the sum $176$ of the following $16$ values:

• The total amount $6 \times 1 = 6$ paid by the $6$ residents of cell $(1,1)$, each of whom pays a travel cost of $\max(|1 - 1|,\ |1 - 2|) = 1$
• The total amount $8 \times 0 = 0$ paid by the $8$ residents of cell $(1,2)$, each of whom pays a travel cost of $\max(|1 - 1|,\ |2 - 2|) = 0$
• The total amount $8 \times 1 = 8$ paid by the $8$ residents of cell $(1,3)$, each of whom pays a travel cost of $\max(|1 - 1|,\ |3 - 2|) = 1$
• The total amount $1 \times 2 = 2$ paid by the $1$ resident of cell $(1,4)$, each of whom pays a travel cost of $\max(|1 - 1|,\ |4 - 2|) = 2$
• $\vdots$
• The total amount $3 \times 3 = 9$ paid by the $3$ residents of cell $(4,1)$, each of whom pays a travel cost of $\max(|4 - 1|,\ |1 - 2|) = 3$
• The total amount $4 \times 3 = 12$ paid by the $4$ residents of cell $(4,2)$, each of whom pays a travel cost of $\max(|4 - 1|,\ |2 - 2|) = 3$
• The total amount $4 \times 3 = 12$ paid by the $4$ residents of cell $(4,3)$, each of whom pays a travel cost of $\max(|4 - 1|,\ |3 - 2|) = 3$
• The total amount $10 \times 3 = 30$ paid by the $10$ residents of cell $(4,4)$, each of whom pays a travel cost of $\max(|4 - 1|,\ |4 - 2|) = 3$

The value of $f(i,j)$ for each cell is as follows: $\displaystyle \begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix}$.

Constraints

• $1 \leq N \leq 1500$
• $2 \leq M \leq 2 \times 10^6$
• $1 \leq A_i \leq M-1$ ($1 \leq i \leq N$)
• $1 \leq B_j \leq M-1$ ($1 \leq j \leq N$)
• All input values are integers.

样例 1 解释：
每个格子中居住的参与者人数如下：$\displaystyle \begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix}$。

例如，$f(1,2)$ 的值为以下 $16$ 项之和，结果为 $176$：

• 格子 $(1,1)$ 中的 $6$ 名居民每人需支付交通费用 $\max(|1 - 1|,\ |1 - 2|) = 1$，共支付 $6 \times 1 = 6$；
• 格子 $(1,2)$ 中的 $8$ 名居民每人需支付交通费用 $\max(|1 - 1|,\ |2 - 2|) = 0$，共支付 $8 \times 0 = 0$；
• 格子 $(1,3)$ 中的 $8$ 名居民每人需支付交通费用 $\max(|1 - 1|,\ |3 - 2|) = 1$，共支付 $8 \times 1 = 8$；
• 格子 $(1,4)$ 中的 $1$ 名居民需支付交通费用 $\max(|1 - 1|,\ |4 - 2|) = 2$，共支付 $1 \times 2 = 2$；
• $\vdots$
• 格子 $(4,1)$ 中的 $3$ 名居民每人需支付交通费用 $\max(|4 - 1|,\ |1 - 2|) = 3$，共支付 $3 \times 3 = 9$；
• 格子 $(4,2)$ 中的 $4$ 名居民每人需支付交通费用 $\max(|4 - 1|,\ |2 - 2|) = 3$，共支付 $4 \times 3 = 12$；
• 格子 $(4,3)$ 中的 $4$ 名居民每人需支付交通费用 $\max(|4 - 1|,\ |3 - 2|) = 3$，共支付 $4 \times 3 = 12$；
• 格子 $(4,4)$ 中的 $10$ 名居民每人需支付交通费用 $\max(|4 - 1|,\ |4 - 2|) = 3$，共支付 $10 \times 3 = 30$。

每个格子对应的 $f(i,j)$ 值如下：$\displaystyle \begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix}$。

约束条件

• $1 \leq N \leq 1500$
• $2 \leq M \leq 2 \times 10^6$
• $1 \leq A_i \leq M-1$（$1 \leq i \leq N$）
• $1 \leq B_j \leq M-1$（$1 \leq j \leq N$）
• 所有输入值均为整数。