题目描述

有一个用 $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)$，求出下面的值，并输出所有格子对应值的按位异或。

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

按位异或运算是什么？

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

• 把 $A \oplus B$ 写成二进制时，第 $2^k$ 位（$k \geq 0$）上的数字，在 $A$ 与 $B$ 的二进制表示中第 $2^k$ 位恰好有一个是 $1$ 时为 $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$ 的顺序。

输入格式

输入按以下格式从标准输入读入：

• $N$ $M$
• $A_1$ $A_2$ $\dots$ $A_N$
• $B_1$ $B_2$ $\dots$ $B_N$

输出格式

输出答案。

4 19
2 3 1 1
3 4 4 10

467

每个格子中住着的参加者人数如下：$\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}$。

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

数据范围

• $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$）

• 所有输入值均为整数。

• 来源：AtCoder ABC 476 F

子任务设置

• 子任务 1（30 分）：$N \le 100$。
• 子任务 2（30 分）：$N \le 800$。
• 子任务 3（40 分）：无特殊限制。