Design a data structure. Given a sequence of positive integers $a_0, a_1, \dots, a_{n-1}$, you need to support the following two operations:

1. MODIFY id x: Change $a_{id}$ to $x$.
2. QUERY x: Find the smallest integer $p$ ($0 \le p < n$) such that $\gcd(a_0, a_1, \dots, a_p) \times \text{XOR}(a_0, a_1, \dots, a_p) = x$. Here, $\text{XOR}(a_0, a_1, \dots, a_p)$ represents the bitwise XOR sum of $a_0, a_1, \dots, a_p$, and $\gcd$ represents the greatest common divisor.

Input

The first line contains a positive integer $n$. The next line contains $n$ positive integers $a_0, a_1, \dots, a_{n-1}$. The next line contains a positive integer $q$, representing the number of queries. The following $q$ lines each contain a query. The format is as described in the problem.

Output

For each QUERY operation, output the result on a single line. If no such $p$ exists, output no.

Constraints

For 30% of the data, $n \le 10000$, $q \le 1000$. For 100% of the data, $n \le 100000$, $q \le 10000$, $a_i \le 10^9$ ($0 \le i < n$), $x \le 10^{18}$ in QUERY x, $0 \le id < n$ and $1 \le x \le 10^9$ in MODIFY id x.

Examples

Input 1

10
1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
10
MODIFY 7 20321280
QUERY 162343680
QUERY 1832232960000
MODIFY 0 92160
QUERY 1234567
QUERY 3989856000
QUERY 833018560
MODIFY 3 8600
MODIFY 5 5306112
QUERY 148900352

Output 1

6
0
no
2
8
8