背景

题目描述

你需要生成一个长度为 $n$ 的非负整数序列 $a$。

$a$ 满足 $m$ 条限制，第 $i$ 条限制形如：

• 若将 $a_{x_i}$ 修改为 $y_i$，则序列中恰好有 $k_i$ 个区间满足修改前后，其区间和的变化量不超过 $p_i$。

各个限制间独立，即修改操作没有真的执行。

为了防止序列中的数过大，如果存在 $a_i>2\times 10^9$，则认为序列 $a$ 不满足限制。

若有多个满足条件的序列，输出任意一个即可。若无解，输出 -1。

输入格式

本题输入均为正整数。

第一行一个数 $T$。

对于每组数据：

第一行两个数 $n,m$。

接下来 $m$ 行，每行四个数 $x_i,y_i,k_i,p_i$。

输出格式

本题使用 SPJ。

每组数据一行。

若有解，输出 $n$ 个非负整数，第 $i$ 个数代表 $a_i$。

若无解，输出 -1。

2
4 4
4 1 6 1
3 20 10 12
2 3 4 4
4 9 10 10
3 2
1 2 6 0
1 3 6 0

6 20 18 4
-1

提示

样例解释

对于第一组数据：

$a_1=6$，$a_2=20$，$a_3=18$，$a_4=4$。

若将 $a_4$ 改为 $1$，则有 $6$ 个区间的区间和变化量不超过 $1$，分别为：

[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]。

若将 $a_3$ 改为 $20$，则所有区间的区间和变化量均不超过 $12$。

若将 $a_2$ 改为 $3$，则有 $4$ 个区间的区间和变化量不超过 $4$，分别为：

[1,1],[3,3],[3,4],[4,4]。

若将 $a_4$ 改为 $9$，则所有区间的区间和变化量均不超过 $10$。

可能存在其他解，输出任意一个即可。

对于第二组数据，可以证明没有符合条件的序列满足限制。

数据范围

本题采用捆绑测试。

• Subtask 1（10 points）：$1 \le n \le 10$，$1 \le m \le 10$，$1 \le y_i \le 10$，$1 \le p_i\le 10$。
• Subtask 2（10 points）：$m=1$。
• Subtask 3（10 points）：$k_i=\frac{n(n+1)}{2}$。
• Subtask 4（20 points）：$1 \le n \le 10 ^ 4$，$1 \le m \le 10 ^ 4$，$1 \le y_i \le 10 ^4$，$1 \le p_i\le 10^4$。
• Subtask 5（50 points）：无特殊限制。

对于所有测试数据，$1 \le n\le 10^5$，$1\le m\le 10^5$，$1 \le T\le 10$，$1\le x_i\le n$，$1 \le k_i\le \frac{n(n+1)}{2}$，$1 \le y_i \le 10 ^ 9$，$0 \le p_i\le 10^9$。