Skyscrapers#169
At the end of the semester, a student at the architecture academy named Peter learned that he urgently needed to submit his course project. The assignment was as follows: On a square site of size N \times N, divided into unit squares, place buildings of heights from to , one in each square, so that all building heights are different in every row and every column.
Realizing he would not make the deadline, Peter asked senior students if they had any drafts of similar assignments. Fortunately, one senior shared his results, but they were unusual: for some rows and columns, the draft listed, for specific directions, the number of buildings that would be visible when viewed from the left or right (for rows) or from the top or bottom (for columns). A building is visible if there is no taller building before it in that direction. Since the draft was old, some notes were missing.
Help Peter restore at least one arrangement of buildings that matches all the surviving notes.
The first line contains two natural numbers separated by a space: (2 \leq N \leq 4) — the size of the site (and the maximum building height), and (0 \leq K \leq 4N) — the number of surviving notes.
Each of the next lines describes a note in the following format: row or column number, space, direction ( — row from left to right, — row from right to left, — column from top to bottom, — column from bottom to top), space, number of visible buildings in this direction. Columns are numbered from left to right, rows from top to bottom. Numbering starts from one.
Output lines. Each line should contain numbers separated by a space — the number of floors in the buildings placed in the corresponding row in order of increasing column number. The arrangement must satisfy all surviving notes. If there are multiple valid arrangements, output any one of them. If there is no solution, print No solution.
Example 1