<|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

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 **at most 1** button, so for a beat with requirement `req`, it suffices that **the pressed set contains `req`**.

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, ending with left at `l`, right at `r`, and `last`.

Initialize:
`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`. New state: `(l,r,2)`, cost +0.

2) **Press with left in place**: allowed if `req==-1` or `l==req`. New state: `(l,r,0)`, cost +1.

3) **Press with right in place**: allowed if `req==-1` or `r==req`. New state: `(l,r,1)`, 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`
   - move cost = `9` if `last in {0,3}` else `3`
   - new state `(nl, r, 0)`

5) **Move right to `nr` and press** (symmetric to 4).

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

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. Easily fits time limits.

---

## 4. C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int inf = (int)1e9 + 42;

int n;
string s;

void read() {
    cin >> n;
    cin >> s;
}

void solve() {
    // The problem fundamentally isn't hard - we can use dynamic programming
    // that tracks the position of the two legs as part of the state, if they
    // pressed the buttons, and where in the beat are we currently at. The main
    // part is all the details about the transitions. One easy to miss detail is
    // that we could make some moves even during a 'N' character.

    map<char, int> char_to_idx = {{'L', 0}, {'U', 1}, {'R', 2}, {'D', 3}};
    vector<char> idx_to_char = {'L', 'U', 'R', 'D'};

    vector<vector<vector<vector<int>>>> dp(
        n + 1, vector<vector<vector<int>>>(
                   4, vector<vector<int>>(4, vector<int>(4, inf))
               )
    );

    struct State {
        int left, right, last_pressed;
    };
    vector<vector<vector<vector<State>>>> parent(
        n + 1, vector<vector<vector<State>>>(
                   4, vector<vector<State>>(4, vector<State>(4, {-1, -1, -1}))
               )
    );

    dp[0][0][2][2] = 0;

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

        for(int left = 0; left < 4; left++) {
            for(int right = 0; right < 4; right++) {
                if(left == right) {
                    continue;
                }

                for(int last = 0; last < 4; last++) {
                    if(dp[i][left][right][last] == inf) {
                        continue;
                    }

                    int cur_cost = dp[i][left][right][last];

                    auto update = [&](int cost, int new_left, int new_right,
                                      int new_last) {
                        int new_cost = cur_cost + cost;
                        if(new_cost <
                           dp[i + 1][new_left][new_right][new_last]) {
                            dp[i + 1][new_left][new_right][new_last] = new_cost;
                            parent[i + 1][new_left][new_right][new_last] = {
                                left, right, last
                            };
                        }
                    };

                    if(req == -1) {
                        update(0, left, right, 2);
                    }
                    if(req == -1 || left == req) {
                        update(1, left, right, 0);
                    }
                    if(req == -1 || right == req) {
                        update(1, left, right, 1);
                    }

                    for(int new_pos = 0; new_pos < 4; new_pos++) {
                        if(new_pos == right) {
                            continue;
                        }
                        if(new_pos == 2 && right == 0) {
                            continue;
                        }
                        if(req != -1 && new_pos != req) {
                            continue;
                        }
                        update(
                            (last == 0 || last == 3) ? 9 : 3, new_pos, right, 0
                        );
                    }

                    for(int new_pos = 0; new_pos < 4; new_pos++) {
                        if(new_pos == left) {
                            continue;
                        }
                        if(left == 2 && new_pos == 0) {
                            continue;
                        }
                        if(req != -1 && new_pos != req) {
                            continue;
                        }
                        update(
                            (last == 1 || last == 3) ? 9 : 3, left, new_pos, 1
                        );
                    }

                    for(int new_left = 0; new_left < 4; new_left++) {
                        for(int new_right = 0; new_right < 4; new_right++) {
                            if(new_left == new_right) {
                                continue;
                            }
                            if(new_left == 2 && new_right == 0) {
                                continue;
                            }
                            if(req != -1 && new_left != req &&
                               new_right != req) {
                                continue;
                            }
                            update(10, new_left, new_right, 3);
                        }
                    }
                }
            }
        }
    }

    int best_cost = inf;
    int best_left = -1, best_right = -1, best_last = -1;
    for(int left = 0; left < 4; left++) {
        for(int right = 0; right < 4; right++) {
            for(int last = 0; last < 4; last++) {
                if(dp[n][left][right][last] < best_cost) {
                    best_cost = dp[n][left][right][last];
                    best_left = left;
                    best_right = right;
                    best_last = last;
                }
            }
        }
    }

    cout << best_cost << '\n';

    vector<pair<int, int>> path;
    int cur_left = best_left, cur_right = best_right, cur_last = best_last;
    for(int i = n; i > 0; i--) {
        path.push_back({cur_left, cur_right});
        State prev = parent[i][cur_left][cur_right][cur_last];
        cur_left = prev.left;
        cur_right = prev.right;
        cur_last = prev.last_pressed;
    }

    reverse(path.begin(), path.end());

    for(auto [left, right]: path) {
        cout << idx_to_char[left] << idx_to_char[right] << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation

```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)]

    # 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 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 nl == nr:
                            return
                        if nl == 2 and nr == 0:
                            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()
```
