Stable Arrangement of Rooks
Contest: Hello 2022
Difficulty rating: 800
Tags: constructive algorithms

You have an $$$n \times n$$$ chessboard and $$$k$$$ rooks. Rows of this chessboard are numbered by integers from $$$1$$$ to $$$n$$$ from top to bottom and columns of this chessboard are numbered by integers from $$$1$$$ to $$$n$$$ from left to right. The cell $$$(x, y)$$$ is the cell on the intersection of row $$$x$$$ and collumn $$$y$$$ for $$$1 \leq x \leq n$$$ and $$$1 \leq y \leq n$$$.

The arrangement of rooks on this board is called good, if no rook is beaten by another rook.

A rook beats all the rooks that shares the same row or collumn with it.

The good arrangement of rooks on this board is called not stable, if it is possible to move one rook to the adjacent cell so arrangement becomes not good. Otherwise, the good arrangement is stable. Here, adjacent cells are the cells that share a side.

Such arrangement of $$$3$$$ rooks on the $$$4 \times 4$$$ chessboard is good, but it is not stable: the rook from $$$(1, 1)$$$ can be moved to the adjacent cell $$$(2, 1)$$$ and rooks on cells $$$(2, 1)$$$ and $$$(2, 4)$$$ will beat each other.

Please, find any stable arrangement of $$$k$$$ rooks on the $$$n \times n$$$ chessboard or report that there is no such arrangement.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 40$$$) — the size of the chessboard and the number of rooks.

Output format:
If there is a stable arrangement of $$$k$$$ rooks on the $$$n \times n$$$ chessboard, output $$$n$$$ lines of symbols . and R. The $$$j$$$-th symbol of the $$$i$$$-th line should be equals R if and only if there is a rook on the cell $$$(i, j)$$$ in your arrangement.

If there are multiple solutions, you may output any of them.

If there is no stable arrangement, output $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you should find stable arrangement of $$$2$$$ rooks on the $$$3 \times 3$$$ chessboard. Placing them in cells $$$(3, 1)$$$ and $$$(1, 3)$$$ gives stable arrangement.

In the second test case it can be shown that it is impossbile to place $$$3$$$ rooks on the $$$3 \times 3$$$ chessboard to get stable arrangement.

Example input:
5
3 2
3 3
1 1
5 2
40 33

Example output:
..R
...
R..
-1
R
.....
R....
.....
....R
.....
-1

Editorial:
It is easy to see that if there are two rooks in the neighbouring rows we can move one of them to the another of these two rows, so there shouldn't be two rooks in the neighbouring rows in a stable arrangement.
Let's split chessboard into $$$\lceil \frac{n}{2} \rceil$$$ regions in the following way: region $$$1$$$ contains all cells of rows $$$1$$$, $$$2$$$, region $$$2$$$ contains all cells of rows $$$3$$$, $$$4$$$ and so on. The last region can contain cells of only one row if $$$n$$$ is odd. We had shown that there can't be two rooks in one region so if $$$k > \lceil \frac{n}{2} \rceil = \lfloor \frac{n+1}{2} \rfloor$$$ there is no stable arrangement.
We can always place $$$k \leq \lfloor \frac{n+1}{2} \rfloor$$$ rooks into cells $$$(1, 1)$$$, $$$(3, 3)$$$, $$$\ldots$$$, $$$(2k-1, 2k-1)$$$. Such arrangement is stable because after moving any rook to the neighbouring row it will be in the same collumn and in the even numbered row where there are no other rooks. The same applies for moving rook to the neighbouring collumn.
Actually, we can show that condition from the first paragraph combined with the same condition for collumns is sufficient and necessary criterion for stable placement.
Bonus: how many stable arrangements exist?