Dãy số của cậu bé

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$. Bạn cần thực hiện $m$ thao tác, mỗi thao tác thuộc một trong ba loại sau:

• Loại 1 — 1 l r: In ra tổng $a_l+a_{l+1}+\cdots +a_r$.
• Loại 2 — 2 l r x: Với mọi $i$ thỏa $l\le i\le r$, gán $a_i=a_{i}modx$ (phần dư khi chia $a_i$ cho $x$).
• Loại 3 — 3 k x: Gán $a_k=x$.

Hãy thực hiện toàn bộ dãy thao tác theo đúng thứ tự và in ra kết quả của mỗi thao tác loại 1.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • Nếu bắt đầu bằng số $1$: tiếp theo là hai số nguyên $l,r$ ($1\le l\le r\le n$).
  • Nếu bắt đầu bằng số $2$: tiếp theo là ba số nguyên $l,r,x$ ($1\le l\le r\le n$; $1\le x\le {10}^9$).
  • Nếu bắt đầu bằng số $3$: tiếp theo là hai số nguyên $k,x$ ($1\le k\le n$; $1\le x\le {10}^9$).

Dữ liệu ra

Với mỗi thao tác loại 1, in ra một dòng chứa tổng tương ứng. Lưu ý kết quả có thể vượt quá phạm vi số nguyên 32-bit.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le a_i\le {10}^9$

Ví dụ