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