## Problem Description

Given a chessboard of $n$ by $n$, is it possible to place m pieces in it so that no more than $k$ pieces appear in each row, each column, and each 45 degree line? Note that there are two 45 degree lines for a cell $(x, y)$ not in the corners. That is, the first one goes through … $(x-1, y + 1)$, $(x, y)$, $(x + 1, y -1)$, … and the second one goes through $(x + 1, y + 1)$, $(x, y)$, $(x - 1, y - 1)$, …

## Subtasks

- 5pt. $n = 3$, $m = 4$, and $k = 2$.
- 5pt. $n = 3$, $m = 3$, and $k = 1$.
- 15pt. $n = 6$, $m = 6$, and $k = 1$.
- 20pt. $n$ is no more than 8, $m$ is no more than 16, and $k$ is no more than 1.
- 50pt. $n$ is no more than 12, $m$ is no more than 30, and $k$ is no more than 10.
- 5pt. $n$ is no more than 15, $m$ is no more than 100, and $k$ is no more than 100.

## Hints

- You simply try to place the pieces into each cell in a row by row manner. Each time you place a piece, you need to check if your placement is valid.
- There are various optimizations you can use. For example, if you have placed m pieces in the same row then you should go on to the next row.
- To get the last 5 points you need a very careful implementation that tracks the number of pieces that are already placed in each row, column a 45 degree line.

## Input Format

`n1 m1 k1`

`n2 m2 k2`

`...(until EOF)`

For each line, you have to find out whether it is possible or not to place m pieces in a chessboard of $n$ by $n$ so that no more than $k$ pieces appear in each row, each column, and each 45 degree line.

## Output Format

If it is possible to place $m$ pieces in the chessboard, print one possible solution.

If it is not possible to place m pieces in the chessboard, print `N`

.

## Sample Input

`3 6 2`

`2 3 1`

`8 8 1`

## Sample Output

`oo.`

`o.o`

`.oo`

`N`

`o.......`

`....o...`

`.......o`

`.....o..`

`..o.....`

`......o.`

`.o......`

`...o....`