32471번 - Same Segment 스페셜 저지다국어

문제

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$.

입력

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.

출력

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$.

제한

• 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$.

노트