#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N];
int root, num, fa[N], cnt[N], val[N], tag[N], sz[N], son[N][2];
void update(int x){
    sz[x] = cnt[x] + sz[son[x][0]] + sz[son[x][1]];
}
void push(int x){
    if(tag[x] == 0)
        return;
    tag[son[x][0]] ^= 1;
    tag[son[x][1]] ^= 1;
    swap(son[x][0], son[x][1]);
    tag[x] = 0;
}
int build(int l, int r, int fat){
    if(l > r)
        return 0;
    int mid = (l + r) / 2;
    int temp = ++num;
    fa[temp] = fat;
    cnt[temp] = 1;
    val[temp] = a[mid];
    son[temp][0] = build(l, mid - 1, temp);
    son[temp][1] = build(mid + 1, r, temp);
    update(temp);
    return temp;
}
bool which(int x){
    return x == son[fa[x]][1];
}
void zz(int x){
    int f = fa[x], ff = fa[f];
    push(x);
    push(f);
    int zy = which(x);
    son[f][zy] = son[x][zy ^ 1];
    fa[son[f][zy]] = f;
    fa[f] = x;
    fa[x] = ff;
    son[x][zy ^ 1] = f;
    if(ff != x)
        son[ff][son[ff][1] == f] = x;
    update(f);
}
void splay(int x, int y){
    for(int ff; (ff = fa[x]) != y; zz(x))
        if(fa[ff] != y){
            if(which(x) == which(ff))
                zz(ff);
            else
                zz(x);
        }
    if(y == 0)
        root = x;
}
int getvbr(int rk){
    int x = root;
    while(1){
        push(x);
        if(rk <= sz[son[x][0]])
            x = son[x][0];
        else{
            rk -= sz[son[x][0]] + cnt[x];
            if(rk <= 0)
                return x;
            x = son[x][1];
        }
    }
}
void rev(int x, int y){
    int l = getvbr(x - 1), r = getvbr(y + 1);
    splay(l, 0);
    splay(r, l);
    tag[son[son[root][1]][0]] ^= 1;
}
void print(int x){
    push(x);
    if(son[x][0])
        print(son[x][0]);
    if(val[x] != -1e9 && val[x] != 1e9)
        printf("%d ", val[x]);
    if(son[x][1])
        print(son[x][1]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n + 2; i++){
        if(i == 1)
            a[i] = -1e9;
        else if(i == n + 2)
            a[i] = 1e9;
        else
            a[i] = i - 1;
    }
    root = build(1, n + 2, 0);
    print(root);
    puts("");
    while(m--){
        int x, y;
        scanf("%d%d", &x, &y);
        rev(x + 1, y + 1); 
    }
    print(root);
    puts("");
    return 0;
}

1: input:

100 100
47 91
11 15
45 57
35 68
20 90
2 23
45 83
12 76
55 57
69 75
17 21
1 5
9 86
33 63
11 23
54 63
4 72
37 89
16 95
43 44
51 72
13 13
12 32
15 72
63 72
24 75
54 69
7 10
13 96
22 25
7 31
36 66
29 52
86 87
56 62
29 65
24 54
29 85
3 22
39 88
72 79
54 62
52 75
75 76
31 91
6 26
56 74
74 86
8 78
47 50
68 99
27 100
31 78
1 80
45 92
44 72
1 87
49 79
13 37
9 49
67 72
17 97
44 88
40 84
8 89
4 42
2 80
24 99
11 35
35 50
50 79
49 62
11 37
16 40
24 37
79 84
7 37
53 64
46 66
8 75
41 66
50 77
16 49
33 34
14 23
2 5
45 91
48 86
15 92
18 31
61 80
31 57
75 76
40 62
38 89
11 90
57 57
5 86
61 86
45 48

output:

93 6 13 44 32 81 74 51 63 35 100 12 11 94 88 87 30 29 62 21 71 70 34 43 78 23 68 96 18 16 61 59 95 55 79 75 42 33 41 90 82 85 8 4 99 98 97 84 66 69 65 52 2 83 37 36 27 28 80 19 77 7 10 5 56 57 60 64 54 40 3 76 86 14 31 89 15 91 92 53 26 38 39 73 72 1 50 48 49 58 45 46 20 47 22 17 24 25 67 9