*Kousaka Honoka* and *Minami Kotori* are playing a game about a secret of *Yazawa Nico*.

Then

There are multiple test cases in input, you should process to the end of file.

For each case, the first line is an integer `N`, the number of elements in the array described above.
Then second line contains `N` integers no greater than 10^{7}, the elements of the array initially.(`1 <= N <= 100,000`)

The third line is a integer `T`, the number of the operations of the game. Each line of the following `T` lines
is in one of the following formats.(`1 <= T <= 100,000`)

"1 L R" : *Minami Kotori* will chooses the consecutive part of the array from the `L`th to `R`th element inclusive.
(1 <= `L <= R` <= N)

"2 L R v" : *Kousaka Honoka* will change the value of the `p`th element `A[p]` in the array to `A[p]%v` for all `L <= p <= R`.(`1 <= L <= R <= N, 1 <= v <= 10 ^{7}`)

"3 p x" : *Kousaka Honoka* will change the value of the `p` th element `A[p]` to `x`.(`1 <= p <= N, 1 <= x <= 10 ^{7}`)

Each time when *Minami Kotori* chooses some part of the array, you should output a line, the number of *NicoNico-number* in that part.

提交代码