XOR Groups

Time limit2sMemory limit512 MB

Summary

Erase cells from an N by M grid in increasing value order and after each erasure report the maximum sum of XOR values of the connected groups.

Level: Medium6 of 10
Topics: Union-find, Simulation, Bit manipulation
Solved: No attempts yet

Problem

An $N \times M$ grid holds one number in every cell, and all of the numbers are different. Among the cells still on the board, cells that touch up, down, left, or right belong to the same XOR group, and the value of a group is the XOR of every number in it. A missing cell in between breaks the link, so one board can hold several XOR groups. The score of the board is the sum of the values of all XOR groups.

Every cell is on the board at the start. You then erase cells one at a time, always the cell holding the smallest number that is left. Each erasure changes the groups and the score. Print the largest score over the starting board before any erasure together with every board that follows an erasure.

Input

The first line has $N$ and $M$ . ( $1 \le N, M \le 1{,}000$ )

Each of the next $N$ lines has the $M$ numbers of row $i$ of the grid, separated by spaces. Every number is an integer between $0$ and $1{,}000{,}000$ , and all numbers in the grid are different.

Output

Print the largest score on the first line.

Examples8

Example 1
Input
```
3 4
9 1 15 16
3 4 10 6
2 5 7 11
```
Expected output
```
42
```
Example 2
Input
```
1 1
0
```
Expected output
```
0
```
Example 3
Input
```
1 1
1000000
```
Expected output
```
1000000
```
Example 4
Input
```
1 3
6 0 5
```
Expected output
```
11
```
Example 5
Input
```
1 2
1 2
```
Expected output
```
3
```
Example 6
Input
```
2 2
1 2
3 4
```
Expected output
```
7
```
Example 7
Input
```
5 1
5
3
1
2
4
```
Expected output
```
12
```
Example 8
Input
```
3 3
8 4 2
16 1 32
64 128 256
```
Expected output
```
511
```