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