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 is divided by a constant.

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 are divided by k (and rounded down to an integer).

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 10^5
• 1 \le q \le 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:

12
7