E. Slimes vs Iron Golem

所有熟識「當個創世神」這一個遊戲的人都知道，假如你創建一個超平坦世界，你會看見村莊，被動型生物（如牛、雞、豬、羊等），以及惡名昭彰的史萊姆。這些史萊姆會製造噪音，破壞農田和攻擊鐡魔像。它們令到在超平坦世界上建築十分不愉快。

你的好朋友愛麗絲是一個著名多人伺服器的持有者，她嘗試設計一些小遊戲給她的玩家。不如令史萊姆變得更有用？所以，她設計了「史萊姆大戰鐡魔像」這個小遊戲。

這個小遊戲的場地是一個有 行， 列，被障礙物包圍的競技場。行和列分別以 至 （上至下）和 至 （左至右）標記。我們將第 行、第 列的格子以 表示。如 ，競技場內不會有障礙物。如 則競技場內會有一個在 的障礙物。

每個玩家控制一隻史萊姆。所有史萊姆的初始體積都是 1，而它們的體積會每秒增加 1。遊戲的目標是打敗位於 、不會移動及攻擊的鐡魔像。如果史萊姆的位置是 並且它的體積大於或等於 ，史萊姆就可以打敗鐡魔像。

為了令小遊戲更具挑戰性，愛麗絲限制了史萊姆移動的方法。每秒史萊姆必需移動到旁邊沒有被障礙物阻礙的格子（上、下、左或右）。每個格子中史萊姆的數目並沒有限制。但是，史萊姆不可以回到上一秒它所在的格子。另一個說法就是，史萊姆不可以轉180度。如果史萊姆走進了一個死胡同（即已經不存在任何合法的移動），史萊姆會輸掉這一場遊戲（除非史萊姆打敗了鐡魔像，見樣例 3）。

作為愛麗絲的好朋友，你想透過在小遊戲中作弊令她對你刮目相看。你的史萊姆永遠於 開始，而你的目標是在正好 秒後，當你的體積是 時打敗鐡魔像。請你編寫一個程式來判斷是否可能逹成目標，並輸出任何可以逹成目標的移動方法。

Any Minecraft veteran will know that if you create a new Superflat map, you will see villages, passive mobs (cows, chickens, pigs, sheeps, etc), and the notorious slimes. Those slimes make a lot of noise, step on farms and attack the Iron Golem. It makes building on a Superflat map very unpleasant.

Your friend Alice is the owner of a popular multiplayer server, and she is trying to come up with new mini games for the players to enjoy. What about making slimes more useful? Therefore, she came up with the ``Slimes and Iron Golem'' mini game.

The mini game is played in an arena with rows and columns surround by obstacles. The rows are numbered from to from top to bottom, and the columns are numbered from to from left to right. Let's denote the cell at row column as . There are no obstacles in the arena if . If , there is an obstacle at .

Each player controls a slime. All slimes start with size equals to 1, and the size will increase by 1 every second. The objective the game is to defeat the Iron Golem at that doesn't move or attack. A slime can defeat the Iron Golem if the slime is located at and has size greater than or equal to .

To make the mini game more challenging, she imposed restrictions on how the slimes can move. In each second, a slime MUST move to an adjacent cell (up, down, left or right) that is not blocked by an obstacle. There is no limit on the number of slimes allowed in a single cell. However, the slime MUST NOT return to the cell that it came from in the previous second. In other words, slimes are NOT allowed to make 180 degree turns. If a slime runs into a dead-end (when there are no possible legal moves), the slime loses the game immediately (except when the slime defeats the Iron Golem; see Example Test 3).

Being a good friend of her, you want to impress her by writing a cheat for the mini game. You should assume that your slime always start at , and your goal is to defeat the Iron Golem exactly seconds later when your size is . Write a program to determine whether it is possible, and output any sequence of steps if possible.

輸入的第一行有一個整數 ，代表測試的數目。

對於每一測試:

第一行有三個整數 ， 和 。

第二行有兩個整數 和 。保證鐡魔像不會位於 。

第三行有一個整數 。

如 ，則第四行會有兩個整數 和 。保證障礙物不會位於 和 。

The first line of the input contains an integer -- the number of testcases, .

For each test case:

The first line contains 3 integers , and .

The second line contains 2 integers and . It is guaranteed that the Iron Golem is not located at .

The third line contains a single integer .

If , then there will be a fourth line containing 2 integers and . It is guaranteed that the obstacle is not located at nor .

對於每一測試:

如果不可能於正好在遊戲開始 秒後打敗鐡魔像，輸出一行 NO。

否則，在第一行輸出 YES。

在第二行輸出一個長度為 包含字符 U ，D，L，R 分別表示上、下、左和右的字符串。第 個字符應表示史萊姆在第 秒應移動的方向。

For each test case:

If there is no possible way to defeat the Iron Golem exactly seconds after the start of the game, output NO in a single line.

Otherwise, output YES on the first line.

On the second line output a string of length , consisting of characters U, D, L, R for up, down, left and right respectively. The -th character in the string should be the direction that the slime should travel during the -th second.

Sample 1 input

1
2 2 5
1 2
0

Sample 1 output

YES
RDLUR

Sample 2 input

2
3 3 6
3 1
1
2 1
3 3 2
3 1
1
2 1

Sample 2 output

YES
RRDLDL
NO

Sample 3 input

2
5 6 17
3 6
1
3 5
2 2 2
2 2
1
1 2

Sample 3 output

YES
RRRRRDDDLLLUURRRD
YES
DR

Sample 3 explanation

樣例 3 的第一個測試： 輸出的視像化如下图所示。

樣例 3 的第二個測試： 這是對於走進死胡同的例外情況。假如你能夠在走進死胡同的同時打敗鐡魔像，你仍能夠獲勝。

1st test in example 3: Below figure is the visualisation for the output.

2nd test in example 3: This is an exception to the dead-end rule. You can still win if you can defeat the Iron Golem when you reach a dead-end.

對於全部測試數據，滿足︰

，

，

, , ，

或 。

如 , 則 , , 及 。

For all test data,

,

,

, , ,

or .

If , then , , and .