You've got an array *a*, consisting of *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. You are allowed to perform two operations on this array:
 1.  Calculate the sum of current array elements on the segment [*l*, *r*], that is, count value *a*<sub class="lower-index">*l*</sub> + *a*<sub class="lower-index">*l* + 1</sub> + ... + *a*<sub class="lower-index">*r*</sub>. 1.  Apply the xor operation with a given number *x* to each array element on the segment [*l*, *r*], that is, execute <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2ef04d094daf2dcff9a998a558bd9cab93bbd012.png" style="max-width: 100.0%;max-height: 100.0%;"/>. This operation changes exactly *r* - *l* + 1 array elements. 
Expression <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b364f2e04c665b78b924ec10666327a4ef4635bc.png" style="max-width: 100.0%;max-height: 100.0%;"/> means applying bitwise xor operation to numbers *x* and *y*. The given operation exists in all modern programming languages, for example in language C++ and Java it is marked as "^", in Pascal — as "xor".

You've got a list of *m* operations of the indicated type. Your task is to perform all given operations, for each sum query you should print the result you get.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the size of the array. The second line contains space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the original array.

The third line contains integer *m* (1 ≤ *m* ≤ 5·10<sup class="upper-index">4</sup>) — the number of operations with the array. The *i*-th of the following *m* lines first contains an integer *t*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2) — the type of the *i*-th query. If *t*<sub class="lower-index">*i*</sub> = 1, then this is the query of the sum, if *t*<sub class="lower-index">*i*</sub> = 2, then this is the query to change array elements. If the *i*-th operation is of type 1, then next follow two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*). If the *i*-th operation is of type 2, then next follow three integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>). The numbers on the lines are separated by single spaces.
import gc
import heapq
import itertools
import math
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *
from fractions import Fraction
import bisect


def S():
	return sys.stdin.readline().split()


def I():
	return [int(i) for i in sys.stdin.readline().split()]


def II():
	return int(sys.stdin.readline())


def IS():
	return sys.stdin.readline().replace('\n', '')


class SegTree:
	def __init__(self, a):
		self.n = len(a)
		self.size = 1
		self.a = a
		while self.size < self.n:
			self.size *= 2
		self.tree = [[0, 0] for _ in range(2 * self.size - 1)]
		self._build(0, 0, self.size)
		
	def _build(self, x, lx, rx):
		if rx - lx == 1:
			if lx < self.n:
				self.tree[x][0] = self.a[lx]
			return
		
		m = (rx + lx) // 2
		self._build(2 * x + 1, lx, m)
		self._build(2 * x + 2, m, rx)
		self.tree[x][0] = self.tree[2 * x + 1][0] + self.tree[2 * x + 2][0]
	
	def _get_sum(self, left, right, x, lx, rx, g):
		if left <= lx and rx <= right:
			if g % 2 == 0:
				return self.tree[x][0]
			else:
				return rx - lx - self.tree[x][0]
		if rx <= left or lx >= right:
			return 0
		
		m = (lx + rx) // 2
		s1 = self._get_sum(left, right, 2 * x + 1, lx, m, g + self.tree[x][1])
		s2 = self._get_sum(left, right, 2 * x + 2, m, rx, g + self.tree[x][1])
		return s1 + s2
	
	def get_sum(self, left, right):
		return self._get_sum(left, right, 0, 0, self.size, 0)

	def _operation(self, left, right, x, lx, rx, g):
		if left <= lx and rx <= right:
			self.tree[x][0] = g - self.tree[x][0]
			self.tree[x][1] += 1
			return self.tree[x][0]
		if rx <= left or lx >= right:
			return self.tree[x][0]
		m = (lx + rx) // 2
		s1 = self._operation(left, right, 2 * x + 1, lx, m, g // 2)
		s2 = self._operation(left, right, 2 * x + 2, m, rx, g // 2)
		self.tree[x][0] = s1 + s2
		return self.tree[x][0]
		
	def operation(self, left, right):
		return self._operation(left, right, 0, 0, self.size, self.size)


def main():
	n = II()
	a = I()
	bin_a = ['0'] * n
	for i in range(n):
		el = bin(a[i])[2:]
		bin_a[i] = (20 - len(el)) * '0' + el
	
	for_tree = [[0] * n for _ in range(20)]
	for i in range(n):
		for j in range(20):
			if bin_a[i][j] == '1':
				for_tree[j][i] = 1
				
	trees = [SegTree(i) for i in for_tree]
	
	m = II()
	for i in range(m):
		kind, *z = I()
		if kind == 1:
			left, right = z
			left -= 1
			ans = 0
			two = 1
			for j in range(20):
				ans += two * trees[19 - j].get_sum(left, right)
				two *= 2
			print(ans)
		else:
			left, right, x = z
			left -= 1
			x = bin(x)[2:]
			x = (20 - len(x)) * '0' + x
			for j in range(20):
				if x[j] == '1':
					trees[j].operation(left, right)
		
	
if __name__ == '__main__':
	# for _ in range(II()):
	# 	main()
	main()
