Небоскрёбы
Под конец семестра студент архитектурной академии Петя узнал, что ему срочно нужно сдать курсовой проект, задание к которому звучало следующим образом: на квадратной площадке размером N x N, поделенной на единичные квадратики, разместить дома высотой от 1 до N этажей, по одному в каждом квадратике так, чтобы в каждой строке и в каждом столбце схемы площадки этажность всех домов была различна.
Поняв, что сам он справиться с заданием в срок не успеет, Петя поспрашивал у старших товарищей, не завалялось ли у них черновиков с подобным заданием. К счастью, один из старшекурсников поделился с Петей своими результатами, но выглядели они весьма странно. Для строк и столбцов площадки было подписано, сколько зданий будет видно, если смотреть на них слева или справа (для строк) и сверху или снизу (для столбцов). Здание считается видимым, если перед ним нет зданий большей этажности. Более того, так как черновики были довольно старыми, некоторые подписи стерлись.
Помогите Пете по заданному черновику восстановить хотя бы один из вариантов расположения домов, подходящий под это описание.
Входные данные
В первой строке два натуральных числа через пробел: N, 2 <= N <= 4 - размер квадратной площадки, а также максимальная этажность зданий, и K - количество подписей, сохранившихся в черновике, 0 <= K <= N*4.
В последующих K строках записаны подписи из черновика в следующем формате: номер строки или столбца, пробел, направление (W - строка слева направо, E - строка справа налево, N - столбец сверху вниз, S - столбец снизу вверх), пробел, количество видимых домов в этом направлении. Столбцы нумеруются слева направо, а строки - сверху вниз. Нумерация начинается с единицы.
Выходные данные
В выходной файл выводится N строк. В каждой строке N чисел через пробел - этажности зданий, расположенных в соответствующей строке площадки в порядке увеличения номера столбца. Результирующее расположение домов должно удовлетворять подписям с черновика. Если вариантов расположения домов несколько, то вывести любой из них. В случае отсутствия решения вывести No solution.