Вы бродите по исследовательской выставке на конференции 2050.
Выставка может быть представлена как неориентированный взвешенный граф в виде сетки размера \(n\times m\). Множество вершин графа это \(\{(i, j)|1\le i\le n, 1\le j\le m\}\). Две вершины \((i_1,j_1)\) и \((i_2, j_2)\) соединены ребром, если и только если \(|i_1-i_2|+|j_1-j_2|=1\).
На каждом ходу вы можете перейти из вершины в любую другую вершину, соединенную ребром с текущей. На каждом ребре расположено несколько экспонатов. Так как вы их все уже видели, то при проходе по ребру, на котором расположено \(x\) экспонатов, ваша скукота увеличивается на \(x\).
Для каждой стартовой вершины \((i, j)\) найдите ответ на следующий вопрос: чему равна минимальная возможная скукота, если вы начнете в вершине \((i, j)\) и вернетесь обратно, сделав ровно \(k\) ходов.
Вы можете использовать каждое ребро несколько раз, но и скукота будет увеличиваться это же количество раз. Вы не можете остаться в той же вершине вместо того, чтобы делать ход. Вы также не можете менять направление, когда идете по ребру. Прежде чем вернуться в стартовую вершину \((i, j)\) после \(k\) ходов, вы можете посещать (или нет) вершину \((i, j)\) любое количество раз.
Выходные данные
Выведите \(n\) строк по \(m\) чисел в каждой. \(j\)-е число в \(i\)-й строке, \(answer_{ij}\), должно равняться минимальной возможной скукоте, если вы начнете в вершине \((i, j)\) и вернетесь обратно, сделав ровно \(k\) ходов.
Если вы не можете вернуться обратно в вершину \((i, j)\), сделав ровно \(k\) ходов, \(answer_{ij}\) должен равняться \(-1\).
Примечание
В первом примере ответ всегда равен \(10\) вне зависимости от того, как вы пойдете.
Во втором примере \(answer_{21} = 10\), путь может быть таким: \((2,1) \to (1,1) \to (1,2) \to (2,2) \to (2,1)\), скукота равна \(4 + 1 + 2 + 3 = 10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 10
1 1
1 1
1 1
1 1 1
1 1 1
|
10 10 10
10 10 10
10 10 10
|
|
2
|
2 2 4
1
3
4 2
|
4 4
10 6
|
|
3
|
2 2 3
1
2
3 4
|
-1 -1
-1 -1
|