At 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? The first line of input contains two integer: n , m (1 ≤ n , m ≤ 10 5 ) . The second line contains n integers, separated by space: a 1, a 2, ..., a n (1 ≤ a i ≤ 10 9 ) — 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 ≤ 10 9 ) , which correspond the operation 2. If type = 3 , there will be two integers more in the line: k , x (1 ≤ k ≤ n ; 1 ≤ x ≤ 10 9 ) , which correspond the operation 3. For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer. Consider 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 .