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 math
arraySize = int(input())
sqrtSize = math.ceil((math.sqrt(arraySize)))
array = list(map(int, input().split()))
listOfLists = []
listofSums = []
base = 0
cap = sqrtSize
for x in range(sqrtSize):
	tempList = array[base:cap]
	if len(tempList) < sqrtSize:
		diff = sqrtSize - len(tempList)
		tempList.extend([0]*diff)
	listOfLists.append(tempList)
	listofSums.append(sum(tempList))
	base = cap
	cap = cap + sqrtSize
	
numQueries = int(input())
for x in range(numQueries):
	command = list(map(int, input().split()))
	total = 0
	if command[0] == 1:
		left = command[1]
		leftShift = math.ceil(left/sqrtSize) - 1
		right = command[2]
		rightShift = math.ceil(right/sqrtSize) - 1
		if int(left%sqrtSize) != 0:
				leftIndex = int(left%sqrtSize) - 1
		else:
			leftIndex = sqrtSize - 1
		if int(right%sqrtSize) != 0:
				rightIndex = int(right%sqrtSize) - 1
		else:
			rightIndex = sqrtSize - 1
		if leftShift != rightShift:
			total = sum(listofSums[leftShift+1:rightShift])
			for x in listOfLists[leftShift][leftIndex:]:
				total += x
			for y in listOfLists[rightShift][:rightIndex + 1]:
				total += y
		else:
			total = sum(listOfLists[leftShift][int(leftIndex):int(rightIndex) + 1])
		print(total)
	else:
		left = command[1]
		right = command[2]
		xorVal = command[3]
		leftShift = math.ceil(left/sqrtSize) - 1
		rightShift = math.ceil(right/sqrtSize) - 1
		if int(left%sqrtSize) != 0:
				leftIndex = int(left%sqrtSize) - 1
		else:
			leftIndex = sqrtSize - 1
		if int(right%sqrtSize) != 0:
				rightIndex = int(right%sqrtSize) - 1
		else:
			rightIndex = sqrtSize - 1
		if leftShift != rightShift:
			for k in range(len(listOfLists[leftShift][leftIndex:])):
				listOfLists[leftShift][leftIndex + k] = listOfLists[leftShift][leftIndex + k] ^ xorVal
			for j in range(len(listOfLists[rightShift][:rightIndex + 1])):
				listOfLists[rightShift][j] = listOfLists[rightShift][j] ^ xorVal
			for i in listOfLists[leftShift + 1:rightShift]:
				for h in range(len(i)):
					 i[h] = i[h] ^ xorVal
		else:
			for g in range(len(listOfLists[leftShift][int(leftIndex):int(rightIndex) + 1])):
				listOfLists[leftShift][leftIndex + g] = listOfLists[leftShift][leftIndex + g] ^ xorVal
