Esta é a versão difí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 numa 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 a 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$, por isso quer ir à linha $n + 1$ para apreciar a paisagem.
Para atingir o seu objetivo, Yuki pode realizar vários movimentos. Em cada movimento, escolhe uma das quatro direções (cima, baixo, esquerda, direita) e desloca-se uma célula nessa direção. Especificamente, 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 de distribuição dos obstáculos, não as suas posições específicas. Portanto, ela quer que a ajude a definir 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 (basta ter alcançado a linha $n + 1$ pelo menos uma vez; não precisa de permanecer lá após todos os movimentos serem concluídos).
Como Yuki está com pressa, o número de movimentos na sua solução não pode exceder $10 \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 \le 10 \cdot n$), que representa o número de movimentos na sua solução.
Na segunda linha, imprima uma cadeia $s$ de comprimento $k$, onde $s_i$ representa a direção do $i$-ésimo movimento de Yuki:
Se $s_i = \texttt{U}$, Yuki move-se para cima.
Se $s_i = \texttt{D}$, Yuki move-se para baixo.
Se $s_i = \texttt{L}$, Yuki move-se para a esquerda.
Se $s_i = \texttt{R}$, Yuki move-se 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 cinzentas representam obstáculos e as brancas representam células vazias. A imagem seguinte mostra todas as possíveis distribuições de obstáculos que satisfazem os requisitos:
Para a primeira distribuição de obstáculos, o percurso 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 percurso de Yuki é $(1, 1) \to (2, 1) \to (2, 1) \to (3, 1) \to (3, 1)$.
Para cada 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 cinzentas representam obstáculos e as brancas representam células vazias. A imagem seguinte mostra todas as possíveis distribuições de obstáculos que satisfazem os requisitos:
- É fácil provar que, para qualquer uma destas distribuições de obstáculos, seguindo os movimentos dados na saída do exemplo, Yuki alcançará a linha $n + 1$.