AT_abc476_f [ABC476F] Chebyshev Cafe

有一个城市被分为一个 $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)$ 的咖啡馆的代价和。 对于每一个格子，它的价值是下式。输出所有格子价值的异或和。 + $f(i,j)+(i-1)N+(j-1)$ :::info[异或和是什么] 对于非负整数 $A,B$，他们的异或和（写作 $A\oplus B$）定义如下： + 将 $A,B$ 改写成二进制，其异或和在二进制下的某一位为 $1$ 当且仅当 $A,B$ 在二进制下的这一位恰好有一个为 $1$。 举个例子，$3\oplus5=6(\text{二进制下：}011_{(2)}\oplus101_{(2)}=110_{(2)})$。 更一般的，非负整数 $p_1,p_2,p_3\ldots,p_k$ 的异或和定义为 $(\ldots((p_1\oplus p_2)\oplus p_3)\oplus\ldots\oplus p_k)$。易证 $p_1,p_2,p_3\cdots,p_k$ 的顺序不影响最终结果。 :::

输入由标准输入给出，形式如下： $ N\quad M\\ A_1\quad\ldots\quad A_N\\ B_1\quad\ldots\quad B_N $

输出答案。

### 数据范围 + $1\le N\le1500\\$ + $2\le M\le2\times10^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 解释 每个格子里的参与者数量如下：$ \displaystyle \begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix} $。 举个例子，$f(1,2)=176$，由 $16$ 个数加和而来： + 格子 $(1,1)$ 中的 $6$ 个人总共产生了 $6\times1=6$ 的代价，其中每个人赶路产生代价 $\max(|1-1|,\ |1-2|)=1$。 + 格子 $(1,2)$ 中的 $8$ 个人总共产生了 $8\times0=0$ 的代价，其中每个人赶路产生代价 $\max(|1-1|,\ |2-2|)=0$。 + 格子 $(1,3)$ 中的 $8$ 个人总共产生了 $8\times1=8$ 的代价，其中每个人赶路产生代价 $\max(|1-1|,\ |3-2|)=1$。 + 格子 $(1,4)$ 中的 $1$ 个人总共产生了 $1\times2=2$ 的代价，其中每个人赶路产生代价 $\max(|1-1|,\ |4-2|)=2$。 + $\vdots$ + 格子 $(4,1)$ 中的 $3$ 个人总共产生了 $3\times3=9$ 的代价，其中每个人赶路产生代价 $\max(|4-1|,\ |1-2|)=3$。 + 格子 $(4,2)$ 中的 $4$ 个人总共产生了 $4\times3=12$ 的代价，其中每个人赶路产生代价 $\max(|4-1|,\ |2-2|)=3$。 + 格子 $(4,3)$ 中的 $4$ 个人总共产生了 $4\times3=12$ 的代价，其中每个人赶路产生代价 $\max(|4-1|,\ |3-2|)=3$。 + 格子 $(4,4)$ 中的 $10$ 个人总共产生了 $10\times3=30$ 的代价，其中每个人赶路产生代价 $\max(|4-1|,\ |4-2|)=3$。 每一个格子的 $ f(i,j) $ 如下：$ \displaystyle \begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix} $ .