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 | |
Dataset can be huge. Use faster I/O
