# C. Game with Chips

Petya has a rectangular Board of size n×m. Initially, k chips are placed on the board, i-th chip is located in the cell at the intersection of sxi-th row and syi-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) cell, then after the operation:

• left, its coordinates will be (x, y − 1);
• right, its coordinates will be (x, y + 1);
• down, its coordinates will be (x + 1, y);
• up, its coordinates will be (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 2nm 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 2nm actions.

## Input

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

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

The next kk lines contains two integers each fxi, fyi (1 ≤ fxi ≤ n, 1 ≤ fyi ≤ m) — the position that the i-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,U respectively.

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

## Examples

input

3 3 2
1 2
2 1
3 3
3 2


output

3
DRD


input

5 4 3
3 4
3 1
3 3
5 3
1 3
1 4


output

9
DDLUUUURR


## Problem solving

#include<bits/stdc++.h>
#define fi        first
#define se        second
#define pb        push_back
#define PI        acos(-1)
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<ll,ll>   PLL;
typedef pair<ll,int>  PLI;
const int INF = 0X3F3F3F3F;
const int MIN = -(1<<30);
const ll N = 1e5+7;
inline void solve()
{
int n,m,k;
cin>>n>>m>>k;
int x,y;
for(int i=0; i<k; i++) cin>>x>>y;//与输入的起始点和终止点无关了
for(int i=0; i<k; i++) cin>>x>>y;

string s="";
for(int i=n; i>1; i--) s=s+'U';//把所有点向上向左移到左上角
for(int j=m; j>1; j--) s=s+'L';

for(int i=1; i<=n; i++)//n行
{
if(i&1) //奇数行向右
for(int j=1; j<m; j++) s=s+'R';
else   //偶数行向左
for(int j=m; j>1; j--) s=s+'L';
if(i!=n) s+='D'; //除了最后一行 每行走到头的时候向下
}
cout<<s.size()<<endl<<s<<endl;
}
int main()
{
IOS();
solve();
return 0;
}


# E. Count The Blocks

You wrote down all integers from 0 to 10n − 1, padding them with leading zeroes so their lengths are exactly n. For example, if n = 3 then you wrote out 000, 001, …, 998, 999.

A block in an integer x is a consecutive segment of equal digits that cannot be extended to the left or to the right.

For example, in the integer 00027734000 there are three blocks of length 1, one block of length 2 and two blocks of length 3.

For all integers i from 1 to n count the number of blocks of length i among the written down integers.

Since these integers may be too large, print them modulo 998244353.

## Input

The only line contains one integer n (1 ≤ n ≤ 2⋅105).

## Output

In the only line print n integers. The i-th integer is equal to the number of blocks of length i.

Since these integers may be too large, print them modulo 998244353.

## Examples

input

1


output

10


input

2


output

180 10


## Problem solving

• [ ] 插入的串两端都不在边界，插入的连续串可以为0-9，10种，两端相邻的位置不能和他相同，所以有9种。其他的位置可以随便，都是10种。而长度为i的串在n个为位置中有（n-i+1）个位置可以查入，减去两端的边界，就有（n-i-1)个位置可以插入。所以一共有：(n-i-1)$\times$10$\times$9$\times$9$\times$10 n-i-2 个block，n-i-2是剩余随便插的空格。
• [ ] 插入的串两端有一端在边界。因为有一端在边界，所以只需要处理另一端不在边界的相邻位置就行了。这种情况有 2$\times$10$\times$9$\times$10 n-i-1 个block，这里乘上2是因为有两个边界，不知道哪一端在边界上。

#include<bits/stdc++.h>
#define fi        first
#define se        second
#define pb        push_back
#define PI        acos(-1)
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<ll,ll>   PLL;
typedef pair<ll,int>  PLI;
const int INF = 0X3F3F3F3F;
const int MIN = -(1<<30);
const ll N = 2e5+7;
const ll mod = 998244353;
ll fac[N];
ll ans[N];
inline void solve()
{
fac[0]=1;
for(int i=1; i<N; i++) fac[i] = fac[i-1]*10%mod; //把10的N次方预处理一下

ll n;
cin>>n;
ans[n] = 10;
for(int i=n-1; i>=1; i--)
ans[i] = (((n-i-1)*10*9*9*fac[n-i-2])%mod + (10*9*2*fac[n-i-1])%mod)%mod;
for(int i=1; i<=n; i++)
cout<<ans[i]<<" ";
cout<<endl;

}
int main()
{
IOS();
solve();
return 0;
}