Cho một dãy số nguyên không âm \(a = a_1, a_2, \ldots, a_n\) và \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

• 0 \(u\) \(v\) \(x\): Gán \(a_i = a_i \wedge x\) \(\forall u \leq i \leq v\), với \(\wedge\) là phép xor, tổng nim, hoặc triệt tiêu

• 1 \(u\) \(v\): Tính và in ra tổng các \(a_i\) \(\forall u \leq i \leq v\)

Input

• Dòng đầu chứa \(n\)
• Dòng tiếp theo chứa \(a_1\) \(a_2\) \(\ldots\) \(a_n\)
• Dòng tiếp theo chứa số lượng truy vấn: \(Q\)
• \(Q\) dòng tiếp theo mỗi dòng chứa một truy vấn: \(0\) \(u\) \(v\) \(x\) hoặc \(1\) \(u\) \(v\)

Output

• Với mỗi truy vấn dạng \(1\) \(u\) \(v\), in ra trên một dòng tổng các số từ vị trí \(u\) đến \(v\) trên dãy \(a\)

Scoring

• \(1 \leq n, T \leq 10^5\), \(0 \leq a_i \leq 10^5\), \(0 \leq x \leq 10^5\)
• Có ít nhất 50% số test với \(n, Q \leq 5000\)

Example

5
1 2 3 4 5
5
0 1 3 1
0 3 5 2
1 1 5
1 3 3
1 1 2 

16
0
3