你有一个由 $N$ 个介于 $0$ 到 $K$ 之间（含 $0$ 和 $K$）的整数组成的序列 $a$。给定 $M$ 个区间，其中第 $i$ 个区间为 $[l_i, r_i]$。我们希望对于每个区间，都满足 $\sum_{j=l_i}^{r_i} a_j = K$。判断是否存在这样的序列 $a$。

输入格式

每个测试数据包含一个或多个测试用例。第一行包含一个整数 $T$ —— 此输入文件中的测试用例数量。

每个测试用例的第一行包含 $3$ 个整数 $N, M, K$。

接下来的 $M$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$：表示第 $i$ 个区间的左端点和右端点。

输出格式

对于每个测试用例，如果存在满足条件的序列，输出该序列的元素。

如果存在多个满足条件的答案，你可以输出其中任意一个。

如果不存在满足条件的序列，输出单个整数 $-1$。

数据范围

• $1 \le T \le 10^5$
• $2 \le N \le 4 \times 10^5$
• $1 \le M \le \min\left(2 \times 10^5, \frac{N(N+1)}{2}\right)$
• $1 \le K \le 20$
• $1 \le l_i \le r_i \le N$
• 对于 $i \ne j$，$(l_i, r_i) \ne (l_j, r_j)$
• 所有测试用例的 $N$ 之和不超过 $4 \times 10^5$
• 所有测试用例的 $M$ 之和不超过 $2 \times 10^5$

样例

输入样例 1

4
6 3 3
1 3
2 4
3 5
4 6 2
1 2
1 3
1 4
2 3
2 4
3 4
4 4 1
1 2
3 4
1 3
2 4
3 3 10
1 1
2 2
3 3

输出样例 1

1 1 1 1 1 1
-1
1 0 0 1
10 10 10