You are given an array of positive integers of size n. There will be two types of operation.

Find the minimum of a range [l,r] of the array. Where 1 <= l < r <= n

If the sum of the range [l,r] is A then type 2 operation will be adding A^-1 mod m for a given m with all the values of the range. If there doesn't exist A^-1 mod m for the given m then update operation will be adding A mod m for the given m with all the values of the range.

Input

Input will start with an integer n ( size of the array ). The next line there will be n space sperated integers. The next line will be q ( number of queries ). Following q lines there will be queries of type 1 or type 2.

A type 1 query will be like this :

1 l r ( where l is the leftmost index of the range and r is rightmost index of the range)

And type 2 query will be like this :

2 l r m ( where l is the leftmost index of the range, r is rightmost index of the range and m is the given number to find modulo with)

2 <= n <= 10^5

1 <= q <= 10^5

2 <= m <= 10^5

1 <= array elements <= 10^5

Output

For each operation of type 1 output is one single integer on a line, the minimum of the given range of that operation

Sample

Input

Output

7
3 4 2 5 3 7 9
3
1 3 6
2 3 6 8
1 3 6

2
3

From range [3,6] the values are 2, 5, 3, 7. And the minimum is 2.

The sum of this range is 17. Mod inverse of 17 for 8 is 1. So after updating values are 3, 6, 4, 8. The new minimum is 3