You are given integers N,Q (1≤N,Q≤2⋅105) and Q constraints represented by four integers ti,li,ri,ki (1≤ti≤2,1≤li≤ri≤N,0≤ki≤109,all ki are distinct).
Construct an array a consisting of N integers between 0 and 109 such that for all 1≤i≤Q, mina[li...ri]=ki if ti=1 and maxa[li...ri]=ki if ti=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≤T≤104) 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 ti li ri ki.
It is guaranteed that neither the sum of N nor the sum of Q over all test cases exceed 2⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, if a valid array exists, output N space-separated integers a1…aN 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≤100 and all ti within the same test case are equal
Inputs 5-6: all ti within the same test case are equal
Inputs 7-10: N,Q≤100
Inputs 11-14: No additional constraints.
Problem credits: Charlie Yang