Kedoli and the Sequence Operations

You are given a non-negative integer sequence \(a\) of length \(n\). You need to process \(m\) operations on the sequence. There are two types of operations:

• \(\texttt{1 l r x}\): For every index \(i\) such that \(l \le i \le r\), if \(a_i\) is a multiple of \(x\) (i.e. \(x\mid a_i\)), then set \(a_i = \frac{a_i}{x}\).
• \(\texttt{2 l r}\): Report the sum of the elements in the interval \([l, r]\).

Your task is to process all the operations and output the answers for the query operations.

inputFormat

The first line contains two integers \(n\) and \(m\) — the length of the sequence and the number of operations.

The second line contains \(n\) non-negative integers \(a_1, a_2, \ldots, a_n\).

The following \(m\) lines describe the operations. Each operation is in one of the following two formats:

• 1 l r x
• 2 l r

It is guaranteed that all indices are 1-indexed.

outputFormat

For each operation of the second type, print the sum of the elements in the corresponding interval on a new line.

sample

5 4
2 4 6 8 10
2 1 5
1 1 3 2
2 1 3
2 4 5

30
6
18