396. Dance it up!

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Dance Dance Revolution is a game machine which forces a player to dance. The goal of the game is to step the dance-floor buttons in appropriate time. There are four buttons on the floor: LEFT, UP, RIGHT and DOWN.

Petya is a big DDR fun and spends all his spare time dancing on it. But he has a problem: he doesn't have enough of stamina. Therefore he asks you to write a program which can compute the optimal sequence of actions for a song in order to minimize the energy required to dance it.

The song for the DDR machine is divided into several equal time intervals (beats). For each beat it shows the buttons to be pressed. It is allowed to press non-required buttons (there is no penalty for doing this), but all required buttons should be pressed. For now, Petya is not a very good dancer and you can assume that each beat requires at most one button pressed.

The initial player position is "left leg on the LEFT button and right leg on the RIGHT button". Each beat a player is allowed to follow one of these patterns:



After testing a Prove-Of-Concept version of the program, Vasya realized that if program instructs him to move into position "left leg on RIGHT button and right leg on LEFT button" he can't see monitor with further instructions and fails immediately. So, this position is illegal.

Input
The first line of the input file contains integer number N — length of the song in beats (1≤ N≤ 1000). The second line consists of exactly N characters and contains instructions for each beat. Characters 'L', 'U', 'R' or 'D' mean that the required button for a beat is LEFT, UP, RIGHT or DOWN correspondingly. Character 'N' means that there are no required buttons at this beat.

Output
In the first line output the amount of energy required for stepping the song. After that, output exactly N lines with two characters in each. Each line should contain the optimal legs position (the first character for the left leg, the second character — for the second) for the corresponding beat. Use 'L', 'U', 'R' and 'D' characters for LEFT, UP, RIGHT and DOWN buttons correspondingly. If there are several solutions you can output any of them.

Example(s)
sample input
sample output
6
RULURL
14
LR
UR
UL
UL
UR
LR

sample input
sample output
9
LURLDRLNL
25
LR
LU
RU
DL
DL
DR
LR
LR
LR




Online Contester Team © 2002 - 2010. All rights reserved.