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

187. Twist and whirl - want to cheat
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



A well-known sharper I*** invented a new way to swindle people. There are N thimbles on the table, and there is a small ball with the number under each of them. The balls are numbered with numbers from 1 to N from left to right. At one operation I*** changes the order of some subsequence of successive thimbles to the opposite. Your task is to find the order of numbers (from left to right) in sequence after all of his manipulations. The total number of manipulations is M.

Input
The first line contains two integer numbers N and M (1<=N<=130000, 1<=M<=2000) separated by a space. Each of the following M lines contains two integer numbers Pi, Qi (1<=Pi<=Qi<=N) - positions of the leftmost and rightmost thimbles in rotated sequence.

Output
Output the sequence of N numbers - the numbers of balls in the thimbles from left to right.

Sample test(s)

Input
Test #1
5 2
1 3
4 5

Test #2
5 2
1 4
2 5

Output
Test #1
3 2 1 5 4

Test #2
4 5 1 2 3
Author:	Michael R. Mirzayanov
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

<|response|>
1. Abridged problem statement
Given an initial sequence of thimbles numbered 1 through N, perform M operations. Each operation specifies indices l and r, and you must reverse the subarray from position l to position r (inclusive). After all operations, output the final sequence.

2. Key observations
- A single reverse of a subarray of length L takes O(L) time if done naively on an array. In the worst case, repeating M times gives O(N·M), which can be up to 2.6·10^8 element moves (too slow under 0.25 s in C++).
- We need a data structure that supports:
  • splitting the sequence at an arbitrary position in O(log N)
  • merging two sequences in O(log N)
  • applying "reverse" to an entire subsequence in O(1) (lazy propagation)
- An implicit treap (Cartesian tree by position) with a lazy "reverse" flag satisfies these requirements.

3. Full solution approach
We represent the sequence as an implicit treap, where the in-order traversal of the treap nodes yields the current sequence. Each node stores:
  • key: the current element value (initially 1…N)
  • prior: a random priority for heap ordering
  • size: size of the subtree rooted at this node
  • lazy: a "reverse this subtree" flag (ReverseLazy)
  • left, right: child pointers

We maintain these invariants:
  - The tree is a max-heap by priority.
  - In-order traversal corresponds to the sequence order.
  - `size` is always correct for each subtree.
  - If the reverse flag is set at a node, its children are logically swapped, and the flag should be pushed down when accessing that node.

Key operations:
  • pull(node): recalculate node->size = 1 + size(left) + size(right) (and the subtree monoid; here the monoid is empty).
  • push(node): if the reverse flag is set, swap(node->left, node->right), propagate the flag to children, clear the node's flag.
  • split_by_size(node, k): split the treap into (L, R) so that L contains the first k elements (by in-order) and R contains the rest.
  • merge(A, B): merge two treaps A and B assuming all elements in A come before those in B in in-order.

The treap is implemented as a generic template parameterized by a monoid (an empty monoid here) and a lazy tag type (ReverseLazy). The initial treap is built in O(N) from the already-sorted [1..N] array using the Cartesian-tree stack construction.

To reverse the subarray [l,r]:
  1. Split root into (A, BC) at k = l−1.
  2. Split BC into (B, C) at k = r−l+1.
  3. Toggle B's reverse flag.
  4. Merge back: root = merge(A, merge(B, C)).

Each split/merge takes O(log N) on average, so total is O((N + M) log N), which is efficient for N up to 130 000 and M up to 2000.

4. C++ implementation
```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(random_device{}());
        // FOR DEBUG:
        // 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 TreapWithLazy = Treap<int, EmptyMonoid, EmptyMonoid::merge,
                            ReverseLazy<EmptyMonoid>>;
using Node = TreapWithLazy::Node;


int n, q;

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

void walk(Node* node, vector<int>& res) {
    if(node == nullptr) {
        return;
    }
    node->push();
    walk(node->left, res);
    res.push_back(node->key);
    walk(node->right, res);
}

void solve() {
    // - Maintain the permutation 1..n in an implicit treap keyed by position,
    //   with a lazy "reverse this subtree" flag (ReverseLazy) that swaps the
    //   left/right children and propagates down on push.
    //
    // - Each query (l, r) reverses the subsegment: split off the first l-1
    //   elements, then split the remainder into the [l, r] block and the tail,
    //   toggle the reverse flag on the middle block, and merge the three parts
    //   back together.
    //
    // - After all queries, an in-order walk (pushing lazies along the way)
    //   yields the final left-to-right order.

    vector<pair<int, EmptyMonoid>> a;
    for(int i = 0; i < n; i++) {
        a.push_back({i + 1, EmptyMonoid()});
    }

    TreapWithLazy treap(a);

    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        auto [t1, t2] = split_by_size(treap.root, l - 1);
        auto [t3, t4] = split_by_size(t2, r - l + 1);
        t3->lazy.should_reverse ^= true;
        treap.root = merge(t1, merge(t3, t4));
    }

    vector<int> ans;
    walk(treap.root, ans);
    cout << ans << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys
import threading
import random

sys.setrecursionlimit(1 << 25)

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    # Node of the implicit treap
    class Node:
        __slots__ = ('val','prior','size','rev','l','r')
        def __init__(self, v):
            self.val = v
            self.prior = random.randrange(1 << 30)
            self.size = 1
            self.rev = False
            self.l = None
            self.r = None

    def get_size(t):
        return t.size if t else 0

    def update(t):
        if not t:
            return
        t.size = 1 + get_size(t.l) + get_size(t.r)

    def push(t):
        if t and t.rev:
            # swap children
            t.l, t.r = t.r, t.l
            # toggle flags
            if t.l:
                t.l.rev = not t.l.rev
            if t.r:
                t.r.rev = not t.r.rev
            t.rev = False

    # Split into (left, right) where left has first k elements
    def split(t, k):
        if not t:
            return (None, None)
        push(t)
        if get_size(t.l) >= k:
            left, t.l = split(t.l, k)
            update(t)
            return (left, t)
        else:
            t.r, right = split(t.r, k - get_size(t.l) - 1)
            update(t)
            return (t, right)

    # Merge two treaps a and b
    def merge(a, b):
        if not a or not b:
            return a or b
        push(a)
        push(b)
        if a.prior > b.prior:
            a.r = merge(a.r, b)
            update(a)
            return a
        else:
            b.l = merge(a, b.l)
            update(b)
            return b

    # Build initial treap by merging nodes 1..n
    root = None
    for v in range(1, n+1):
        node = Node(v)
        root = merge(root, node)

    # Perform m reversals
    for _ in range(m):
        l = int(next(it))
        r = int(next(it))
        A, BC = split(root, l-1)
        B, C  = split(BC, r-l+1)
        if B:
            B.rev = not B.rev
        root = merge(merge(A, B), C)

    # In-order traversal to collect result
    ans = []
    def inorder(t):
        if not t:
            return
        push(t)
        inorder(t.l)
        ans.append(str(t.val))
        inorder(t.r)

    inorder(root)
    print(' '.join(ans))

if __name__ == "__main__":
    threading.Thread(target=main).start()
```

Explanation of the main parts:
- We use an implicit treap: a randomized balanced BST where the "key" is the position in the sequence (implicit by subtree sizes).
- `split`/`split_by_size` partition the treap by position, `merge` joins two treaps.
- To reverse a subarray, we split out that segment, toggle its lazy `rev` flag (which will swap children when needed), then merge everything back.
- Final in-order traversal prints the resulting sequence in O(N).
