XOR trên đoạn (XOR on Segment)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì mảng số nguyên với truy vấn tổng đoạn và phép XOR cùng một mask lên toàn bộ phần tử của đoạn.

Input

Dòng đầu chứa $n$, dòng thứ hai chứa mảng ban đầu, dòng thứ ba chứa $m$. Mỗi thao tác:

• 1 l r: in tổng $[l,r]$.
• 2 l r x: thay mỗi $a_i$ trong $[l,r]$ bằng $a_i\mathbin{\oplus}x$.

Output

In tổng cho mỗi truy vấn loại 1.

Subtask

• 20 điểm: $n,m\le50$.
• 30 điểm: $n,m\le5000$.
• 50 điểm: $n\le10^5$, $m\le5\cdot10^4$, $0\le a_i\le10^6$, $1\le x\le10^6$.

Ví dụ

Input

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

Output

26
22
0
34
11

Giải thích

Truy vấn đầu tính $10+3+13=26$. Mỗi cập nhật XOR lật đúng các bit xuất hiện trong mask $x$; thực hiện tuần tự các thao tác cho các tổng tiếp theo 22, 0, 34, 11.