Các truy vấn khác nhau

Trong một buổi thảo luận về thuật toán, FullHouse Dev đã được đưa ra một bài toán thú vị liên quan đến mảng và các truy vấn. Với niềm đam mê toán học và lập trình, nhóm đã bắt tay vào phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) có kích thước \(N\). Họ phải thực hiện \(Q\) truy vấn trên mảng này. Mỗi truy vấn thuộc một trong hai loại sau:

1. \(1\ L\ R\ X\): Cộng \(X\) vào tất cả các phần tử trong đoạn từ \(L\) đến \(R\).
2. \(2\ L\ R\ X\): Đặt giá trị của tất cả các phần tử trong đoạn từ \(L\) đến \(R\) thành \(X\).

Tuy nhiên, không bắt buộc phải thực hiện các truy vấn theo thứ tự. Nhiệm vụ của FullHouse Dev là xác định mảng lớn nhất theo thứ tự từ điển có thể đạt được bằng cách thực hiện tất cả \(Q\) truy vấn.

Lưu ý:

• Các truy vấn không thể bị thay đổi hoặc bỏ qua. Chỉ có thể thay đổi thứ tự thực hiện chúng.
• Nếu tồn tại một chỉ số \(i\) sao cho \(A[i] > B[i]\) và \(A[j] = B[j]\) với mọi \(j < i\), thì mảng \(A\) được coi là lớn hơn mảng \(B\) theo thứ tự từ điển.

INPUT FORMAT:

• Dòng đầu tiên: Hai số nguyên \(N\) và \(Q\) cách nhau bởi dấu cách.
• Dòng thứ hai: \(N\) số nguyên cách nhau bởi dấu cách biểu diễn mảng \(A\).
• \(Q\) dòng tiếp theo: Mỗi dòng chứa một truy vấn theo định dạng \(1\ L\ R\ X\) hoặc \(2\ L\ R\ X\).

OUTPUT FORMAT:

• In ra \(N\) số nguyên cách nhau bởi dấu cách biểu diễn mảng lớn nhất theo thứ tự từ điển có thể đạt được.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq L \leq R \leq N\)
• \(-10^9 \leq A[i], X \leq 10^9\)

Ví dụ

INPUT

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

OUTPUT

3 3 5 0 -1

Giải thích

Trong trường hợp này, thứ tự thực hiện các truy vấn không ảnh hưởng đến kết quả cuối cùng. Giả sử các truy vấn được thực hiện theo thứ tự trong input, mảng sau mỗi truy vấn sẽ như sau:

• Ban đầu: \([1, 2, 3, 4, 5]\)
• Sau truy vấn 1: \([1, 2, 5, 6, 5]\)
• Sau truy vấn 2: \([3, 3, 5, 6, 5]\)
• Sau truy vấn 3: \([3, 3, 5, 0, -1]\)

Lưu ý rằng mảng cuối cùng sẽ giống nhau ngay cả khi các truy vấn được thực hiện theo một thứ tự khác.