Stack

题号：NC223389
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

ZYT had a magic permutation $a_1,a_2,\cdots, a_n$ , and he constructed a sequence $b_1,b_2,\cdots b_n$ by the following pseudo code:

Stk is an empty stack
for i = 1 to n :
    while ( Stk is not empty ) and ( Stk's top > a[i] ) : 
        pop Stk
    push a[i]
    b[i]=Stk's size

But he somehow forgot the permutation ${a}$ , and only got some ${k}$ elements of $b_i$ .

Construct a permutation ${a}$ satisfying these $b_i$ , or determine no such permutation exists.

Here a permutation refers to a sequence that contains all integers from ${1}$ to ${n}$ exactly once.

输入描述:

The first line contains two integers , — the length of the permutation, the number of  left .

Then  lines each contains two integer , denoting that .

输出描述:

Output one line with n integers  — a possible permutation.

If no such permutation exists, output one integer -1.

示例1

输入

复制

5 2
2 2
5 4

输出

复制

1 2 5 3 4

示例2

输入

复制

10 1
1 10

输出

复制

-1

备注:

It's guaranteed that , and .