Description:

Eddy likes to play cards game since there are always lots of randomness in the game. For most of the cards game, the very first step in the game is shuffling the cards. And, mostly the randomness in the game is from this step. However, Eddy doubts that if the shuffling is not done well, the order of the cards is predictable!

To prove that, Eddy wants to shuffle cards and tries to predict the final order of the cards. Actually, Eddy knows only one way to shuffle cards that is taking some middle consecutive cards and put them on the top of rest. When shuffling cards, Eddy just keeps repeating this procedure. After several rounds, Eddy has lost the track of the order of cards and believes that the assumption he made is wrong. As Eddy’s friend, you are watching him doing such foolish thing and easily memorizes all the moves he done. Now, you are going to tell Eddy the final order of cards as a magic to surprise him.

Eddy has showed you at first that the cards are number from 1 to N from top to bottom.

For example, there are 5 cards and Eddy has done 1 shuffling. He takes out 2-nd card from top to 4-th card from top(indexed from 1) and put them on the top of rest cards. Then, the final order of cards from top will be [2,3,4,1,5].

Input:

The first line contains two space-separated integer N, M indicating the number of cards and the number of shuffling Eddy has done.

Each of following M lines contains two space-separated integer pi, si indicating that Eddy takes pi-th card from top to (pi+si-1)-th card from top(indexed from 1) and put them on the top of rest cards.

1 ≤ N, M ≤ 105

1 ≤ pi ≤ N

1 ≤ si ≤ N-pi+1

Output

Output one line contains N space-separated integers indicating the final order of the cards from top to bottom.

Sample Input:

5 1
2 3

Sample Output:

2 3 4 1 5

Sample Input:

5 2
2 3
2 3

Sample Output:

3 4 1 2 5

Sample Input:

5 3
2 3
1 4
2 4

Sample Output:

3 4 1 5 2

题目链接

对一串N个数的序列(1N)进行M此操作，每次操作把PP+S段区间移动到序列起始位置，求最后序列。

将一段区间移动到序列起始位置可以用三次序列区间翻转达到，而区间翻转则可以通过Splay高效实现。

例若将序列1,2,3,4,5,6,7,8,9,10中4~7区间序列移动到整个序列的起始位置首先翻转1~7区间(调换目标区间与其左侧区间位置)后获得:7,6,5,4,3,2,1,8,9,10，接着翻转1~4区间(翻转目标区间调整序列顺序)序列获得:4,5,6,7,3,2,1,8,9,10，最后翻转5~7区间(翻转区间调整序列顺序)获得:4,5,6,7,1,2,3,8,9,10，此序列即为序列移动操作结果。

AC代码:

#include <bits/stdc++.h>

const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5;

// Root:Splay Tree根节点
int Root, Tot;
// Son[i][0]:i节点的左孩子，Son[i][0]:i节点的右孩子
int Son[maxn][2];
// Pre[i]:i节点的父节点
int Pre[maxn];
// Val[i]:i节点的权值
int Val[maxn];
// Size[i]:以i节点为根的Splay Tree的节点数(包含自身)
int Size[maxn];
// 惰性标记数组
bool Lazy[maxn];

int A[maxn];

void PushUp(int X) {
    Size[X] = Size[Son[X][0]] + Size[Son[X][1]] + 1;
}

void PushDown(int X) {
    if (Lazy[X]) {
        std::swap(Son[X][0], Son[X][1]);
        Lazy[Son[X][0]] ^= 1;
        Lazy[Son[X][1]] ^= 1;
        Lazy[X] ^= 1;
    }
}

// 判断X节点是其父节点的左孩子还是右孩子
bool Self(int X) {
    return Son[Pre[X]][1] == X;
}

// 旋转节点X
void Rotate(int X) {
    int Fa = Pre[X], FaFa = Pre[Fa], XJ = Self(X);
    PushDown(Fa); PushDown(X);
    Son[Fa][XJ] = Son[X][XJ ^ 1];
    Pre[Son[Fa][XJ]] = Pre[X];
    Son[X][XJ ^ 1] = Pre[X];
    Pre[Fa] = X;
    Pre[X] = FaFa;
    if (FaFa) {
        Son[FaFa][Fa == Son[FaFa][1]] = X;
    }
    PushUp(Fa); PushUp(X);
}

// 旋转X节点到节点Goal
void Splay(int X, int Goal = 0) {
    for (int Cur = Pre[X]; (Cur = Pre[X]) != Goal; Rotate(X)) {
        if (Pre[Cur] != Goal) {
            if (Self(X) == Self(Cur)) {
                Rotate(Cur);
            }
            else {
                Rotate(X);
            }
        }
    }
    PushUp(X);
    if (!Goal) {
        Root = X;
    }
}

// 获取以R为根节点Splay Tree中的第K大个元素在Splay Tree中的位置
int Kth(int R, int K) {
    PushDown(R);
    int Temp = Size[Son[R][0]] + 1;
    if (Temp == K) {
        return R;
    }
    if (Temp > K) {
        return Kth(Son[R][0], K);
    }
    else {
        return Kth(Son[R][1], K - Temp);
    }
}

// 翻转Splay Tree中Left~Right区间
void Reverse(int Left, int Right) {
    int X = Kth(Root, Left), Y = Kth(Root, Right + 2);
    Splay(X, 0);
    Splay(Y, X);
    PushDown(Root);
    Lazy[Son[Y][0]] ^= 1;
}

// 建立Splay Tree
void Build(int Left, int Right, int Cur) {
    if (Left > Right) {
        return;
    }
    int Mid = (Left + Right) >> 1;
    Build(Left, Mid - 1, Mid);
    Build(Mid + 1, Right, Mid);
    Pre[Mid] = Cur;
    Val[Mid] = A[Mid];
    Lazy[Mid] = 0;
    PushUp(Mid);
    if (Mid < Cur) {
        Son[Cur][0] = Mid;
    }
    else {
        Son[Cur][1] = Mid;
    }
}

void Print(int Cur) {
    PushDown(Cur);
    if (Son[Cur][0]) {
        Print(Son[Cur][0]);
    }
    if (Val[Cur] != -INF && Val[Cur] != INF) {
        printf("%d ", Val[Cur]);
    }
    if (Val[Son[Cur][1]]) {
        Print(Son[Cur][1]);
    }
}

int main(int argc, char *argv[]) {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 2; i <= N + 1; ++i) {
        A[i] = i - 1;
    }
    A[1] = INF;
    A[N + 2] = -INF;
    Build(1, N + 2, 0);
    Root = (N + 3) >> 1;
    for (int i = 0, Left, Right; i < M; ++i) {
        scanf("%d%d", &Left, &Right);
        Reverse(1, Left + Right - 1);
        Reverse(1, Right);
        Reverse(Right + 1, Left + Right - 1);
    }
    Print(Root);
    return 0;
}