Min Max Subarrays II
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.
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.
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
Source: USA Computing Olympiad.
Input Format
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
For each test case, if a valid array exists, output N space-separated integers a1…aN on a new line. Otherwise, print −1.