<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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:



Not to change legs position. Not to press buttons. This action costs no energy.
Not to change legs position. Press the button on which one of the legs is. This action costs 1 point of energy.
Move the leg, which didn't press a button at the previous beat, to a vacant button and press it. Another leg doesn't change position. This action costs 3 points of energy.
Move the leg, which pressed a button at the previous beat, to a vacant button and press it. Another leg doesn't change position. This action costs 9 points of energy.
Jump with both legs to any two different buttons and press both of them. This action costs 10 points of energy.



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

<|response|>
## 1) Abridged problem statement (concise)

There are 4 DDR buttons: `L, U, R, D`. A song has `N (1..1000)` beats, each beat requires pressing **at most one** button: one of `L/U/R/D`, or `N` meaning “no required press”.

Initial position before beat 1: **left foot on `L`**, **right foot on `R`**.

Each beat you may do one action (extra presses are allowed, but required button must be pressed if given):

1. Do nothing (no move, no press) — cost `0`
2. Press with a foot already on its button — cost `1`
3. Move the foot that **did not press** previous beat to a vacant button and press — cost `3`
4. Move the foot that **did press** previous beat to a vacant button and press — cost `9`
5. Jump: move both feet to any two different buttons and press both — cost `10`

Feet must be on **different** buttons. Additionally, position `(left=R, right=L)` is **illegal**.

Output minimum total energy and one optimal sequence of positions (2 characters per beat: left-foot button then right-foot button).

---

## 2) Key observations

1. **Cost depends on who pressed last beat**, not only on current positions:
   - Moving the same foot that pressed last time costs `9`, the other costs `3`.
   - Therefore we must track “last presser” in the DP state.

2. Each beat requires **≤ 1** button, so for a beat with requirement `req`, it suffices that **the pressed set contains `req`**:
   - Press-left, press-right, move-left, move-right press exactly one button.
   - Jump presses two buttons.

3. State space is tiny:
   - left position: 4 choices
   - right position: 4 choices
   - last presser: 4 possibilities (`left/right/none/both`)
   - Total per beat: `4*4*4 = 64` states (minus invalid ones)

4. Illegal constraints are easy to filter:
   - Disallow `left == right`
   - Disallow `(left==R && right==L)`

---

## 3) Full solution approach (DP + reconstruction)

### State encoding
Index buttons as: `L=0, U=1, R=2, D=3`.

Let `last` be:
- `0`: left pressed last beat
- `1`: right pressed last beat
- `2`: nobody pressed last beat
- `3`: both pressed last beat (happens only after jump)

Define:
`dp[i][l][r][last]` = minimum energy after processing first `i` beats (beats `0..i-1`), ending with left at `l`, right at `r`, and `last`.

Initialize:
`dp[0][L][R][none] = dp[0][0][2][2] = 0`.

Maintain a `parent` pointer for each state to reconstruct the positions sequence.

### Transitions for beat i
Let `req = -1` if `s[i]=='N'`, else index of required button.

From state `(l,r,last)`:

1) **Do nothing**  
Allowed only if `req == -1`  
- `(l,r,2)` with cost `+0`

2) **Press with left in place**  
Allowed if `req==-1` or `l==req`  
- `(l,r,0)` with cost `+1`

3) **Press with right in place**  
Allowed if `req==-1` or `r==req`  
- `(l,r,1)` with cost `+1`

4) **Move left to `nl` and press**  
- `nl != r` (vacant)
- not illegal crossed: NOT `(nl==R && r==L)`
- if `req!=-1` then must have `nl==req` (because you press `nl`)
- move cost = `9` if `last in {0,3}` else `3`
- new state `(nl, r, 0)`

5) **Move right to `nr` and press**  
Symmetric:
- `nr != l`
- not crossed: NOT `(l==R && nr==L)`
- if `req!=-1` then `nr==req`
- move cost = `9` if `last in {1,3}` else `3`
- new state `(l, nr, 1)`

6) **Jump** to `(nl,nr)` and press both  
- `nl != nr`
- not crossed: NOT `(nl==R && nr==L)`
- if `req!=-1` then `nl==req or nr==req`
- new state `(nl,nr,3)` with cost `+10`

Finally, among all `dp[N][*][*][*]`, choose the minimal; backtrack with `parent` to output positions per beat.

### Complexity
States: `O(N*4*4*4) = O(64N)`.  
Transitions per state are constant (at most 1 + 2 + 4 + 4 + 16).  
This easily fits time limits.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

struct PrevState {
    int l, r, last;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string s;
    cin >> N >> s;

    // Map button char to index and back
    auto idx = [&](char c) -> int {
        if (c == 'L') return 0;
        if (c == 'U') return 1;
        if (c == 'R') return 2;
        return 3; // 'D'
    };
    const vector<char> ch = {'L', 'U', 'R', 'D'};

    // dp[i][l][r][last]
    // last: 0 left pressed, 1 right pressed, 2 none, 3 both
    vector dp(N + 1, vector(4, vector(4, vector<int>(4, INF))));
    vector parent(N + 1, vector(4, vector(4, vector<PrevState>(4, {-1,-1,-1}))));

    // Initial position: left on L(0), right on R(2), last=none(2)
    dp[0][0][2][2] = 0;

    auto illegal = [&](int l, int r) -> bool {
        if (l == r) return true;        // cannot stand on same button
        if (l == 2 && r == 0) return true; // forbidden crossed position (R,L)
        return false;
    };

    for (int i = 0; i < N; i++) {
        int req = (s[i] == 'N') ? -1 : idx(s[i]);

        for (int l = 0; l < 4; l++) for (int r = 0; r < 4; r++) {
            if (illegal(l, r)) continue;

            for (int last = 0; last < 4; last++) {
                int cur = dp[i][l][r][last];
                if (cur == INF) continue;

                // Helper to relax dp[i+1]
                auto relax = [&](int addCost, int nl, int nr, int nlast) {
                    if (illegal(nl, nr)) return;
                    int nc = cur + addCost;
                    if (nc < dp[i + 1][nl][nr][nlast]) {
                        dp[i + 1][nl][nr][nlast] = nc;
                        parent[i + 1][nl][nr][nlast] = {l, r, last};
                    }
                };

                // 1) Do nothing (only if no required press)
                if (req == -1) {
                    relax(0, l, r, 2);
                }

                // 2) Press with left in place
                if (req == -1 || l == req) {
                    relax(1, l, r, 0);
                }

                // 3) Press with right in place
                if (req == -1 || r == req) {
                    relax(1, l, r, 1);
                }

                // 4) Move left to a vacant button nl and press it
                for (int nl = 0; nl < 4; nl++) {
                    if (nl == r) continue;              // must be vacant
                    if (req != -1 && nl != req) continue; // must press req if any

                    int moveCost = (last == 0 || last == 3) ? 9 : 3;
                    relax(moveCost, nl, r, 0); // left pressed now
                }

                // 5) Move right to a vacant button nr and press it
                for (int nr = 0; nr < 4; nr++) {
                    if (nr == l) continue;
                    if (req != -1 && nr != req) continue;

                    int moveCost = (last == 1 || last == 3) ? 9 : 3;
                    relax(moveCost, l, nr, 1); // right pressed now
                }

                // 6) Jump: choose any two different buttons, press both
                for (int nl = 0; nl < 4; nl++) for (int nr = 0; nr < 4; nr++) {
                    if (nl == nr) continue;
                    if (req != -1 && nl != req && nr != req) continue; // must include req
                    relax(10, nl, nr, 3); // both pressed now
                }
            }
        }
    }

    // Pick best final state
    int best = INF, bl = -1, br = -1, blast = -1;
    for (int l = 0; l < 4; l++) for (int r = 0; r < 4; r++) {
        for (int last = 0; last < 4; last++) {
            if (dp[N][l][r][last] < best) {
                best = dp[N][l][r][last];
                bl = l; br = r; blast = last;
            }
        }
    }

    cout << best << "\n";

    // Reconstruct positions after each beat (1..N)
    vector<pair<int,int>> path;
    int cl = bl, cr = br, clast = blast;
    for (int i = N; i >= 1; i--) {
        path.push_back({cl, cr});
        PrevState p = parent[i][cl][cr][clast];
        cl = p.l; cr = p.r; clast = p.last;
    }
    reverse(path.begin(), path.end());

    for (auto [l, r] : path) {
        cout << ch[l] << ch[r] << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

INF = 10**18

def solve() -> None:
    input = sys.stdin.readline
    N = int(input().strip())
    s = input().strip()

    char_to_idx = {'L': 0, 'U': 1, 'R': 2, 'D': 3}
    idx_to_char = ['L', 'U', 'R', 'D']

    # dp[l][r][last] for current beat index i
    # last: 0 left, 1 right, 2 none, 3 both
    dp = [[[INF] * 4 for _ in range(4)] for __ in range(4)]

    # parent[i][l][r][last] = (pl, pr, plast) for reconstruction
    parent = [[[[None] * 4 for _ in range(4)] for __ in range(4)]
              for ___ in range(N + 1)]

    def illegal(l: int, r: int) -> bool:
        if l == r:
            return True
        if l == 2 and r == 0:  # (R, L) is forbidden
            return True
        return False

    # initial state: L(0), R(2), none(2)
    dp[0][2][2] = 0

    for i in range(N):
        req = -1 if s[i] == 'N' else char_to_idx[s[i]]
        ndp = [[[INF] * 4 for _ in range(4)] for __ in range(4)]

        for l in range(4):
            for r in range(4):
                if illegal(l, r):
                    continue
                for last in range(4):
                    cur = dp[l][r][last]
                    if cur >= INF:
                        continue

                    def relax(add_cost: int, nl: int, nr: int, nlast: int) -> None:
                        if illegal(nl, nr):
                            return
                        nc = cur + add_cost
                        if nc < ndp[nl][nr][nlast]:
                            ndp[nl][nr][nlast] = nc
                            parent[i + 1][nl][nr][nlast] = (l, r, last)

                    # 1) do nothing
                    if req == -1:
                        relax(0, l, r, 2)

                    # 2) press with left in place
                    if req == -1 or l == req:
                        relax(1, l, r, 0)

                    # 3) press with right in place
                    if req == -1 or r == req:
                        relax(1, l, r, 1)

                    # 4) move left and press
                    for nl in range(4):
                        if nl == r:
                            continue
                        if req != -1 and nl != req:
                            continue
                        move_cost = 9 if (last == 0 or last == 3) else 3
                        relax(move_cost, nl, r, 0)

                    # 5) move right and press
                    for nr in range(4):
                        if nr == l:
                            continue
                        if req != -1 and nr != req:
                            continue
                        move_cost = 9 if (last == 1 or last == 3) else 3
                        relax(move_cost, l, nr, 1)

                    # 6) jump and press both
                    for nl in range(4):
                        for nr in range(4):
                            if nl == nr:
                                continue
                            if req != -1 and nl != req and nr != req:
                                continue
                            relax(10, nl, nr, 3)

        dp = ndp

    # best final state
    best = INF
    best_state = None
    for l in range(4):
        for r in range(4):
            for last in range(4):
                if dp[l][r][last] < best:
                    best = dp[l][r][last]
                    best_state = (l, r, last)

    # reconstruct path
    l, r, last = best_state
    path = []
    for i in range(N, 0, -1):
        path.append((l, r))
        l, r, last = parent[i][l][r][last]
    path.reverse()

    # output
    out = [str(best)]
    out += [idx_to_char[l] + idx_to_char[r] for l, r in path]
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()
```

