CF420D.Cup Trick

The employees of the F company have lots of ways to entertain themselves. Today they invited a famous magician who shows a trick with plastic cups and a marble.

The point is to trick the spectator's attention. Initially, the spectator stands in front of a line of n plastic cups. Then the magician places a small marble under one cup and shuffles the cups. Then the spectator should guess which cup hides the marble.

But the head coder of the F company isn't easy to trick. When he saw the performance, he noticed several important facts:

• each cup contains a mark — a number from 1 to n; all marks on the cups are distinct;
• the magician shuffles the cups in m operations, each operation looks like that: take a cup marked x__i, sitting at position y__i in the row of cups (the positions are numbered from left to right, starting from 1) and shift it to the very beginning of the cup row (on the first position).

When the head coder came home after work he wanted to re-do the trick. Unfortunately, he didn't remember the starting or the final position of the cups. He only remembered which operations the magician performed. Help the coder: given the operations in the order they were made find at least one initial permutation of the cups that can go through the described operations in the given order. Otherwise, state that such permutation doesn't exist.

F 公司的员工有许多娱乐方式。今天，他们邀请了一位著名魔术师，表演一个使用塑料杯子和一颗弹珠的魔术。

其关键在于转移观众的注意力。最初，观众站在一排 $n$ 个塑料杯子前。接着，魔术师将一颗小弹珠藏在其中一个杯子下面，并对杯子进行洗牌操作。随后，观众需猜测哪个杯子下藏着弹珠。

但 F 公司的首席程序员可没那么容易被欺骗。当他观看这场表演时，注意到了几个重要事实：

• 每个杯子上都标有一个数字——范围为 $1$ 到 $n$；所有杯子上的标记互不相同；
• 魔术师共执行了 $m$ 次洗牌操作，每次操作的形式如下：取标号为 $x_i$ 的杯子，该杯子当前位于杯子序列中的第 $y_i$ 个位置（位置编号从左至右，起始为 $1$），然后将其移动到杯子序列的最前端（即第 $1$ 个位置）。

首席程序员下班回家后，想复现这个魔术。遗憾的是，他既不记得杯子的初始排列，也不记得最终排列，只记得魔术师执行过的操作序列。请你帮助这位程序员：给定按执行顺序排列的操作序列，找出至少一个初始杯子排列，使得该排列能按给定顺序依次执行全部操作；若不存在这样的排列，则说明其不存在。

The first line contains integers n and m (1 ≤ n, m ≤ 106). Each of the next m lines contains a couple of integers. The i-th line contains integers x__i, y__i (1 ≤ x__i, y__i ≤ n) — the description of the i-th operation of the magician. Note that the operations are given in the order in which the magician made them and the coder wants to make them in the same order.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^6$）。接下来的 $m$ 行中，每行包含一对整数。第 $i$ 行包含整数 $x_i$、$y_i$（$1 \leq x_i, y_i \leq n$），表示魔术师执行的第 $i$ 个操作。注意：这些操作按魔术师实际执行的顺序给出，而程序员希望以相同的顺序执行它们。

If the described permutation doesn't exist (the programmer remembered wrong operations), print -1. Otherwise, print n distinct integers, each from 1 to n: the i-th number should represent the mark on the cup that initially is in the row in position i.

If there are multiple correct answers, you should print the lexicographically minimum one.

如果所描述的排列不存在（程序员记错了操作），则输出 -1。否则，输出 n 个互不相同的整数，每个整数均在 1 到 n 之间：其中第 i 个数表示初始时位于第 i 个位置上的杯子上的编号。

若存在多个正确答案，你应输出字典序最小的那个。