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

397. Text Editor
Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The simplest text editor "Open Word" allows to create and edit only one word. The editor processes keys 'a' -- 'z', and also 'L' (to the left) and 'R' (to the right). After starting his work the editor immediately creates an empty word and sets its cursor to the left-most position. When one of keys 'a' -- 'z' is pressed, the text editor inserts corresponding symbol just after the cursor. After that a cursor moves one position to the right in such a way that it is placed just after new symbol. When key 'L' or 'R' is pressed, the cursor moves one position to the left or to the right respectively. If the cursor can't be moved because it is placed at the left-most or right-most position the command is ignored. Developers of "Open Word" didn't think about the effectiveness so the editor is working slowly if a lot of keys have been pressed.

Your task is to write a program that can process a sequence of key pressings emulating this editor and output result string.

Input
The input file contains one string which consists of symbols 'a' -- 'z', 'L' and 'R'. The string length is not less than 1 and doesn't exceed 106.

Output
Write a required string to the output file.

Example(s)
sample input
sample output
abLcd
acdb

sample input
sample output
icpLLLLLacmRRRRRRRRRRRRc
acmicpc

<|response|>
## 1. Abridged problem statement

You start with an empty word and a cursor at position 0. You receive a sequence of key presses, each being:
- a lowercase letter 'a'-'z': insert that letter immediately after the cursor, then move the cursor right by one.
- 'L': move the cursor left by one (if not already at the beginning).
- 'R': move the cursor right by one (if not already at the end).

After processing all key presses, output the final word.

---

## 2. Key observations

- Directly inserting into the middle of a dynamic array is O(N) per operation, leading to O(N^2) overall for up to 10^6 operations.
- A doubly linked list supports O(1) insertion before any iterator position, and O(1) iterator increment/decrement.
- We keep an iterator pointing to the current "cursor" position (the element before which the next character will be inserted, i.e., `ans.end()` initially). Moving left decrements the iterator; moving right increments it.
- Equivalently, two stacks (left/right of cursor) give the same O(N) behavior.

---

## 3. Full solution approach

Read the input string. Maintain a `std::list<char>` and an iterator `it` initialized to `ans.begin()` (which equals `ans.end()` for an empty list). For each character:
- If letter: `ans.insert(it, c)` (inserts before `it`, so cursor stays at `it` which is now after the new character).
- If `'L'` and `it != ans.begin()`: `--it`.
- If `'R'` and `it != ans.end()`: `++it`.

At the end, iterate over `ans` and print each character.

This runs in O(N) time and O(N) space.

---

## 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;
};

string s;

void read() {
    cin >> s;
}

void solve() {
    list<char> ans;
    auto it = ans.begin();

    for(auto c: s) {
        if(c == 'L') {
            if(it != ans.begin()) {
                it--;
            }
        } else if(c == 'R') {
            if(it != ans.end()) {
                it++;
            }
        } else {
            ans.insert(it, c);
        }
    }

    for(auto c: ans) {
        cout << c;
    }
    cout << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation

```python
import sys
def main():
    data = sys.stdin.read().strip()
    # We'll treat 'left' and 'right' as stacks.
    left = []   # characters to the left of the cursor
    right = []  # characters to the right of the cursor

    for c in data:
        if c == 'L':
            if left:
                # Move one char from left to right (cursor moves left)
                right.append(left.pop())
        elif c == 'R':
            if right:
                # Move one char from right to left (cursor moves right)
                left.append(right.pop())
        else:
            # Letter insertion: push onto left (cursor moves right)
            left.append(c)

    # The final text is left + reversed(right)
    # right is in reverse order of actual text to its right
    sys.stdout.write(''.join(left) + ''.join(reversed(right)))

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