Problem Statement

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$.

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.

Input

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

N M
A_1 \dots A_N
B_1 \dots B_N

Output

Output the answer.