# 50032. N-pieces (special judge)

## 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)$, …

p10074-board

p10074-limit

• 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 k1n2 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 22 3 18 8 1


## Sample Output

oo.o.o.ooNo...........o..........o.....o....o...........o..o.........o....