Cho mảng \(a\) gồm \(n\) số tự nhiên \(a_1,a_2,…,a_n\). Có 2 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\) thoa tác thuộc 2 loại trên. 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,…,a_n\);
• Dòng thứ 3 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 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

• Ghi ra tổng thu được với thao tác loại 1.

Scoring

• 60% số điểm tương ứng với 30% số test có \(n,m≤10^3,a_i≤10^6,x≤10^6\)
• 40% số điểm tương ứng với 30% số test có \(n≤10^5,m≤5.10^4,a_i≤10^6,x≤10^6\)

Example

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                 

26
22
034
11