Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Task

By khepa98 · Limits 1s, 512 MB

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

  1. Find the minimum of a range [l,r] of the array. Where 1 <= l < r <= n
  2. 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

InputOutput
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

    Discussion

    Statistics


    72% Solution Ratio

    YouKnowWhoEarliest, 1M ago

    adnan_tokyFastest, 0.1s

    ash_98Lightest, 7.3 MB

    emrul_muShortest, 2431B

    Submit

    Login to submit