Rhezo defines $Multiplied$ $XOR$ of a range $[L,R]$ as the product of $XOR$ of all elements of the range and sum of all elements of the range.

He encountered a problem that he found difficult to solve, so he asked you to help him. The problem is as follows:

Rhezo has an array A of N elements. He needs to do 2 kinds of operations(Type 1 and Type 2) on it. You are given Q queries of 2 types:

Type 1: You will be given 2 integers $L, R$, you need to find the $Multiplied$ $XOR$ of the sub array $A[L, R]$. As the $Multiplied$ $XOR$ can be large output the value modulo $10^9+7$.

Type 2: You will be given 2 integers X and V, you need to replace the current value of $A[X]$ with V.

Input:

First line contains a single integer N denoting the number of integers in the array A. Next line contains N space separated integers denoting A. Next line contains a single integer Q. Each of the next Q lines contain 3 integers.

If the first integer is 1, then it is a type 1 query and next 2 integers denote L and R. Otherwise it is a type 2 query and next 2 integers denote X and V.

Output:

For each query of $1^{st}$ type output the $Multiplied$ $XOR$ of sub array $A[L, R]$ modulo $10^9+7$.

Constraints:

$1 \le N,Q \le 10^5$

$1 \le L \le R \le N$

$1 \le X \le N$

$1 \le A[i], V \le 10^9$