Congratulations! You’ve been hired in “Buggy Software Ltd.” And you’ve been already given your first assignment. Initially, you’ll be given a n length array a of numbers. Then you’ll be given q queries of two types:
1 l r: meaning that calculate the sum of elements whose indices i satisfy l≤i≤r
2 l r g: meaning that change all ai to gcd(ai,g)aiwhere l≤i≤r
You have to print the results of the queries of the first type.
Input
The first line will contain two integers n and q, the size of a and number of queries respectively. The next line will contain n space separated integers, the contents of array a. Next q lines will each contain the queries: 1 l r or 2 l r g.
1≤n≤2⋅105
1≤q≤2⋅105
1≤ai≤2⋅105
1≤l≤r≤n
1≤g≤2⋅105
Output
For each query of type 1, output the answer in a single line.