Problem 3. Min Max Subarrays II

USACO 2026 Third Contest, Platinum

You are given integers $N,Q$ $(1 \leq N, Q \leq 2 \cdot 10^5)$ and $Q$ constraints represented by four integers $t_i,l_i,r_i,k_i$ $(1 \leq t_i \leq 2, 1 \leq l_i \leq r_i \leq N, 0 \leq k_i \leq 10^9,$ all $k_i$ are distinct$).$

Construct an array $a$ consisting of $N$ integers between $0$ and $10^9$ such that for all $1 \leq i \leq Q$, $\min a[l_i ... r_i]=k_i$ if $t_i=1$ and $\max a[l_i ... r_i]=k_i$ if $t_i=2$. If multiple valid arrays exist, print any. If no valid array exists, print $-1$.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains an integer $T$ ($1 \leq T \leq 10^4$) representing the number of independent test cases.

For each test case, the first line contains two integers $N, Q$.

The next $Q$ lines each contain 4 integers $t_i$ $l_i$ $r_i$ $k_i$.

It is guaranteed that neither the sum of $N$ nor the sum of $Q$ over all test cases exceed $2 \cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, if a valid array exists, output $N$ space-separated integers $a_1\dots a_N$ on a new line. Otherwise, print $-1$.

SAMPLE INPUT:

3
2 2
1 1 2 1
1 1 2 2
2 2
1 1 2 1
1 2 2 2
4 1
2 2 4 3

SAMPLE OUTPUT:

-1
1 2
0 3 0 0

In the first test case, the answer is $-1$ because the minimum value of the array cannot be both $1$ and $2$ at the same time.

In the second test case, $a[1 ... 2]$ has a minimum of $1$ at $a[1]$ in the sample output, satisfying the first constraint. Since $a[2] = 2$, the second constraint is also satisfied.

In the third test case, there are multiple solutions. For instance, the array $[4, 3, 2, 1]$ would also be accepted.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1 2
-1
3 3 0 2 2
1 5 2 6

In the second test case, the array $[3, 5, 1]$ satisfies the first constraint but not the second constraint. Contrarily, the array $[3, 1, 1]$ satisfies the second constraint but not the first constraint. It can be proven that no array can satisfy both constraints at the same time, hence the answer is $-1$.

For all other test cases, it can be proven that the constructed array satisfies all $Q$ constraints.

SCORING: Inputs 3-4: $N,Q\le 100$ and all $t_i$ within the same test case are equalInputs 5-6: all $t_i$ within the same test case are equalInputs 7-10: $N,Q\le 100$Inputs 11-14: No additional constraints.

Problem credits: Charlie Yang