Module: tiền tố

Natalya Korshunova thực sự nhớ Grigory Melekhov và muốn quay lại với anh. Nhưng thật không may, Grigory yêu Aksinya nên Natalya quyết định chứng minh cho người mình yêu thấy rằng cô ấy tốt hơn cô ấy.

Để làm được điều này, Natalia đã đến gặp Grigory và tuyên bố rằng cô ấy có thể giải quyết mọi vấn đề, bất cứ điều gì anh ấy gợi ý. Melekhov chấp nhận thử thách.

 

Grigory cung cấp cho Natalia một mảng A bao gồm các số nguyên không âm n. Sau đó, anh ấy yêu cầu cô ấy thực hiện các thao tác q cùng loại, bao gồm các thao tác sau: "Cho các số l, r và k . Ngoài ra, đối với mỗi chỉ số i từ l đến r, số k được thay thế bằng số A i và được coi là “or” độc quyền theo bit tất cả các số trong đoạn \([l;r]\), sau đó số Aiđịa điểm lần nữa >i".
Do đó, có \(r – l + 1\) thay thế độc lập mà không thay đổi mảng, và theo đó \( r – l + 1\) dẫn đến “hoặc” loại trừ theo bit. Natalia cần nói với Grigory một câu “or” tất cả các kết quả thay thế (để hiểu rõ hơn, hãy xem các ví dụ).

 

Hãy giúp Natalia Korshunova đối phó với nhiệm vụ này! Sau đó, Gregory chắc chắn sẽ trở lại với cô ấy!

 

Dòng đầu tiên là một số nguyên n (\(1 <= n <= 10^5\)) – số phần tử mảng.

Dòng thứ hai chứa n số nguyên không âm không vượt quá \(10^8\).

Dòng thứ ba là một số nguyên q (\(1 <= q <= 10^5\)) – số lượng yêu cầu.

Dòng sau gồm các dòng q, mỗi dòng chứa 3 số nguyên: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).

 

Bạn cần xuất các câu trả lời q cho mỗi truy vấn trên một dòng được phân tách bằng dấu cách.
 

 

Ví dụ

<đầu>

Giải thích

#	Đầu vào	Đầu ra
1	5 1 2 3 4 5 2 1 3 7 4 5 10	7 1