Tổng và XOR trên đoạn

Cho mảng $a$ gồm $n$ số tự nhiên $a_1,a_2,\dots ,a_n$. Có hai loại thao tác:

• Tính tổng các phần tử trong đoạn $[l,r]$;
• Áp dụng phép toán XOR với $x$ cho trước cho từng phần tử trong đoạn $[l,r]$, tức là thay mỗi $a_i$ với $l\le i\le r$ bằng $a_i\oplus x$.

Cho danh sách $m$ thao tác thuộc hai loại trên.

Yêu cầu: Hãy thực hiện lần lượt tất cả các thao tác đã cho, đối với mỗi thao tác tính tổng, in ra kết quả nhận được.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$;
• Dòng thứ hai chứa $n$ số tự nhiên $a_1,a_2,\dots ,a_n$;
• Dòng thứ ba chứa số nguyên dương $m$ là số thao tác;
• $m$ dòng tiếp theo mô tả $m$ thao tác theo định dạng:
  • 1 $l$ $r$: tính tổng các phần tử trong đoạn $[l,r]$;
  • 2 $l$ $r$ $x$: áp dụng phép toán XOR với $x$ cho tất cả các phần tử trong đoạn $[l,r]$.

Dữ liệu ra

Với mỗi thao tác loại 1, theo thứ tự xuất hiện, ghi tổng thu được trên một dòng. Dữ liệu vào có ít nhất một thao tác loại 1.

Ràng buộc

• $1\le n\le {10}^5$, $1\le m\le 5·{10}^4$.
• $0\le a_i\le {10}^6$, $0\le x\le {10}^6$.
• $1\le l\le r\le n$ trong mọi thao tác.
• Sau các thao tác XOR, giá trị các phần tử có thể vượt quá ${10}^6$ (nhưng luôn nhỏ hơn $2^{20}$).

Subtasks

• Subtask 1 ($60\%$ số điểm): $n,m\le {10}^3$.
• Subtask 2 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ