Đứa trẻ và dãy số (The Child and Sequence)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy số nguyên $a_1,a_2,\ldots,a_n$. Cần xử lý $m$ thao tác theo đúng thứ tự:

• 1 l r: in tổng $a_l+a_{l+1}+\cdots+a_r$.
• 2 l r x: với mọi $i\in[l,r]$, gán $a_i\leftarrow a_i\bmod x$.
• 3 k x: gán $a_k\leftarrow x$.

Input

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ số $a_i$. Mỗi trong $m$ dòng sau là một thao tác đúng một trong ba dạng nêu trên.

Output

Với mỗi thao tác loại 1, in tổng trên một dòng.

Subtask

• Subtask 1 (20%): n,m≤30; các điều kiện khác giữ như bài đầy đủ.

• Subtask 2 (30%): n,m≤3000; các điều kiện khác giữ như bài đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

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

• $1\le a_i\le10^9$

• $1\le x\le10^9$

• chỉ số dùng 1-based và các đoạn là đoạn đóng

Ví dụ

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

Giải thích

Ví dụ đầu: sau 2 3 5 4, đoạn [3,5] là [3,4,5] trở thành [3,0,1]. Sau 3 3 5, dãy là [1,2,5,0,1]. Truy vấn [2,5] cho $2+5+0+1=8$.