시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 0 0 0 0.000%

문제

Bobo has a matrix of size $n \times m$ filled with integers. It is guaranteed that all cells which contain the same value are $4$-side connected.

Let's define a jailing $J_x$ of a connected component with value $x$ as minimum-area rectangle (with sides parallel to the matrix sides) that covers all cells of the component.

For each jailing $B_x$, Jessica would like to find the value of

$$ s(B_x)=\sum_{B_y \in A \setminus \{x\}} f(B_x, B_y) \cdot y $$

where $A$ is the set of all integers in the matrix and

$$ f(B_x,B_y)=\begin{cases} 0 & \text{ the area of intersection of } B_x \text{ and } B_y \text{ is } 0 \\ 0 & B_x \text{ is completely inside } B_y \text{ or vice versa} \\ 1 & \text{Otherwise} \end{cases} $$

입력

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $m$ -- the size of the matrix.

The second line contains $n \cdot m$ integers $a_{1,1}, a_{1,2}, \ldots, a_{1, m}$, $a_{2,1}, a_{2,2}, \ldots, a_{2, m}$, $\ldots$, $a_{n, 1}, a_{n, 2}, \ldots, a_{n,m}$, where $a_{i,j}$ is the value in the $i$-th row and the $j$-th column.

출력

For each test case, output an integer denoting the value of $\sum_{x \in A} s(x) \oplus x$, where $\oplus$ denotes the exclusive-or (XOR) operator.

제한

  • $1 \leq n \cdot m \leq 10^6$
  • $1 \leq a_{i,j} \leq nm$
  • It is guaranteed that all cells which contain the same value are $4$-side connected.
  • It is guaranteed that the sum of $n \cdot m$ in all test cases does not exceed $10^7$.

예제 입력 1

4 2
4 8 4 4 4 2 2 2
2 7
12 12 12 13 8 9 14 12 12 7 4 10 11 5
3 5
13 13 3 3 14 2 2 1 1 11 2 2 1 5 7

예제 출력 1

20
93
56