Chocolate

Cô Mi-a có một số kẹo chocolate và muốn chia cho $N$ người bạn của mình. Tuy nhiên các bạn của Mi-a lại muốn chơi một trò chơi để xem số kẹo chocolate mà Mi-a cần phải chia là bao nhiêu.

Ban đầu, người bạn thứ $i$ có $a_i$ viên kẹo. Trò chơi gồm $Q$ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• $1$ $l$ $r$ $k$: với mọi $i$ thỏa mãn $l\le i\le r$, thay $a_i$ bằng $a_{i}modk$ (số dư khi chia $a_i$ cho $k$);
• $2$ $l$ $r$: tính tổng số kẹo của các bạn từ vị trí $l$ đến vị trí $r$, tức là $a_l+a_{l+1}+\dots +a_r$.

Yêu cầu: Với mỗi thao tác loại $2$, hãy tính tổng số kẹo của các bạn từ vị trí $l$ đến vị trí $r$.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên $N$ và $Q$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$.
• $Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong hai dạng: 1 l r k hoặc 2 l r.

Các thao tác được thực hiện lần lượt theo thứ tự trong dữ liệu vào.

Dữ liệu ra

Với mỗi thao tác loại $2$, in ra một dòng chứa tổng $a_l+a_{l+1}+\dots +a_r$ tại thời điểm thực hiện thao tác đó.

Ràng buộc

• $1\le N,Q\le {10}^6$.
• $0\le a_i\le 2·{10}^5$.
• $1\le l\le r\le N$, $1\le k\le 2·{10}^5$.
• Có ít nhất một thao tác loại $2$.
• Mỗi test thỏa mãn ràng buộc của một trong các subtask dưới đây.

Subtasks

• Subtask 1 ($15\%$ số điểm): $N,Q\le {10}^4$.
• Subtask 2 ($25\%$ số điểm): $N,Q\le 2·{10}^5$ và mọi thao tác loại $1$ có $k=1$.
• Subtask 3 ($30\%$ số điểm): $N,Q\le 2·{10}^5$.
• Subtask 4 ($30\%$ số điểm): $N,Q\le {10}^6$, $a_i\le {10}^3$ và $k\le {10}^3$.

Ví dụ