AT_abc476_f [ABC476F] Chebyshev Cafe

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

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ \dots $ $ A_N $ $ B_1 $ $ \dots $ $ B_N $

Output the answer.

### Sample Explanation 1 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} $ . ### 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.