AT_abc476_f [ABC476F] Chebyshev Cafe

$ N $ 行 $ N $ 列のグリッドで表される市街地があります。上から $ i $ 行目・左から $ j $ 列目のマスをマス $ (i,j) $ と表します。各マスには $ 1 $ つずつカフェがあります。 あなたはミーティングを企画しています。参加者のうち、マス $ (i, j) $ に住む人の人数は $ (A_i \times B_j) \bmod M $ です。 マス $ (s_r,\ s_c) $ に住む参加者 $ 1 $ 人がマス $ (t_r,\ t_c) $ にあるカフェに行くときにかかる交通費は $ \max(|s_r - t_r|,\ |s_c - t_c|) $ です。 参加者全員をマス $ (i, j) $ にあるカフェへと集めるときにかかる交通費の合計を $ f(i, j) $ とします。 各マス $ (i,j) $ に対する以下の値をすべてのマスについて求めたときの、それらの bitwise XOR として得られる値を出力してください。 - $ f(i,j) + (i-1)N + (j-1) $ bitwise XOR 演算とは 非負整数 $ A, B $ の bitwise XOR ( $ 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 $ の bitwise XOR は $ (\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 $ $ \dots $ $ A_N $ $ B_1 $ $ \dots $ $ B_N $

答えを出力せよ。

### Sample Explanation 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} $ となります。 ### 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 $ ) - 入力される値はすべて整数