P11764 「KFCOI Round #1」生成序列


你需要生成一个长度为 $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`。

### 样例解释 对于第一组数据： $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$。