Килани играет в игру со своими друзьями. Игра представляет из себя клетчатое поле размером $$$n \times m$$$, где каждая клетка или пуста, или заблокирована, также у каждого игрока есть один или несколько замков на поле (ни одна клетка не содержит более одного замка).

Игра происходит в несколько раундов. В каждом раунде игроки по очереди расширяются: сначала расширяется первый игрок, затем расширяется второй игрок, и так далее. Расширение происходит следующим образом: для каждого замка, которым владеет игрок, он пытается расшириться в свободные клетки поблизости. Игрок $$$i$$$ может расшириться из клетки со своим замком в пустую клетку, если она достижима за не более чем $$$s_i$$$ (где $$$s_i$$$ — это показатель скорости игрока) движений влево, вверх, вправо или вниз, не проходящих через заблокированные клетки или клетки с замками других игроков. Игрок рассматривает множество клеток, в которые он может расшириться, и моментально строит во всех них свой замок. После этого ход переходит к следующему игроку.

Игра заканчивается, когда ни один игрок не может сделать ход. Вам дано поле игры и скорости расширения для каждого игрока. Килани хочет узнать для каждого игрока как много клеток он будет контролировать (иметь там замок) после того как игра закончится.