B. Великий побег Авраама
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Авраам — смелый исследователь, который идет туда, где не был ни один другой программист. В своей следующей экспедиции он планирует исследовать необычный лабиринт. Он знает, что лабиринт представляет собой сетку размером $$$n \times n$$$, в каждой ячейке которой находится стрелка, указывающая в одном из четырёх направлений: вверх, вниз, влево или вправо. Авраам также знает, что если он стоит на стрелке, он будет вынужден перемещаться по направлениям стрелок, начиная с этой ячейки. Каждая стрелка перемещает Авраама ровно на $$$1$$$ ячейку в направлении, в котором она указывает. Если он достигнет стрелки, указывающей за пределы лабиринта, Авраам сможет сбежать из лабиринта.

Авраам не знает, как расположены стрелки, поэтому он хочет подготовиться к нескольким сценариям. Он поручает вам найти такое расположение стрелок в сетке, чтобы было ровно $$$k$$$ ячеек, начиная на которых он сможет сбежать из лабиринта.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$0 \le k \le n^2$$$) — размер сетки и количество ячеек, из которых Авраам должен иметь возможность сбежать.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных:

  • Если существует сетка, удовлетворяющая требованиям, выведите YES, а затем выведите $$$n$$$ строк с $$$n$$$ символами в каждой строке, указывающими направление стрелок. Каждый символ должен быть одним из U (вверх), R (вправо), L (влево) или D (вниз).
  • В противном случае, если решения нет, выведите NO.

Если существует несколько решений, выведите любое из них.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
2 4
3 5
2 3
Выходные данные
YES
UU
UU
YES
UUU
RDR
ULR
NO
Примечание

В первом наборе входных данных, независимо от того, в какой ячейке Авраам изначально стоит, он в конечном итоге выйдет из лабиринта, так как он будет последовательно двигаться вверх; таким образом, он сможет сбежать из всех $$$4$$$ ячеек, как и требовалось.

Во втором наборе входных данных Авраам в конечном итоге сбегает, если он стоит в одной из следующих ячеек:

  • В любой ячейке в первом ряду (все из которых U)
  • В любой ячейке в третьем столбце (одна из которых U, а другие две R)

Кроме них нет ячеек, начиная с которых он сбежит. Итого, Авраам может сбежать ровно из $$$5$$$ ячеек в этой конфигурации, как и требовалось.

В третьем наборе входных данных можно доказать, что нет такого расположения стрелок, чтобы Авраам мог сбежать ровно из $$$3$$$ ячеек.