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

题意就是在一个 n*m 的矩阵中给你 k 个点的起始位置和终止位置,让你输出一个长度小于 2nm 的字符串(只包括U,D,L,R,表示移动的方向,当移动到边界时就原地不动),这个字符串控制所有的k个点,让每个点都会至少经过一次自己对应的终止点。

这道题没有要求输出最小的字符串,所以可以直接让所有的起始点都置于矩阵的左上角,然后从左上角开始,到右下角,依次访问矩阵的每个点,

#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 到 10n - 1的这些数中(包括前导0,所以都是n位数), 对应的每个长度i一共有多少个block。 block指的是连续相同的数字的长度,无法向左向右扩展。

例如:00027734000有2个长度为3的block,1个长度为2的block,3个长度为1的block.

可以理解为现在有n个空,每个空都可以插入0-9的一个数字,所有这些排列中长度为i的block有多少个。

因为所求的是长度为i的block,我们不妨直接插入一段长度为i的连续相等的一串数字,然后处理这串数字两端相邻的位置,让他们不与插入的数字相等即可。这里分两种情况:

  • [ ] 插入的串两端都不在边界,插入的连续串可以为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是因为有两个边界,不知道哪一端在边界上。

这两种情况加起来就是所求的block的个数了

#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;
}

一个好奇的人