Internet Problem Solving Contest

• Easy input data set – G1
• Hard input data set – G2

You are given a rectangular grid consisting of r × c points. The lower left corner has coordinates (1,1), the upper right corner has coordinates (c,r). The neighbors of a point (x,y) are the points (x − 1,y), (x + 1,y), (x,y − 1), and (x,y + 1), if they exist. A path is a sequence of points such that subsequent points are neighbors and each point appears on the path at most once.

Problem specification

Given two distinct points (x_s,y_s) and (x_f,y_f), find one longest path from (x_s,y_s) to (x_f,y_f).

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line with six integers – r, c, x_s, y_s, x_f, y_f.

For both the easy subproblem G1 and the hard subproblem G2, you may assume that 1 ≤ r,c ≤ 100 and rc ≥ 2. Additionally, for the easy subproblem G1 you may assume that r ≤ 5.

Output specification

For each test case, output a single string describing one possible longest path. If there are multiple longest paths, output any one of them.

A path a₁,a₂,…,a_k is described by a string consisting of k − 1 letters U, D, L, R. The i-th letter in the string describes the move from point a_i to a_i+1:
If a_i = (x,y) and a_i+1 = (x,y + 1), the i-th letter should be U.
If a_i = (x,y) and a_i+1 = (x,y − 1), the i-th letter should be D.
If a_i = (x,y) and a_i+1 = (x + 1,y), the i-th letter should be R.
If a_i = (x,y) and a_i+1 = (x − 1,y), the i-th letter should be L.

Example

first example:

second example: