Вы дошли до последней миссии в очень старой и очень популярной стратегии Dune II: Battle For Arrakis. Карта этой миссии может быть представлена в виде прямоугольной матрицы размера \(n \times m\). Изначально, в клетке \((i, j)\) стоит \(a_{i, j}\) отрядов вашей армии.
Вы готовитесь к последней битве, поэтому вы хотите собрать всю вашу армию в ровно одну клетку на карте (то есть \(nm-1\) клетка должна содержать \(0\) отрядов, а оставшаяся клетка должна содержать всю армию).
Чтобы достичь этого, вы можете совершить несколько (возможно, ноль) ходов. За один ход можно выбрать ровно один отряд из некоторой клетки и отправить его в соседнюю по стороне клетку. То есть из клетки \((i, j)\) можно отправить отряд в клетки:
- \((i - 1, j)\);
- \((i, j - 1)\);
- \((i + 1, j)\);
- \((i, j + 1)\).
Разумеется, вы хотите собрать армию в ровно одной клетке как можно быстрее. Поэтому вы хотите узнать минимальное необходимое для этого число ходов.
Также, жизнь не стоит на месте, а ситуация на карте меняется. Всего есть \(q\) изменений, \(i\)-е изменение задается тремя целыми числами \(x, y, z\). Это изменение затрагивает армию в клетке \((x, y)\): после этого изменения количество отрядов в клетке \((x, y)\) становится \(z\) (то есть \(a_{x, y}\) заменяется на \(z\)).
Также вы хотите знать для каждого \(i\) минимальное количество ходов, необходимое для сбора всей армии в ровно одной клетке после применения первых \(i\) изменений к изначальной карте. Другими словами, карта после \(i\)-го изменения равна изначальной карте с первыми \(i\) изменениями, примененными к ней.
Выходные данные
Выведите \(q+1\) целое число \(r_0, r_1, r_2, \dots, r_n\), где \(r_0\) — это минимальное количество ходов, необходимые для сбора всей армии в ровно одной клетке, а \(r_i\) для каждого \(i\) от \(1\) до \(q\) — минимальное количество ходов, необходимые для сбора всей армии в ровно одной клетке, после \(i\) изменений.