1. Abridged Problem Statement
Given an initial sequence [1, 2, …, N], perform M operations of the form "reverse the subarray from positions l to r" and output the final sequence. Constraints: N≤130 000, M≤2000.

2. Detailed Editorial
We need a data structure that supports reversing arbitrary contiguous subranges in a sequence of size up to 130 000, M up to 2000, and finally outputting the sequence. Doing each reverse in O(r−l+1) time on an array could be as bad as O(N × M)=2.6×10^8 element moves, which may be too slow in low-level languages.

An implicit treap (a randomized balanced binary search tree keyed by position) with lazy propagation of "reverse" flags handles this in O((N + M) log N) time:

1. Representation
   - Each node stores:
     · its key (the value 1…N),
     · its subtree size,
     · a random priority,
     · a lazy "reverse" tag,
     · pointers left, right.

2. Invariants
   - In-order traversal yields the sequence in current order.
   - The tree is heap-ordered by priority.
   - The implicit "key" is the in-order index; we never store it explicitly.

3. Operations
   - `push(node)`: if the node's reverse tag is set, swap left/right, push the reverse flag to children, clear the node's flag.
   - `pull(node)`: recalculate node→size = 1 + size(left) + size(right) (and the subtree monoid, unused here).
   - `split_by_size(t, k)`: split tree t into (L, R) so that L contains the first k elements in in-order, R the rest. Implementation: push(t), let left_size = size(t.left). If k ≤ left_size, recurse left; else recurse right with k−left_size−1.
   - `merge(A, B)`: push both, compare priorities: the root is whichever has higher priority; merge its right (or left) child appropriately; then pull.

4. Reversing a range [l, r]:
   - Split root into (A, BC) at l−1.
   - Split BC into (B, C) at (r−l+1).
   - Toggle B's reverse tag.
   - Merge back: root = merge(A, merge(B, C)).

5. Final output
   - In-order traversal of the treap.

The implementation uses a generic treap template parameterized by a monoid (here an empty monoid, since only the keys matter) and a lazy tag type (here ReverseLazy). The initial treap is built in O(N) from the already-sorted array using the Cartesian-tree stack construction. Time per split/merge is O(log N), so total O((N + M) log N) with very high probability.

3. 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(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;
}
```

4. Python Solution
```python
import sys
import threading
import random
sys.setrecursionlimit(10**7)

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

    # Node of an implicit treap
    class Node:
        __slots__ = ('val','prio','left','right','size','rev')
        def __init__(self, v):
            self.val = v
            self.prio = random.randrange(1<<30)
            self.left = None
            self.right = None
            self.size = 1
            self.rev = False

    # recalc size
    def pull(t):
        if not t: return
        t.size = 1
        if t.left:  t.size += t.left.size
        if t.right: t.size += t.right.size

    # push down lazy reverse flag
    def push(t):
        if t and t.rev:
            t.rev = False
            # swap children
            t.left, t.right = t.right, t.left
            # toggle children flags
            if t.left:  t.left.rev  ^= True
            if t.right: t.right.rev ^= True

    # split treap t into (L, R),
    # where L has first k elements
    def split(t, k):
        if not t:
            return (None, None)
        push(t)
        left_size = t.left.size if t.left else 0
        if k <= left_size:
            # all desired in left subtree
            L, R = split(t.left, k)
            t.left = R
            pull(t)
            return (L, t)
        else:
            # some in left, current, some in right
            L, R = split(t.right, k - left_size - 1)
            t.right = L
            pull(t)
            return (t, R)

    # merge two treaps L and R
    def merge(L, R):
        if not L or not R:
            return L or R
        # push flags before comparing
        push(L); push(R)
        if L.prio > R.prio:
            L.right = merge(L.right, R)
            pull(L)
            return L
        else:
            R.left = merge(L, R.left)
            pull(R)
            return R

    # build initial treap by successive merges
    root = None
    for x in range(1, n+1):
        node = Node(x)
        root = merge(root, node)

    # process reversals
    for _ in range(m):
        l = int(next(it))
        r = int(next(it))
        # split into A=[1..l-1], BC=[l..n]
        A, BC = split(root, l-1)
        # split BC into B=[l..r], C=[r+1..n]
        B, C  = split(BC, r-l+1)
        # toggle reverse flag on B
        if B:
            B.rev ^= True
        # reassemble
        root = merge(merge(A, B), C)

    # in-order traversal to collect result
    res = []
    def inorder(t):
        if not t: return
        push(t)
        inorder(t.left)
        res.append(t.val)
        inorder(t.right)
    inorder(root)
    print(' '.join(map(str, res)))

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

5. Compressed Editorial
Use an implicit treap with random priorities, storing subtree sizes and a lazy "reverse" bit. To reverse [l,r], split at l−1 and at r, toggle the lazy bit on the middle treap, then merge back. Each operation costs O(log N), total O((N+M) log N).
