Mạch gộp OR/XOR nhiều tầng

Bối cảnh và bài toán

Một mạch tổng hợp nhận 2^n tín hiệu ở tầng lá. Tầng đầu gộp từng cặp bằng OR, tầng kế tiếp bằng XOR, rồi tiếp tục luân phiên cho tới khi còn một giá trị ở gốc. Sau mỗi lần thay đổi một tín hiệu đầu vào, cần xuất giá trị tại gốc.

Yêu cầu

Sau mỗi cập nhật điểm, tính giá trị tổng hợp ở gốc của cây nhị phân đầy đủ.

Input

• Dòng 1 chứa n m.
• Dòng 2 chứa 2^n số ban đầu.
• m dòng tiếp theo chứa p b: gán vị trí p bằng b.

Output

Sau mỗi cập nhật, in giá trị tại gốc.

Ràng buộc

• 1 <= n <= 17
• 1 <= m <= 10^5
• 0 <= a[i], b < 2^30
• 1 <= p <= 2^n

Chấm điểm

Ví dụ 1

Input

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

Output

1
3
3

Giải thích. Với n=2, tầng lá gộp OR rồi tầng gốc gộp XOR.

Ví dụ 2

Input

1 2
5 2
2 7
1 0

Output

7
7

Giải thích. Khi n=1, gốc chỉ là OR của hai lá.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 339D – Xenia and Bit Operations.