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.

4 19
2 3 1 1
3 4 4 10

467

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

6 67
1 6 9 2 3 1
1 10 3 7 2 2

1021

20 676767
60932 508200 22883 481150 426836 554098 276223 307959 133025 573906 17711 413230 274246 500277 524959 477728 546547 43099 324227 660187
552697 293978 246000 159233 213736 628198 394200 194076 618720 453035 615100 331522 669419 180856 530693 399531 223149 159334 102107 598633

764668547

• Source: AtCoder ABC 476 F