Trong các môn học thì anh Lộc thích nhất môn CP, và trong các mảng kiến thức CP, Lộc thích nhất việc dùng cây phân đoạn. Lộc đã luyện nó ngày đêm đến hàng chuyên gia. Một hôm, có anh Aquarius cũng xưng là nghệ nhân về cây phân đoạn đến thử thách anh Lộc một bài toán quen mà lạ như sau: Cho ~n~ số tự nhiên ~a_1,a_2,…,a_n~ và ~2~ loại thao tác:

• Loại 1: tính tổng các phần tử trong đoạn ~[l,r].~
• Loại 2: á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].~

Cho danh sách ~m~ thao tác thuộc 2 loại trên, anh Lộc cần thực hiện tất cả các thao tác đã cho và đối với mỗi thao tác tính tổng, in ra kết quả nhận được. Anh Lộc đã giải xong subtask 1 dùng vét cạn rồi, còn subtask 2 thì anh... đang suy nghĩ thêm ^^. Bạn hay thử sức nhé, vì nghệ nhân Aquarius hình như cũng đang quên solution rồi T_T.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ và dòng tiếp theo là các số tự nhiên ~a_1,a_2,…,a_n~.
• Dòng thứ 3 chứa số nguyên dương ~m~ là số thao tác và trong ~m~ dòng tiếp theo mô tả ~m~ thao tác theo định dạng:
• ~1~ ~l~ ~r~: Tính tổng 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ả phần tử trong đoạn ~[l,r].~

Output trả lời tất cả các câu hỏi ở thao tác loại 1.

Sample 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

Sample output

26
22
0
34
11

Subtasks

• Có 60% test ứng với ~n,m≤2.10^3~ còn ~x, a_i <= 10^6~.
• Có 40% test ứng với ~n≤2.10^5,m≤2.10^5~ còn ~x, a_i≤10^6~.