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