#include <bits/stdc++.h>   using namespace std;   const int NMax = 1100000;   inline int read() {     int x = 0;     char ch = getchar();     bool positive = 1;     for (; ch <  0  || ch >  9 ; ch = getchar())       if (ch ==  - ) positive = 0;     for (; ch >=  0  && ch <=  9 ; ch = getchar()) x = x * 10 + ch -  0 ;     return positive ? x : -x;   }   struct node {     int w, id, sz;     node *left, *right;     int lsize() { return left ? left->sz : 0; }     int rsize() { return right ? right->sz : 0; }   } * T, pool[NMax];   void update(node *p) {     if (!p) return;     p->sz = p->lsize() + p->rsize() + 1;   }   int L;   struct pnn {     node *x, *y;   };   pnn mp(node *x, node *y) {     pnn ret;     ret.x = x;     ret.y = y;     return ret;   }   node *new_node(int id) {     node *p = &pool[L++];     p->w = rand() * rand();     p->id = id;     p->sz = 1;     p->left = p->right = NULL;     return p;   }   node *new_node(int id, int w) {     node *p = &pool[L++];     p->w = w;     p->id = id;     p->sz = 1;     p->left = p->right = NULL;     return p;   }   int N, M;   node *merge(node *a, node *b) {     if (!a) return b;     if (!b) return a;     if (b->w > a->w) {       a->right = merge(a->right, b);       update(a);       return a;     } else {       b->left = merge(a, b->left);       update(b);       return b;     }   }   pnn split(node *a, int l) {     if (!a) return mp((node *)NULL, (node *)NULL);     if (l >= a->sz) return mp(a, (node *)NULL);     if (l <= 0) return mp((node *)NULL, a);     if (l <= a->lsize()) {       pnn ret = split(a->left, l);       a->left = ret.y;       update(a);       ret.y = a;       return ret;     } else {       pnn ret = split(a->right, l - a->lsize() - 1);       a->right = ret.x;       update(a);       ret.x = a;       return ret;     }   }   int have[NMax], chose[NMax], nn;   int oper[NMax];   void DFS(node *p) {     if (p->left) DFS(p->left);     if (p->id == -1) p->id = chose[nn++];     if (p->right) DFS(p->right);   }   void DFS1(node *p) {     if (p->left) DFS1(p->left);     printf( %d  , p->id);     if (p->right) DFS1(p->right);   }   node *Build(int x, int y, int w) {     if (x == y) {       node *p = new_node(-1, w);       return p;     }     int mid = (x + y) >> 1;     node *p = new_node(-1, w);     if (mid > x) p->left = Build(x, mid - 1, w + rand());     if (mid < y) p->right = Build(mid + 1, y, w + rand());     update(p);     return p;   }   int main() {     N = read();     M = read();     T = Build(1, N, -100000000);     for (int i = 1; i <= M; i++) {       int x, y;       x = read();       y = read();       swap(x, y);       oper[i] = x;       pnn tmp = split(T, x - 1);       pnn tmq = split(tmp.y, 1);       if (have[y] && tmq.x->id != y) {         puts( -1 );         getchar();         getchar();         return 0;       }       have[y] = 1;       if (tmq.x->id != -1 && tmq.x->id != y) {         puts( -1 );         getchar();         getchar();         return 0;       }       tmq.x->id = y;       tmp.x = merge(tmq.x, tmp.x);       T = merge(tmp.x, tmq.y);     }     for (int i = 1; i <= N; i++)       if (!have[i]) chose[nn++] = i;     nn = 0;     DFS(T);     for (int i = M; i >= 1; i--) {       pnn tmp = split(T, oper[i]);       pnn tmq = split(tmp.x, 1);       tmp.x = merge(tmq.y, tmq.x);       T = merge(tmp.x, tmp.y);     }     DFS1(T);     puts(  );     getchar();     getchar();     return 0;   }   