codeforces1327C. Game with Chips

C. Game with Chips

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya has a rectangular Board of size n×mn×m. Initially, kk chips are placed on the board, ii-th chip is located in the cell at the intersection of sxisxi-th row and syisyi-th column.

In one action, Petya can move all the chips to the left, right, down or up by 11 cell.

If the chip was in the (x,y)(x,y) cell, then after the operation:

left, its coordinates will be (x,y−1)(x,y−1);
right, its coordinates will be (x,y+1)(x,y+1);
down, its coordinates will be (x+1,y)(x+1,y);
up, its coordinates will be (x−1,y)(x−1,y).

If the chip is located by the wall of the board, and the action chosen by Petya moves it towards the wall, then the chip remains in its current position.

Note that several chips can be located in the same cell.

For each chip, Petya chose the position which it should visit. Note that it's not necessary for a chip to end up in this position.

Since Petya does not have a lot of free time, he is ready to do no more than 2nm2nm actions.

You have to find out what actions Petya should do so that each chip visits the position that Petya selected for it at least once. Or determine that it is not possible to do this in 2nm2nm actions.

Input

The first line contains three integers n,m,kn,m,k (1≤n,m,k≤2001≤n,m,k≤200) — the number of rows and columns of the board and the number of chips, respectively.

The next kk lines contains two integers each sxi,syisxi,syi (1≤sxi≤n,1≤syi≤m1≤sxi≤n,1≤syi≤m) — the starting position of the ii-th chip.

The next kk lines contains two integers each fxi,fyifxi,fyi (1≤fxi≤n,1≤fyi≤m1≤fxi≤n,1≤fyi≤m) — the position that the ii-chip should visit at least once.

Output

In the first line print the number of operations so that each chip visits the position that Petya selected for it at least once.

In the second line output the sequence of operations. To indicate operations left, right, down, and up, use the characters L,R,D,UL,R,D,Urespectively.

If the required sequence does not exist, print -1 in the single line.

Examples

input

Copy

output

Copy

3
DRD

input

Copy

output

Copy

9
DDLUUUURR

题意：

n * m大的方格里有 k 个点，给出每个点至少要访问一次的位置，每次可以将所有点向上、向下、向左、向右移动一个单位，问是否可以在 2 * n * m 步数内移动完成，如果可以输出一种移动方法。

（题目中没说要输出的移动方法必须 <= 2 * n * m

所以把整个网格扫描一遍就行了……

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int main()
{
    int n, m, k, x, y;
    while(~scanf("%d%d%d", &n, &m, &k))
    {
        for(int i = 1; i <= k; ++i)
        {
            scanf("%d%d", &x, &y);
        }
        for(int i = 1; i <= k; ++i)
        {
            scanf("%d%d", &x, &y);
        }
        string s = "";
        s += string(n - 1, 'U');
        s += string(m - 1, 'L');
        for(int i = 1; i <= n; ++i)
        {
            if(i & 1)
            {
                s += string(m - 1, 'R');
            }
            else
            {
                s += string(m - 1, 'L');
            }
            if(i < n)
                s += "D";
        }
        cout<<s.size()<<'\n';
        cout<<s<<'\n';
    }
    return 0;
}