Wrong Operator


Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

You are writing a problem:

Given an array A of length N, perform Q operations, each in one of the following forms:

  • 0 l r x: set A_l to A_l+x, \; A_{l+1} to A_{l+1}+x, \; \dots, A_r to A_r+x.
  • 1 l r: compute A_l + A_{l+1} + \dots + A_r

Yesterday, you realized you accidentally replaced all + signs with \% signs (except the ones in subscripts), where \% denotes the modulus operator. You think this is a much more interesting problem. Find a solution!

Modulus is left to right associative. This means type 1 operations are in the form ((A_l \% A_{l+1}) \% \dots) \% A_r. In this question, redefine x \% 0 = 0.

Input Specification

The first line contains two space-separated integers: N and Q (1 \leq N, Q \leq 2 \times 10^5).

The next line contains N space-separated integers: the array A (0 \leq A_i \leq 10^9 for 0 \leq i \leq N-1).

The next Q lines each contain one query in one of the formats above with 0 \leq l \leq r \leq N-1 and 0 \leq x \leq 10^9.

For 20% of the points, N, Q \leq 5 \times 10^4, and each element in A and all x in type 0 operations are \leq 6.

For another 30% of the points, there are no type 0 operations.

Output Specification

For each type 0 operation 0 l r x, set A_l to A_l \% x, \; A_{l+1} to A_{l+1} \% x, \; \dots, A_r to A_r \% x.

For each type 1 operation 1 l r, compute A_l \% A_{l+1} \% \dots \% A_r, and output the answer on a separate line.

Sample Input

5 3
5 3 4 3 3
1 0 4
0 1 3 2
1 0 1

Sample Output

2
0

Comments

There are no comments at the moment.