CF1697F.Too Many Constraints

You are asked to build an array $a$, consisting of $n$ integers, each element should be from $1$ to $k$.

The array should be non-decreasing ($a_i \le a_{i+1}$ for all $i$ from $1$ to $n-1$).

You are also given additional constraints on it. Each constraint is of one of three following types:

• $1~i~x$: $a_i$ should not be equal to $x$;
• $2~i~j~x$: $a_i + a_j$ should be less than or equal to $x$;
• $3~i~j~x$: $a_i + a_j$ should be greater than or equal to $x$.

Build any non-decreasing array that satisfies all constraints or report that no such array exists.

你需要构造一个由 $n$ 个整数组成的数组 $a$，其中每个元素取值范围为 $1$ 到 $k$（含端点）。

该数组必须是非递减的（即对所有从 $1$ 到 $n-1$ 的 $i$，满足 $a_i \le a_{i+1}$）。

此外，你还需满足若干额外约束条件。每条约束属于以下三种类型之一：

• $1~i~x$：$a_i$ 不能等于 $x$；
• $2~i~j~x$：$a_i + a_j$ 必须 小于或等于 $x$；
• $3~i~j~x$：$a_i + a_j$ 必须 大于或等于 $x$。

请构造出任意一个满足所有约束的非递减数组；若不存在这样的数组，则报告无解。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^4$; $0 \le m \le 2 \cdot 10^4$; $2 \le k \le 10$).

The $i$-th of the next $m$ lines contains a description of a constraint. Each constraint is of one of three following types:

• $1~i~x$ ($1 \le i \le n$; $1 \le x \le k$): $a_i$ should not be equal to $x$;
• $2~i~j~x$ ($1 \le i \lt j \le n$; $2 \le x \le 2 \cdot k$): $a_i + a_j$ should be less than or equal to $x$;
• $3~i~j~x$ ($1 \le i \lt j \le n$; $2 \le x \le 2 \cdot k$): $a_i + a_j$ should be greater than or equal to $x$.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^4$. The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^4$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 2 \cdot 10^4$；$0 \le m \le 2 \cdot 10^4$；$2 \le k \le 10$）。

接下来的 $m$ 行中，第 $i$ 行描述一条约束。每条约束属于以下三种类型之一：

• $1~i~x$（$1 \le i \le n$；$1 \le x \le k$）：$a_i$ 不应等于 $x$；
• $2~i~j~x$（$1 \le i \lt j \le n$；$2 \le x \le 2 \cdot k$）：$a_i + a_j$ 应小于或等于 $x$；
• $3~i~j~x$（$1 \le i \lt j \le n$；$2 \le x \le 2 \cdot k$）：$a_i + a_j$ 应大于或等于 $x$。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^4$。所有测试用例的 $m$ 之和不超过 $2 \cdot 10^4$。

For each testcase, determine if there exists a non-decreasing array that satisfies all conditions. If there is no such array, then print -1. Otherwise, print any valid array — $n$ integers from $1$ to $k$.

对于每个测试用例，判断是否存在一个非递减数组满足所有条件。如果不存在这样的数组，则输出 -1；否则，输出任意一个合法数组——即由 $n$ 个介于 $1$ 到 $k$ 之间的整数组成的数组。