/*
* @Author: ACCXavier
* @Date: 2021-06-23 11:53:56
* @LastEditTime: 2021-06-23 12:04:21
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/problem/content/description/2439/
* @valwords: Splay fhq treap 文艺平衡树
*/
#include <cctype>
#include <cstdio>
#include <iostream>
#include <random>
std::mt19937 rnd(233);
#define print(a) printf("%d ",a)
using namespace std;
const int maxn = 1e5 + 5;
struct Node {
int l, r;
int key, val;
int size;
bool reverse;
} fhq[maxn];
int cnt, root;
inline int newnode(int key) {
fhq[++cnt].key = key;
fhq[cnt].val = rnd();
fhq[cnt].size = 1;
return cnt;
}
inline void update(int now) {
fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
}
inline void pushdown(int now) {//懒标记下传一层
std::swap(fhq[now].l, fhq[now].r);//交换左右子树
fhq[fhq[now].l].reverse ^= 1;
fhq[fhq[now].r].reverse ^= 1;
fhq[now].reverse = false;
}
void split(int now, int siz, int &x, int &y) {
if (!now)
x = y = 0;
else {
if (fhq[now].reverse) pushdown(now);
if (fhq[fhq[now].l].size < siz) {
x = now;//挂左子树
split(fhq[now].r, siz - fhq[fhq[now].l].size - 1, fhq[now].r, y);//已经分了size+1个,去右边分要减一下
} else {
y = now;
split(fhq[now].l, siz, x, fhq[now].l);
}
update(now);
}
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (fhq[x].val < fhq[y].val) {
if (fhq[x].reverse) pushdown(x);
fhq[x].r = merge(fhq[x].r, y);
update(x);
return x;
} else {
if (fhq[y].reverse) pushdown(y);
fhq[y].l = merge(x, fhq[y].l);
update(y);
return y;
}
}
void reverse(int l, int r) {
int x, y, z;
split(root, l - 1, x, y);
split(y, r - l + 1, y, z);//l~r
//包括l,和后面r-l+1个点
fhq[y].reverse ^= 1;//翻转
root = merge(merge(x, y), z);
}
void ldr(int now) {
if (!now) return;
if (fhq[now].reverse) pushdown(now);
ldr(fhq[now].l);
print(fhq[now].key);
ldr(fhq[now].r);
}
int main() {
int n, m;
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
root = merge(root, newnode(i));//i逐渐增大,大于已有树中的所有值,直接合并
while (m--) {
int l, r;
scanf("%d%d", &l,&r);
reverse(l, r);
}
ldr(root);
return 0;
}