Дана матрица \(a\) размера \(n \times m\), каждая ячейка которой содержит неотрицательное целое число. Число, находящееся на пересечении \(i\)-й строки и \(j\)-го столбца матрицы, называется \(a_{i,j}\).
Определим \(f(i)\) и \(g(j)\) как XOR всех чисел в \(i\)-й строке и \(j\)-м столбце соответственно. За одну операцию вы можете либо:
- Выбрать любую строку \(i\), затем присвоить \(a_{i,j} := g(j)\) для каждого \(1 \le j \le m\); либо
- Выбрать любой столбец \(j\), затем присвоить \(a_{i,j} := f(i)\) для каждого \(1 \le i \le n\).
Пример применения операции к столбцу \(2\) матрицы. В этом примере, когда мы применяем операцию к столбцу \(2\), все элементы в этом столбце изменяются следующим образом:
- \(a_{1,2} := f(1) = a_{1,1} \oplus a_{1,2} \oplus a_{1,3} \oplus a_{1,4} = 1 \oplus 1 \oplus 1 \oplus 1 = 0\)
- \(a_{2,2} := f(2) = a_{2,1} \oplus a_{2,2} \oplus a_{2,3} \oplus a_{2,4} = 2 \oplus 3 \oplus 5 \oplus 7 = 3\)
- \(a_{3,2} := f(3) = a_{3,1} \oplus a_{3,2} \oplus a_{3,3} \oplus a_{3,4} = 2 \oplus 0 \oplus 3 \oplus 0 = 1\)
- \(a_{4,2} := f(4) = a_{4,1} \oplus a_{4,2} \oplus a_{4,3} \oplus a_{4,4} = 10 \oplus 11 \oplus 12 \oplus 16 = 29\)
Вы можете применять операции любое количество раз. Затем мы вычислим \(\textit{красоту}\) финальной матрицы, суммируя абсолютные разности между всеми парами её соседних ячеек.
Более формально, \(\textit{красота}(a) = \sum|a_{x,y} - a_{r,c}|\) для всех ячеек \((x, y)\) и \((r, c)\), если они соседние. Две ячейки считаются соседними, если они имеют общую сторону.
Найдите минимальную \(\textit{красоту}\) среди всех достижимых матриц.
Выходные данные
Для каждого набора входных данных выведите одно целое число \(b\) — наименьшая возможная \(\textit{красота}\) матрицы.
Примечание
Обозначим \(r(i)\) как операцию первого типа, примененную к \(i\)-й строке, и \(c(j)\) как операцию второго типа, примененную к \(j\)-му столбцу.
В первом наборе входных данных вы можете применить операцию \(c(1)\), которая присвоит \(a_{1,1} := 1 \oplus 3 = 2\). Затем мы получим эту матрицу:
Во втором наборе входных данных вы можете применить операцию \(r(1)\), которая присвоит:
- \(a_{1,1} := g(1) = 0 \oplus 5 = 5\)
- \(a_{1,2} := g(2) = 1 \oplus 4 = 5\)
- \(a_{1,3} := g(3) = 0 \oplus 4 = 4\)
Финальная матрица после выполнения операции:
В третьем наборе входных данных лучший способ достичь минимальной \(\textit{красота}\) — применить три операции: \(c(3)\), \(r(2)\) и \(c(2)\). Финальная матрица:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
2 3
0 1 0
5 4 4
2 3
0 2 4
4 5 1
3 3
1 2 3
4 5 6
7 8 9
|
1
3
13
24
|