One of Majk’s passions is chess. Recently, he took part in a tournament that ended up having a peculiar property.
In chess, one point is awarded for each game: if there is a winner, they get the point, and if the game ends in a draw, each player gets half a point.
With this scoring it is very common that multiple players end up with the same point total. The tournaments then use multiple tiebreakers to determine the final ranking. That’s why Majk was so surprised – his tournament didn’t need to use any tiebreakers, as each player ended up with a different point total.
You are given \(n\): the number of players in the tournament. The players are numbered from \(0\) to \(n-1\).
In the tournament, each pair of players played exactly one game.
The number \(n\) is guaranteed to be odd. (The reason why \(n\) is odd is to make sure each player has the white pieces in the same number of games. This is not relevant for our problem, we are mentioning it purely for flavor.)
You are also given the number \(d\): the total number of drawn games in the tournament.
Finally, you are given the information that at the end of the tournament no two players had the same point total.
Determine whether such a tournament exists. If yes, construct one.
The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.
Each test case consists of a single line with two integers \(n\) and \(d\).
In each test case, \(0\leq d\leq n(n-1)/2\).
For each test case, first output one line with “YES” if
such a tournament exists or “NO” if it does not.
If the tournament exists, output additional \(n\) lines describing one such tournament.
The \(i\)-th of these lines (numbering
from \(0\)) should describe the results
of player \(i\) as a string of \(n\) characters. The \(j\)-th of these characters should be \(i\)’s result when playing against \(j\): W for a win,
D for a draw, L for a loss, and X
for no result (which is only used for \(j=i\)).
If there are multiple solutions, you may output any one of them.
Input file: C1.in
Constraints: \(t\leq 100\) and in each test \(n\leq 5\).
Input file: C2.in
Constraints: \(t\leq 100\) and in each test \(n\leq 11\).
Input file: C3.in
Constraints: \(t\leq 100\) and in each test \(n\leq 101\).
input2 5 10 7 3 | outputNO YES XLLWLLD WXLWLWL WWXLDWL LLWXLWD WWDWXWW WLLLLXL DWWDLWX |
If there are five players and ten draws, all games must have ended in a draw, but then each player has exactly two points. Hence, in the first test case there is no such tournament.
In the second test case the individual players scored 1.5, 3, 3.5, 2.5, 5.5, 1, and 4 points – no two total scores are the same. And as required, there were exactly three draws: 0 with 6, 2 with 4, and 3 with 6.
