Skyscrapers
By the end of the semester, Peter, a student at the architectural academy, discovered he urgently needed to submit a course project. The task was as follows: On a square site of size N*N, divided into unit squares, place buildings with heights ranging from 1 to N floors, one in each square, ensuring that in each row and each column, the "height" of all buildings is unique.
Realizing he couldn't complete the task on his own in time, Peter reached out to his senior friends for any drafts of similar tasks. Luckily, one senior shared his results with Peter, but they appeared quite peculiar. For each row and column of the site, it was noted how many buildings would be visible when viewed from the left or right (for rows) and from the top or bottom (for columns). A building is considered visible if no taller buildings are in front of it. However, since the drafts were quite old, some notes had faded.
Help Peter restore at least one possible arrangement of the buildings that fits this description based on the given draft.
Input
The first line contains two natural numbers separated by a space: N, where 2 <= N <= 4, representing the size of the square site and the maximum height of the buildings, and K, the number of notes that have survived in the draft, where 0 <= K <= N*4.
The next K lines provide the notes from the draft in the following format: row or column number, space, direction (W for row from left to right, E for row from right to left, N for column from top to bottom, S for column from bottom to top), space, the number of visible buildings in this direction. Columns are numbered from left to right, and rows from top to bottom. Numbering starts from one.
Output
The output should consist of N lines. Each line should contain N numbers separated by a space, representing the height of the buildings placed in the corresponding row of the site in order of increasing column number. The resulting placement of buildings must satisfy the notes from the draft. If there are multiple valid placements, output any one of them. If no solution exists, output "No solution".