The Child and Sequence

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

You are given an integer array $a_1,a_2,\ldots,a_n$. Process $m$ operations in order:

• 1 l r: print $a_l+a_{l+1}+\cdots+a_r$.
• 2 l r x: for every $i\in[l,r]$, set $a_i\leftarrow a_i\bmod x$.
• 3 k x: set $a_k\leftarrow x$.

Input

The first line contains $n,m$. The second line contains $a_1,\ldots,a_n$. Each of the next $m$ lines is one operation in one of the three formats above.

Output

For every type-1 operation, print the range sum on its own line.

Subtasks

• Subtask 1 (20%): n,m≤30; all other conditions are unchanged.

• Subtask 2 (30%): n,m≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,m\le10^5$

• $1\le a_i\le10^9$

• $1\le x\le10^9$

• indices are 1-based and every query range is inclusive

Examples

Input

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

Output

8
5

Explanation

After modulo on positions 3..5 by 4, [3,4,5] becomes [3,0,1]. Setting position 3 to 5 gives [1,2,5,0,1]; the sum on 2..5 is 8.