Subtask 1

Nhận thấy ~x_i \le 2~ nên ~a_i = 1~ hoặc ~a_i = 2~.

Với mỗi điều kiện có ~x_i = 2~ ta gán ~a_{l_i}, ..., a_{r_i}~ bằng ~2~.

Sau khi thực hiện các thao tác xong, kiểm tra lại xem dãy ~a~ có thoả mãn hết ~m~ điều kiện hay không.

Độ phức tạp: ~O(n \times m)~.

Subtask 2

Xét giá trị ~l_i, r_i, x_i~ của một điều kiện, ta muốn đạt được ~2~ điều sau:

1. Tất cả các phần tử ở vị trí từ ~l_i~ đến ~r_i~ đều chia hết cho ~x_i~.
2. Các phần tử ~a_{l_i}, ..., a_{r_i}~ càng nhỏ càng tốt (để hạn chế việc phần tử có giá trị vượt quá ~10^9~).

Để làm được điều này, ta sẽ đặt ~a_i~ bằng bội chung nhỏ nhất của tất cả các giá trị ~x_k \ (1 \le k \le m)~ mà ~l_k \le i \le r_k~.

Cuối cùng, kiểm tra lại xem dãy ~a~ có thoả mãn hết ~m~ điều kiện hay không.

Độ phức tạp: ~O(n \times m)~ .

Subtask 3

Tư tưởng của subtask này cũng giống với subtask 2. Tuy nhiên, vì giới hạn của ~n, m~ khá lớn nên ta cần phải tối ưu ~2~ việc:

1. Xác định giá trị của ~a_i~.
2. Kiểm tra xem dãy có thoả mãn điều kiện hay không.

Kiểm tra tính thoả mãn của dãy không khó, cách đơn giản nhất là sử dụng cấu trúc dữ liệu cây phân đoạn (segment tree). Còn việc xác định giá trị của ~a_i~ một cách nhanh chóng thì dựa vào nhận xét của subtask 2, ta có thể sử dụng kỹ thuật đánh dấu hai đầu (bài toán cơ bản của kỹ thuật đánh dấu hai đầu) để xác định xem phần tử ~a_i~ có ước là ~x \ (1 \le x \le 16)~ hay không.

Độ phức tạp:

• Độ phức tạp của việc khởi tạo mảng đánh dấu hai đầu là ~O(m \times max(x_i))~.
• Độ phức tạp của thao tác xác định các phần tử trong dãy là ~O(n \times x \times \log (\max(a_i)))~.
• Độ phức tạp của thao tác kiểm tra là ~O(m \times \log (n) \times \log (\max(a_i)))~.
• Độ phức tạp của thao tác in dãy cần tìm là ~O(n)~.