K. Same Segment
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You have a sequence $$$a$$$ of $$$N$$$ integers between $$$0$$$ and $$$K$$$ inclusive. $$$M$$$ segments are given, where $$$i$$$th segment is $$$[l_i, r_i]$$$. We want $$$\sum_{j=l_i}^{r_i} a_j = K$$$ to satisfy for every segment. Determine whether there exists such sequence $$$a$$$.

Input

Each test data contains one or more test cases. The first line contains an integer $$$T$$$ — the number of test cases for this input file.

First line of each test case contains $$$3$$$ integers $$$N$$$, $$$M$$$, $$$K$$$.

$$$i$$$-th of the next $$$M$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$: left and right end of $$$i$$$-th segment.

Output

For each test case, if a sequence that satisfies the condition exists, output the elements of the sequence. In case of multiple answers you may output any of them.

If no valid sequence exists, output a single integer $$$-1$$$.

Scoring
  • $$$1 \leq T \leq 10^5$$$
  • $$$2 \leq N \leq 4 \times 10^5$$$
  • $$$1 \leq M \leq \min\left(2 \times 10^5, \frac{N(N+1)}{2}\right)$$$
  • $$$1 \leq K \leq 20$$$
  • $$$1 \leq l_i \leq r_i \leq N$$$
  • $$$(l_i, r_i) \neq (l_j, r_j)$$$ for $$$i \neq j$$$
  • Sum of $$$N$$$ over every test case does not exceed $$$4 \times 10^5$$$.
  • Sum of $$$M$$$ over every test case does not exceed $$$2 \times 10^5$$$.
Example
Input
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
Output
1 1 1 1 1 1
-1
1 0 0 1
10 10 10