Bạn được cho các số nguyên \(N,Q\) (\(1\leq N,Q\leq 2\cdot 10^5\)) và \(Q\) ràng buộc được biểu diễn bởi bốn số nguyên \(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\), mọi \(k_i\) đôi một khác nhau).

Hãy xây dựng một mảng \(a\) gồm \(N\) số nguyên nằm trong khoảng từ \(0\) đến \(10^9\) sao cho với mọi \(1\leq i\leq Q\), \(\min a[l_i\dots r_i]=k_i\) nếu \(t_i=1\), và \(\max a[l_i\dots r_i]=k_i\) nếu \(t_i=2\). Nếu có nhiều mảng hợp lệ, hãy in ra một mảng bất kỳ. Nếu không tồn tại mảng hợp lệ, in \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(T\) (\(1\leq T\leq 10^4\)), biểu diễn số bộ kiểm thử độc lập.

Với mỗi bộ kiểm thử, dòng đầu tiên chứa hai số nguyên \(N,Q\).

\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(t_i\), \(l_i\), \(r_i\), \(k_i\).

Đảm bảo rằng cả tổng \(N\) lẫn tổng \(Q\) trên tất cả các bộ kiểm thử đều không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ kiểm thử, nếu tồn tại một mảng hợp lệ, in \(N\) số nguyên \(a_1\dots a_N\), cách nhau bởi dấu cách, trên một dòng mới. Nếu không, in \(-1\).

Ví dụ

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

-1
1 2
0 3 0 0

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

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

Phân nhóm

• Dữ liệu 3–4: \(N,Q\leq 100\) và mọi \(t_i\) trong cùng một bộ kiểm thử đều bằng nhau.
• Dữ liệu 5–6: mọi \(t_i\) trong cùng một bộ kiểm thử đều bằng nhau.
• Dữ liệu 7–10: \(N,Q\leq 100\).
• Dữ liệu 11–14: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Platinum — “Min Max Subarrays II” — tác giả: Charlie Yang.
https://usaco.org/index.php?page=viewproblem2&cpid=1598