Килани играет в игру со своими друзьями. Игра представляет из себя клетчатое поле размером \(n \times m\), где каждая клетка или пуста, или заблокирована, также у каждого игрока есть один или несколько замков на поле (ни одна клетка не содержит более одного замка).
Игра происходит в несколько раундов. В каждом раунде игроки по очереди расширяются: сначала расширяется первый игрок, затем расширяется второй игрок, и так далее. Расширение происходит следующим образом: для каждого замка, которым владеет игрок, он пытается расшириться в свободные клетки поблизости. Игрок \(i\) может расшириться из клетки со своим замком в пустую клетку, если она достижима за не более чем \(s_i\) (где \(s_i\) — это показатель скорости игрока) движений влево, вверх, вправо или вниз, не проходящих через заблокированные клетки или клетки с замками других игроков. Игрок рассматривает множество клеток, в которые он может расшириться, и моментально строит во всех них свой замок. После этого ход переходит к следующему игроку.
Игра заканчивается, когда ни один игрок не может сделать ход. Вам дано поле игры и скорости расширения для каждого игрока. Килани хочет узнать для каждого игрока как много клеток он будет контролировать (иметь там замок) после того как игра закончится.
Выходные данные
Выведите \(p\) целых чисел — количество клеток, контролируемых каждым игроком после конца игры.
Примечание
Картинка ниже показывает состояние игры до начала, после первого раунда и после второго раунда в первом примере.
Во втором примере первый игрок «заблокирован», так что он ничего не сможет захватит в течении всей игры. Все остальные игроки будут расширяться наверх в течении первых двух раундов, а на третьем раунде только второй игрок расширится влево.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
1 1
1..
...
..2
|
6 3
|
|
2
|
3 4 4
1 1 1 1
....
#...
1234
|
1 4 3 3
|