splay

#include <cstdio>

#include <algorithm>

#define GET_CHILD(P, SIDE) ((SIDE) ? (P)->r : (P)->l)

using namespace std;

struct node {
    int cnt, id;
    bool f;
    node *l, *r;
};

const int N = 100010;

node pool[N];
node* root;
bool f;

void update(node* p);
void push_down(node* p);
void rotate(node*& p, bool side);
void splay(node*& p, int x);
void order(node* p);

int main() {
    int n, m, l, r;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        pool[i].id = i;
        pool[i].cnt = n - i + 1;
        if (i != n)
            pool[i].r = pool + i + 1;
    }
    root = pool + 1;
    while (m--) {
        scanf("%d%d", &l, &r);
        if (l == 1) {
            if (r == n) {
                root->f = !root->f;
                continue;
            }
            splay(root, r + 1);
            root->l->f = !root->l->f;
            continue;
        }
        splay(root, l - 1);
        if (r == n) {
            root->r->f = !root->r->f;
            continue;
        }
        splay(root, r + 1);
        root->l->r->f = !root->l->r->f;
    }
    order(root);
    putchar('\n');
    return 0;
}

inline void rotate(node*& p, bool side) {
    push_down(p);
    node* son = GET_CHILD(p, side);
    push_down(son);
    GET_CHILD(p, side) = GET_CHILD(son, !side);
    GET_CHILD(son, !side) = p;
    update(p);
    p = son;
    update(p);
}

inline void push_down(node* p) {
    if (p->f)
        swap(p->l, p->r);
    if (p->l)
        p->l->f ^= p->f;
    if (p->r)
        p->r->f ^= p->f;
    p->f = false;
}

inline void update(node* p) {
    p->cnt = 1;
    if (p->l)
        p->cnt += p->l->cnt;
    if (p->r)
        p->cnt += p->r->cnt;
}

void splay(node*& p, int x) {
    push_down(p);
    if (p->l) {
        if (p->l->cnt >= x) {
            splay(p->l, x);
            rotate(p, 0);
            return;
        }
        x -= p->l->cnt;
    }
    if (x == 1)
        return;
    splay(p->r, x - 1);
    rotate(p, 1);
}

void order(node* p) {
    if (!p)
        return;
    push_down(p);
    order(p->l);
    if (f)
        putchar(' ');
    printf("%d", p->id);
    f = true;
    order(p->r);
}