Sometimes Kaaleppi has a bad day. Then he runs on the street and damages some of the buildings.

The street consists of n buildings, and for each building you know its initial value. However, after Kaaleppi's run, the value of each building that he damages will be its previous value modulo Kaaleppi's strength on that run.

Your task is to simulate Kaaleppi's runs and calculate the values of the buildings.

Input

The first input line contains two integers n and q: the number of buildings and the number of queries. The buildings are numbered 1,2,\ldots,n. The second input line contains n numbers a_1,a_2,\ldots,a_n: the initial value for each building.

Finally, the input contains q lines that describe the queries. The first number in each query is either 1 (Kaaleppi's run) or 2 (calculation).

If the number is 1, the query contains numbers l, r and k. This means that the values of buildings l,l+1,\ldots,r will change to be their remainders when dividing by k. In other words value a_i will become a_i mod k if l \le i \le r.

If the number is 2, the query contains numbers l and r. This means that you should output the sum of the values of buildings l,l+1,\ldots,r.

Output

For each query of type 2, you should output the answer.

Constraints

• 1 \le n \le 2 \cdot 10^5
• 1 \le q \le 2 \cdot 10^5
• 1 \le a_i \le 10^9
• 1 \le l \le r \le n
• 1 \le k \le 10^9

Example

Input:

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

Output:

10
5