GCD and Sum Queries

You are given a sequence \(a\) of length \(n\) and \(m\) operations. The operations are of two types:

1. 1 l r x: For every index \(i\) in the range \([l,r]\), update \(a_i = \gcd(a_i, x)\), where \(\gcd(\cdot, \cdot)\) denotes the greatest common divisor.
2. 2 l r: Query the sum of elements in the interval \([l,r]\) and output the answer modulo \(2^{32}\) (i.e. modulo \(4294967296\)).

You need to process all operations and for every query output the required result.

Note: All indices are 1-indexed.

inputFormat

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

The second line contains \(n\) space-separated integers denoting the initial sequence \(a_1, a_2, \dots, a_n\).

Each of the following \(m\) lines describes an operation in one of the following formats:

• 1 l r x
• 2 l r

outputFormat

For each query operation (of the form 2 l r), output a single line containing the sum of elements in the range \([l, r]\) modulo \(2^{32}\).

sample

5 5
10 20 30 40 50
2 1 5
1 2 4 10
2 1 5
1 1 3 5
2 3 5

150
90
65