TRGRID - Traversing Grid

Starting at the top left corner of an N*M grid and facing towards the right, you keep walking one square at a time in the direction you are facing. If you reach the boundary of the grid or if the next square you are about to visit has already been visited, you turn right. You stop when all the squares in the grid have been visited. What direction will you be facing when you stop?

For example : Consider the case with N = 3,M = 3. The path followed will be (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 1) → (2, 0) → (1, 0) → (1, 1). At this point, all squares have been visited, and you are facing right.

Input

The first line contains T the number of test cases. Each of the next T lines contain two integers N and M, denoting the number of rows and columns respectively.

Output

Output T lines, one for each test case, containing the required direction you will be facing at the end. Output L for left, R for right, U for up, and D for down.

Example

Input:
4
1 1
2 2
3 1
3 3

Output:
R
L
D
R

Constraints

1 <= T <= 10000
1 <= N, M <= 1000000000


Added by:Varun Jalan
Date:2010-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem used for Codechef Snackdown Onsite

hide comments
2016-03-22 13:22:29 utkarsh538
Simple problem,Just think of all possible cases. (y)
2016-01-20 05:25:23
For me, it was enough to draw 25 rectangles of sizes from 1x1 to 5x5 in Excel, calculate the direction and enter it into the table. The formula is easily observable.
2015-10-30 03:10:45 Prakhar Dev Gupta
Doing easy questions is fun :P
2015-09-25 12:25:26 Sarthak Munshi
Just work out all possible scenarios !

Last edit: 2015-09-25 12:32:33
2015-09-19 12:04:27 Kriti Singhal
easy prblm...my 50th on spoj :D
2015-08-31 12:23:30
simple problem dont use any iterations just draw for n=m,n>m,n<m and see how directions change for these values for the smaller constraints(if n<m check for m whether even or odd and get a conclusion
) if they are even or odd
2015-08-28 11:32:28 ram
My 100th on SPOJ. :) :)
Very easy problem. Just look at 4 different cases.
2015-07-20 07:55:54 xxbloodysantaxx
No finding the co-ordinate is damn easy . Just a single easy recursion and you are done!!
2015-05-27 07:59:33 [Mayank Pratap]
Just observe ......
@dushyant ....Right ....problem can be made more fun if final position is asked...
2015-03-29 19:17:49 Dushyant Singh
A tougher version of this problem can be like this- Find the position where the player would stop. For example- for 2*3 it is (1,0) and for 3*3 it is (1,1).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.