Задачи командного чемпионата

Макс хранит свои радиоуправляемые машины в большой коробке размером 3x3, в которой может поместиться вплотную 3 ряда по 3 машины. Начальное расположение машин в коробке неизвестно. С помощью пульта управления Макс может двигать машины в коробке в 4-х направлениях в соседнюю позицию. Если на пути движения машины находится стенка или другая машина, машина не выполняет команду и сообщает звуковым сигналом об ошибке.

Напишите программу, которая определяет расположение машин в коробке после выполнения серии команд.

В первой строке ввода содержатся два целых число – количество машин в коробке `N` (`1\ ≤\ N\ ≤\ 8`) и количество команд `K` (`1\ ≤\ K\ ≤\ 100`). Далее следует `K` строк, каждая строка содержит одну команду в формате `"idf"`, где `i` (`1\ ≤\ i\ ≤\ N`) – номер машины, `d` – направление движения машины с номером `i`, задается символами 'N' (север), 'S' (юг), 'E' (восток), 'W' (запад), `f` – результат выполнения команды, символ '+' (машина выполнила команду) или '-' (машина наткнулась на препятствие).

Вывести 3 строки, содержащих по 3 символа – предполагаемое конечное расположение машин в коробке. Клетка с машиной содержит номер машины, а пустая – символ '.'. Если входным данных соответствует несколько возможных расположений, вывести одно из них (любое).

3 4
1N+
2S+
3N-
1N+

1.3
.2.
...