Peaceful kings P71701

Statement

thehtml

Write a program that prints all the ways to place k kings on a n × n board so that no king threatens another king. Remember that a king threatens all the surrounding cells, either horizontally, vertically, or diagonally.

For instance, these are some ways to place 3 kings on a 4 × 4 board:

showmover=false, label=false, maxfield=d4, setpieces=ka2,kb4,kc1 showmover=false, label=false, maxfield=d4, setpieces=ka3,kc4,kd2 showmover=false, label=false, maxfield=d4, setpieces=ka1,kc4,kd1 showmover=false, label=false, maxfield=d4, setpieces=ka1,kb3,kd4

Input

Input consists of two natural numbers n > 0 and 0 ≤ k ≤ n².

Output

Print all the ways to place k kings on a n × n board so that no king threatens another king. Mark the kings with a ‘K’, and the empty cells with a dot. Print a line with ten hyphens after every board.

Information about the checker

You can print the solutions to this exercise in any order.

Observation

The test cases of this problem do not require a very clever algorithm.

Public test cases

Input

2 1

Output

K.
..
----------
.K
..
----------
..
K.
----------
..
.K
----------

Input

3 4

Output

K.K
...
K.K
----------

Input

3 5

Output

Input

3 3

Output

K.K
...
K..
----------
K.K
...
.K.
----------
K.K
...
..K
----------
K..
..K
K..
----------
K..
...
K.K
----------
.K.
...
K.K
----------
..K
K..
..K
----------
..K
...
K.K
----------

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++