eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Хмарочоси

Хмарочоси

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Під кінець семестру студент архітектурної академії Петро взнав, що йому терміново потрібно здати курсовий проект, завданння до якого звучало наступним чином: на квадратній площадці розміром N*N, розділеній на одиничні квадратики, розмістити будинки висотою від 1 до N поверхів, по одному у кожному квадратику так, щоб у кожному рядку і у кожному стовбчику схеми площадки "поверховість" всіх будинків була різною.

Зрозумівши, що сам він справитись із завданнням у встанволений термін не вспіє, Петро попитав у старших товаришів, чи не завалялись у них чернетки з подібним завданням. На щастя, один з старшокурсників поділився з Петром своїми результатами, але виглядали вони досить дивно. Для рядків і стовбчиків площадки було підписано, скільки будівель буде видно, якщо дивитись них ліворуч або праворуч (для рядків) та зверху чи знизу (для стовбчиків). Будівля вважається видимою, якщо перед нею немає будинків більшої поверховості. Більше того, так як чернетки були достатньо старими, деякі підписи стерлись.

Допоможіть Петру за заданою чернеткою відновити хоча б один з варіантів розміщення будинків, який підходить під цей опис.

Вхідні дані

У першому рядку задано два натуральних числа через пропуск: N, 2 <= N <= 4 – розмір квадратної площадки, а також максимальну поверховість будівель, та K – кількість підписів, що збереглись у чернетці, 0 <= K <= N*4.

У наступних K рядках задані підписи з чернетки у наступному форматі: номер рядка чи стовбчика, пропуск, напрям (W – рядок зліва направо, E – рядок зправа наліво, N – стовбчик зверху вниз, S – стовбчик знизу вверх), пропуск, кількість видимих будинків у цьому напрямку. Стовбчики нумеруються зліва направо, а рядки – зверху вниз. Нумерація начинається з одиниці.

Вихідні дані

У вихідний файл виводиться N рядків. У конному рядку N чисел через пропуск – поверховість будівель, розміщених у відповідному рядку площадки у порядку збільшення номера стовбчика. Результуюче розміщення булинків повинно задовільняти підписам з чернетки. Якщо варіантів розміщення будинків декількі, то вивести довільний з них. У випадку відсутності розв'язку вивести "No solution".

Приклад

Вхідні дані #1
4 7
1 N 3
2 S 2
4 S 4
1 E 1
2 W 2
3 E 2
3 W 2
Вихідні дані #1
2 3 1 4
1 4 2 3
3 1 4 2
4 2 3 1