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

271. Book Pile
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



There is a pile of N books on the table. Two types of operations are performed over this pile:
- a book is added to the top of the pile,
- top K books are rotated. If there are less than K books on the table, the whole pile is rotated.
First operation is denoted as ADD(S) where S is the name of the book, and the second operations is denoted as ROTATE.
The maximum number of books is no more than 40000. All book names are non-empty sequences of no more than 3 capital Latin letters. The names of the books can be non-unique.

Input
The first line of input file contains 3 integer numbers N, M, K (0 <= N <= 40000; 0 <= M <= 100000; 0 <= K <= 40000). The following N lines are the names of the books in the pile before performing any operations. The book names are given in order from top book to bottom. Each of the following M lines contains the operation description.

Output
Output the sequence of books names in the pile after performing all operations. First line corresponds to the top book.

Sample test(s)

Input
2 3 2
A
B
ADD(C)
ROTATE
ADD(D)

Output
D
A
C
B
Author:	Michael R. Mirzayanov
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
1. Abridged Problem Statement  
You have a pile (stack) of books, initially N books given from top to bottom. You then perform M operations of two types:  
- **ADD(S)**: push a new book named S onto the top of the pile.  
- **ROTATE**: reverse the order of the top K books (if fewer than K books remain, reverse the whole pile).  
After all operations, output the final pile from top to bottom.  
Constraints:  
• 0 ≤ N ≤ 40000, 0 ≤ M ≤ 100000, 0 ≤ K ≤ 40000  
• Book names are 1–3 uppercase letters; duplicates allowed.  

2. Key Observations  
- A naïve array or list reversal of the top K books per ROTATE would cost O(K) each, leading to O(M·K) worst-case (up to 4·10^9), too slow.  
- We need O(1) or amortized O(1) per operation.  
- Notice that K is fixed throughout, so we only ever reverse a prefix of size “up to K.”  
- We can keep the top K books in one data structure (“prefix”) and the remaining books below in another (“suffix”), maintaining the invariant that prefix.size() ≤ K.  
- By storing a boolean flag rev on the prefix, we can “reverse” it logically in O(1) by flipping the flag, and push/pop at its ends in O(1) even under reversal.  
- Any time prefix grows beyond K (after an ADD), we move its logical back element into the front of suffix, keeping prefix.size() ≤ K.  

3. Full Solution Approach  
Maintain two deques of strings, prefix and suffix, plus a boolean rev indicating whether prefix is logically reversed:  
Initialization:  
  - Read the N initial books into a single deque all_books (front = top).  
  - Move elements from the back of all_books into the front of suffix until all_books.size() ≤ K.  
  - Let prefix = all_books (remaining ≤ K books), and set rev = false.  

Operations:  
  - ADD(S):  
      • To push S onto the top of the pile, we insert S into the logical front of prefix:  
          if rev==false, prefix.push_front(S); else prefix.push_back(S).  
      • If prefix.size() > K, we pop its logical back (if rev==false pop_back(), else pop_front()) and push that book to the front of suffix.  
  - ROTATE:  
      • Flip rev = !rev. This logically reverses prefix in O(1).  

Final Output:  
  - First output prefix in correct order: if rev==false, iterate from front to back; else from back to front.  
  - Then output suffix from front to back (always in normal order).  

All operations are O(1) amortized, so total O(N+M).  

4. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/data_structures/treap_lazy.hpp>

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

template<
    class KeyT, class T, T (*merge_func)(T, T), class LazyT, uint64_t (*rng)()>
struct TreapNode {
    KeyT key;
    T data, subtree;
    uint64_t prior;
    size_t size;
    TreapNode *left, *right;
    LazyT lazy;

    TreapNode(KeyT key, T data)
        : key(key), data(data), left(nullptr), right(nullptr), size(1) {
        prior = rng();
        lazy = LazyT();
    }

    void pull() {
        subtree = data;
        size = 1;
        if(left) {
            left->push();
            subtree = merge_func(left->subtree, subtree);
            size += left->size;
        }
        if(right) {
            right->push();
            subtree = merge_func(subtree, right->subtree);
            size += right->size;
        }
    }

    void push() { lazy.apply_lazy(this); }

    friend void push_lazy(TreapNode* t) {
        if(t) {
            t->push();
        }
    }

    friend pair<TreapNode*, TreapNode*> split(TreapNode* t, KeyT key) {
        if(!t) {
            return {nullptr, nullptr};
        }

        t->push();
        if(key < t->key) {
            auto [left, t_left] = split(t->left, key);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split(t->right, key);
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend pair<TreapNode*, TreapNode*> split_by_size(
        TreapNode* t, size_t size
    ) {
        if(!t) {
            return {nullptr, nullptr};
        }

        t->push();
        size_t left_size = t->left ? t->left->size : 0;
        if(left_size >= size) {
            auto [left, t_left] = split_by_size(t->left, size);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split_by_size(
                t->right, size - 1 - left_size
            );
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend TreapNode* merge(TreapNode* l, TreapNode* r) {
        push_lazy(l);
        push_lazy(r);
        if(!l || !r) {
            return l ? l : r;
        } else if(l->prior > r->prior) {
            l->right = merge(l->right, r);
            l->pull();
            return l;
        } else {
            r->left = merge(l, r->left);
            r->pull();
            return r;
        }
    }

    friend TreapNode* unordered_merge(TreapNode* l, TreapNode* r) {
        push_lazy(l);
        push_lazy(r);
        if(!l) {
            return r;
        }
        if(!r) {
            return l;
        }
        if(l->prior < r->prior) {
            swap(l, r);
        }
        auto [t1, t2] = split(r, l->key);
        l->left = unordered_merge(l->left, t1);
        l->right = unordered_merge(l->right, t2);
        l->pull();
        return l;
    }

    friend void insert_in(TreapNode*& t, TreapNode* it) {
        if(!t) {
            t = it;
        } else {
            t->push();
            if(it->prior > t->prior) {
                auto [t1, t2] = split(t, it->key);
                it->left = t1;
                it->right = t2;
                t = it;
            } else {
                insert_in(it->key < t->key ? t->left : t->right, it);
            }
        }
        t->pull();
    }

    friend TreapNode* erase_from(
        TreapNode*& t, KeyT key, bool delete_node = false
    ) {
        t->push();
        T return_data;
        if(t->key == key) {
            auto tmp = t;
            t = merge(t->left, t->right);

            return_data = tmp->data;
            if(delete_node) {
                delete tmp;
            }
        } else {
            return_data =
                erase_from(key < t->key ? t->left : t->right, key, delete_node);
        }
        if(t) {
            t->pull();
        }
        return return_data;
    }
};

template<class KeyT, class T, T (*merge_func)(T, T), class LazyT>
class Treap {
  public:
    static uint64_t rng() {
        static mt19937_64 static_rng(42);
        return static_rng();
    }

    using Node = TreapNode<KeyT, T, merge_func, LazyT, Treap::rng>;

    void _pull_all(Node* t) {
        if(t) {
            t->push();
            _pull_all(t->left);
            _pull_all(t->right);
            t->pull();
        }
    }

    Node* root;

    Treap() { root = nullptr; }
    Treap(const vector<pair<KeyT, T>>& a) { build_cartesian_tree(a); }

    void build_cartesian_tree(const vector<pair<KeyT, T>>& a) {
        vector<Node*> st;

        function<Node*(Node*)> recycle_stack = [&](Node* last) {
            Node* new_last = st.back();
            st.pop_back();
            new_last->right = last;
            return new_last;
        };

        for(const auto& [key, val]: a) {
            Node* new_node = new Node(key, val);
            Node* last = nullptr;
            while(!st.empty() && st.back()->prior < new_node->prior) {
                last = recycle_stack(last);
            }

            new_node->left = last;
            st.push_back(new_node);
        }

        root = nullptr;
        while(!st.empty()) {
            root = recycle_stack(root);
        }

        _pull_all(root);
    }

    void insert(KeyT key, T data) {
        Node* new_node = new Node(key, data);
        insert_in(root, new_node);
    }

    void erase(KeyT key) { return erase_from(root, key); }

    friend Treap<KeyT, T, merge_func, LazyT> merge_treaps(
        Treap<KeyT, T, merge_func, LazyT> l, Treap<KeyT, T, merge_func, LazyT> r
    ) {
        Treap<KeyT, T, merge_func, LazyT> res;
        res.root = unordered_merge(l.root, r.root);
        return res;
    }
};

template<class T>
struct ReverseLazy {
    bool should_reverse;

    ReverseLazy() { should_reverse = false; }

    template<class G, uint64_t (*rng)(), T (*merge_func)(T, T)>
    void apply_lazy(TreapNode<G, T, merge_func, ReverseLazy, rng>* node) {
        if(!node || !should_reverse) {
            return;
        }

        swap(node->left, node->right);
        if(node->left) {
            node->left->lazy.should_reverse ^= true;
        }
        if(node->right) {
            node->right->lazy.should_reverse ^= true;
        }

        should_reverse = false;
    }
};

struct EmptyMonoid {
    static EmptyMonoid merge(EmptyMonoid a, EmptyMonoid b) {
        return EmptyMonoid();
    }
};

using TreapWithReverse =
    Treap<string, EmptyMonoid, EmptyMonoid::merge, ReverseLazy<EmptyMonoid>>;

int n, m, k;
vector<string> names;

void read() {
    cin >> n >> m >> k;
    names.resize(n);
    cin >> names;
}

void solve() {
    // Maintain the book pile as an implicit treap whose in-order traversal is
    // the pile from top to bottom; the stored string is the book name and the
    // BST key is unused, all positional work is done via size-splits and
    // priority merges.
    //
    // - Build the initial treap as a cartesian tree over the N starting names.
    //
    // - ADD(S): create a node for S and merge it at the front, putting the new
    //   book on top.
    //
    // - ROTATE: split off the first k nodes, toggle a lazy reverse flag on that
    //   prefix, then merge back. The ReverseLazy flag swaps children on push,
    //   so the top k books appear in reversed order.
    //
    // - Finally an in-order DFS (pushing pending reversals) prints the pile.

    vector<pair<string, EmptyMonoid>> init_treap_data;
    for(auto name: names) {
        init_treap_data.emplace_back(name, EmptyMonoid());
    }

    TreapWithReverse treap(init_treap_data);

    while(m--) {
        string txt;
        cin >> txt;
        if(txt[0] == 'A') {
            string name;
            int state = 0;
            for(char c: txt) {
                if(c == '(') {
                    state++;
                } else if(c == ')') {
                    state++;
                } else if(state == 1) {
                    name.push_back(c);
                }
            }

            auto new_node = new TreapWithReverse::Node(name, EmptyMonoid());
            treap.root = merge(new_node, treap.root);
        } else {
            auto [t1, t2] = split_by_size(treap.root, k);
            if(t1) {
                t1->lazy.should_reverse ^= true;
            }
            treap.root = merge(t1, t2);
        }
    }

    function<void(TreapWithReverse::Node*)> dfs =
        [&](TreapWithReverse::Node* node) {
            if(node) {
                node->push();
                dfs(node->left);
                cout << node->key << "\n";
                dfs(node->right);
            }
        };

    dfs(treap.root);
}

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 with Detailed Comments  

```python
import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))

    # Read initial pile: top at front
    all_books = deque()
    for _ in range(N):
        all_books.append(next(it))

    # Split off the bottom (size-K) into suffix
    suffix = deque()
    while len(all_books) > K:
        suffix.appendleft(all_books.pop())
    prefix = all_books  # up to K books
    rev = False         # prefix normal if False, reversed if True

    # Helpers to treat prefix with logical reversal
    def push_front(s):
        if not rev:
            prefix.appendleft(s)
        else:
            prefix.append(s)
    def pop_back():
        if not rev:
            return prefix.pop()
        else:
            return prefix.popleft()

    # Process operations
    for _ in range(M):
        op = next(it)
        if op[0] == 'A':   # ADD(...)
            # extract book name
            name = op[4:-1]
            push_front(name)
            # keep prefix size ≤ K
            if len(prefix) > K:
                moved = pop_back()
                suffix.appendleft(moved)
        else:  # ROTATE
            rev = not rev

    # Output final pile
    out = []
    if not rev:
        out.extend(prefix)
    else:
        out.extend(reversed(prefix))
    out.extend(suffix)

    sys.stdout.write("\n".join(out))

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

Explanation of Key Steps:  
- We never pay O(K) per ROTATE; flipping the boolean rev reverses our view in O(1).  
- By keeping prefix.size() ≤ K, every ADD that overflows prefix does one O(1) move into suffix.  
- Final printing takes O(N) to traverse prefix+suffix once.  
This yields O(N + M) time and O(N) extra memory, comfortably within the problem limits.