Cho một dãy số nguyên ~a~ kích thước ~n~ bao gồm toàn các phần tử không âm.
Người ta thực hiện lần lượt các truy vấn sau thuộc một trong ba dạng sau trên dãy:
~1~ ~l~ ~r~ ~x~: Gán ~a_i=a_i~ AND ~x~ với mọi ~l\le i \le r~.
~2~ ~l~ ~r~ ~x~: Gán ~a_i=x~ với mọi ~l\le i \le r~.
~3~ ~l~ ~r~: Tính giá trị ~a_l~ OR ~a_{l+1}~ OR ~...~ OR ~a_r~.
Trong đó AND là toán tử AND và OR là toán tử OR.
Yêu cầu: Bạn hãy cho biết người ta ở đây là ai trả lời giá trị của
biểu thức ở các truy vấn loại 3 nhé.
Input
Dòng đầu chứa hai số nguyên dương ~n, q~ (~1\le n,q \le 5\cdot10^5~) là kích thước dãy và số truy vấn.
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0\le a_i < 2^{30}~) mô tả dãy số.
~q~ dòng tiêp, mỗi dòng chứa một truy vấn thuộc một trong ba dạng kể trên. Trong mọi truy vấn luôn có ~1\le l \le r \le n~; trong truy vấn 1 và 2 luôn có ~0 \le x < 2^{30}~.
Output
In ra nhiều dòng, mỗi dòng là câu trả lời cho các truy vấn loại 3 tương ứng.
Scoring
Có ~20\%~ số test của bài với ~n,q\le 5000~.
Có ~20\%~ số test khác của bài không có các truy vấn loại 1.
Có ~20\%~ số test khác của bài với ~n,q \leq 10^5~
~40\%~ số test còn lại không có điều kiện gì thêm.
Sample Input 1
5 6
1 2 3 4 5
3 1 5
3 2 3
1 1 5 1
3 1 5
2 3 4 4
3 2 3
Sample Output 1
7
3
1
4
Notes
Sau truy vấn loại 1, dãy ~a~ trở thành:
~[1, 0, 1, 0, 1]~
Sau truy vấn loại 2, dãy ~a~ trở thành:
~[1, 0, 4, 4, 1]~
Bình luận