时间限制： 1.0 秒

空间限制： 256 MB

题目描述

现在有一个排列 $a$ （ $1$ 到 $n$ 只出现了一次的数组），$k$ 个限制，每个限制有两个数字 $p$ 和 $x$，表示下标小于等于 $p$ 的数字中，值小于等于 $a_p$ 的恰好为 $x$ 个。即满足 $a_i\le a_p$ 且 $i\le p$ 的 $i$ 的数量恰好是 $x$ 个。

现在请你构造出这个 $a$ 数组，如果有多种构造方式，输出任意一种，如果构造不出来，请输出 -1。

输入格式

从标准输入读入数据。

第一行一个整数 $T$，表示有 $T$ 组数据。

之后每组数据第一行两个整数 $n,k$，表示有 $n$ 个数字，$k$ 组限制。

之后的 $k$ 行，每一行有两个数字 $p$ 和 $x$，表示下标小于等于 $p$ 的数字中，值小于等于 $a_p$ 的恰好为 $x$ 个，保证每个限制条件中的 $p$ 各不相同。

输出格式

输出到标准输出。

输出共计 $T$ 行。对于每组数据，输出 $n$ 个整数，代表你构造出来的 $a$ 数组。如果有多种构造方式，输出任意一种。如果构造不出来，请输出一行 -1。

2
5 2
2 2
5 4
10 1
1 10

1 2 5 3 4
-1

样例 1 解释

在有解的情况下，输出任意一种正确答案即可。对于样例 1 当中的第一组数据，输出 1 2 5 3 4 或 1 2 3 5 4 或其他满足两组限制条件的排列都是正确的。第二组数据无论如何也无法满足要求，故输出一行 -1 即可。

子任务

对于全部数据，保证 $1\le k,p\le n,~1\le x,n\le 10^5,~\sum n\le 5\times 10^5$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。