Phần Dư Trên Dãy

Cho dãy số nguyên không âm $a_1,\dots ,a_n$. Bạn cần thực hiện ba loại thao tác:

• $1$ $l$ $r$: tính tổng các phần tử trên đoạn đóng $[l,r]$.
• $2$ $l$ $r$ $x$: với mọi $i$ trong $[l,r]$, gán $a_i=a_i\mathrm{mod}x$.
• $3$ $k$ $x$: gán riêng phần tử $a_k=x$.

Input

• Dòng đầu chứa $n$ và $m$.
• Dòng thứ hai chứa $n$ phần tử ban đầu.
• $m$ dòng tiếp theo mô tả các thao tác theo đúng một trong ba dạng trên.

Output

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

Constraints

• $1\le n,m\le 10^5$.
• $0\le a_i,x\le 10^9$ đối với phép gán; $1\le x\le 10^9$ đối với phép modulo.
• Các chỉ số và đoạn đều hợp lệ; tổng cần dùng số nguyên $64$ bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$ và mọi giá trị không vượt $10^6$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 6
10 7 5 12
1 1 4
2 1 3 6
1 1 4
3 2 20
2 2 4 7
1 2 4

34
22
16