D. The Child and Sequencetime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAt the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:  Print operation l, r. Picks should write down the value of .  Modulo operation l, r, x. Picks should perform assignment a[i] = a[i] mod x for each i (l ≤ i ≤ r).  Set operation k, x. Picks should set the value of a[k] to x (in other words perform an assignment a[k] = x). Can you help Picks to perform the whole sequence of operations?InputThe first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.Each of the next m lines begins with a number type .   If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1.  If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2.  If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3. OutputFor each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.ExamplesInput5 51 2 3 4 52 3 5 43 3 51 2 52 1 3 31 1 3Output85Input10 106 9 6 7 6 1 10 10 9 51 3 92 7 10 92 5 10 81 4 73 3 72 7 9 91 2 41 6 61 5 93 1 10Output49152319NoteConsider the first testcase:  At first, a = {1, 2, 3, 4, 5}.  After operation 1, a = {1, 2, 3, 0, 1}.  After operation 2, a = {1, 2, 5, 0, 1}.  At operation 3, 2 + 5 + 0 + 1 = 8.  After operation 4, a = {1, 2, 2, 0, 1}.  At operation 5, 1 + 2 + 2 = 5. 
Input5 51 2 3 4 52 3 5 43 3 51 2 52 1 3 31 1 3
Output85
['data structures', 'math', '*2300']