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]~.

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 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.

Input

• 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]~.

Output

Với mỗi thao tác loại 1, ghi tổng thu được trên một dòng.

Scoring

Sample Input 1

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 1

26
22
0
34
11