# Count the Co Prime Number

Limits 1s, 512 MB

Wow, The statement is very clear, you are given an array $A$ that contains $N$ number of positive integers and another array $B$ and $B$ also contains $N$ positive integers. Initially all the elements of $B$ are zero. You have three types of queries. The queries are:

1 l r s ( you have to update l to r like this $B[l] = A[s], B[l+1] = A[s+1], B[l+2] = A[s+2]…$ and so on ).

2 l r s ( you have to update r to l like this $B[r] = A[s], B[r-1] = A[s-1], B[r-2] = A[s-2]...$ and so on ).

3 u v ( you have to give the answer. Find how many numbers exist such that $GCD(R, L) = 1$).

Suppose $R = B[u] * B[v]$ and ( $R >= L >= 0$ )

## Input

The first line of contains $N( 1 \le N \le 100000)$- number of elements in array $A$

Next $N$lines contain $A_1, A_2, A_3..., A_N (1 \le A_i \le 1000000)$

Next line contains a positive integer $Q (1 \le Q \le 100000)$- the number of queries.

Next $Q$lines contain the queries in the format given below.

First number of each of these line contains the query type $1$ or $2$ or $3$.

In case of query type $1$or $2$, the next three numbers will be $l, r, s.$$( 1 <= l <= r <= n )$

for the query type $1$$( 1 <= s <= n-(r-l) )$and for the query type $2$ $( 1 + ( r - l ) <= s <= n )$

In case of query type 3, the next two numbers will be $u, v$. $( 1 <= u <= v <= n )$

See the sample test for a better understanding.

## Output

For each of the query type $3$ you have to print the answer to the query in separate lines.

## Sample

InputOutput
4
2
3
4
6
4
1 2 3 1
2 2 4 3
3 2 4
3 1 1

4
0


Explanation:

Explanation of the $1$'st case.

Initially: $B$$=$ { $0 , 0 , 0 , 0$ }

After the $1$st query: $B$$=$ { 0 , 2 , 3 , 0 }

After the $2$nd query: B $=$ { $0 , 2 , 3 , 4$ }

$B[2] = 2$, $B[4] = 4$

So $R = 8$.

$L = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]$

$GCD(1,8) = GCD(3,8) = GCD(5,8) = GCD(7,8) = 1$

So the answer is $4$