XOR 그룹

시간 제한2초메모리 제한512 MB

요약

N x M 격자에서 값이 작은 칸부터 차례로 지우고, 각 단계에서 남은 칸들이 이루는 연결 그룹들의 XOR 값 합 중 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 유니온 파인드, 시뮬레이션, 비트 연산
정답자: 아직 제출이 없습니다

문제

$N \times M$ 격자의 모든 칸에 서로 다른 수가 하나씩 들어 있다. 격자에 남아 있는 칸 중에서 위, 아래, 왼쪽, 오른쪽으로 맞닿은 칸끼리 하나의 XOR 그룹을 이루고, 그룹의 값은 그 그룹에 속한 수를 모두 XOR한 값이다. 중간 칸이 비어 있으면 연결이 끊기므로 한 격자에 XOR 그룹이 여러 개 생길 수 있다. 격자의 점수는 모든 XOR 그룹의 값을 더한 수다.

처음에는 모든 칸이 남아 있다. 여기서 남은 수 중 가장 작은 수가 적힌 칸을 하나씩 지워 나간다. 한 칸을 지울 때마다 그룹의 구성이 바뀌고 점수도 달라진다. 한 칸도 지우지 않은 처음 격자와 한 칸씩 지운 뒤의 모든 격자를 통틀어, 점수의 최댓값을 구하여라.

입력

첫째 줄에 $N$ 과 $M$ 이 주어진다. ( $1 \le N, M \le 1{,}000$ )

다음 $N$ 개 줄에는 격자의 $i$ 번째 줄에 있는 수 $M$ 개가 공백으로 구분되어 주어진다. 각 수는 $0$ 이상 $1{,}000{,}000$ 이하의 정수이고, 격자에 있는 수는 모두 다르다.

출력

첫째 줄에 점수의 최댓값을 출력한다.

예제8

예제 1
입력
```
3 4
9 1 15 16
3 4 10 6
2 5 7 11
```
예상 출력
```
42
```
예제 2
입력
```
1 1
0
```
예상 출력
```
0
```
예제 3
입력
```
1 1
1000000
```
예상 출력
```
1000000
```
예제 4
입력
```
1 3
6 0 5
```
예상 출력
```
11
```
예제 5
입력
```
1 2
1 2
```
예상 출력
```
3
```
예제 6
입력
```
2 2
1 2
3 4
```
예상 출력
```
7
```
예제 7
입력
```
5 1
5
3
1
2
4
```
예상 출력
```
12
```
예제 8
입력
```
3 3
8 4 2
16 1 32
64 128 256
```
예상 출력
```
511
```