Esta é a versão fácil deste problema. A única diferença entre as versões fácil e difícil é o limite do número de movimentos na sua solução.
Yuki vive em uma grade com $n+1$ linhas e $n$ colunas. As linhas são numeradas de $1$ a $n+1$ de cima para baixo, e as colunas de $1$ a $n$ da esquerda para a direita. Seja $(i,j)$ a célula na linha $i$ e coluna $j$.
Há $n-1$ obstáculos na grade, e sua distribuição satisfaz as seguintes condições:
Não há obstáculos nas linhas $1$ e $n+1$.
Para todo $2\le i\le n$, há exatamente um obstáculo na linha $i$.
Para todo $1\le j\le n$, há no máximo um obstáculo na coluna $j$.
Inicialmente, Yuki está em $(1,1)$. Ela ouviu dizer que um grupo de cangurus vive na linha $n+1$, então quer ir até a linha $n+1$ para apreciar a paisagem.
Para atingir seu objetivo, Yuki pode realizar vários movimentos. Em cada movimento, ela escolhe uma das quatro direções (cima, baixo, esquerda, direita) e anda uma célula nessa direção. Mais precisamente, se a célula de destino estiver fora da grade ou contiver um obstáculo, o movimento não é executado.
Infelizmente, Yuki conhece apenas as regras da distribuição dos obstáculos, e não suas posições específicas. Portanto, ela quer sua ajuda para especificar uma sequência de movimentos tal que, para qualquer distribuição válida de obstáculos, Yuki alcance a linha $n+1$ em algum momento (ela só precisa ter alcançado a linha $n+1$ pelo menos uma vez; não precisa permanecer lá após concluir todos os movimentos).
Como Yuki não tem pressa, o número de movimentos na sua solução não deve exceder $30\cdot n$.
Entrada
Uma única linha contém um inteiro positivo $n$ ($2\le n\le 10^3$).
Saída
Na primeira linha, imprima um inteiro $k$ ($1\le k\le30\cdot n$), representando o número de movimentos na sua solução.
Na segunda linha, imprima uma string $s$ de comprimento $k$, em que $s_i$ representa a direção do $i$-ésimo movimento de Yuki:
Se $s_i=\texttt{U}$, Yuki se move para cima.
Se $s_i=\texttt{D}$, Yuki se move para baixo.
Se $s_i=\texttt{L}$, Yuki se move para a esquerda.
Se $s_i=\texttt{R}$, Yuki se move para a direita.
Exemplos
Entrada 1
2
Saída 1
4 DRDD
Entrada 2
3
Saída 2
17 DDDUUURDDDUUURDDD
Nota
Para o primeiro exemplo:
- As células cinzas representam obstáculos, e as células brancas representam células vazias. A imagem a seguir mostra todas as distribuições possíveis de obstáculos que satisfazem os requisitos:
Para a primeira distribuição de obstáculos, o caminho de Yuki é $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.
Para a segunda distribuição de obstáculos, o caminho de Yuki é $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.
Para toda distribuição válida de obstáculos, Yuki alcança a linha $n+1$, portanto a saída do exemplo está correta.
Para o segundo exemplo:
- As células cinzas representam obstáculos, e as células brancas representam células vazias. A imagem a seguir mostra todas as distribuições possíveis de obstáculos que satisfazem os requisitos:
- É fácil provar que, para qualquer uma dessas distribuições de obstáculos, seguindo os movimentos dados na saída do exemplo, Yuki alcançará a linha $n+1$.