Cô Mi-a có một số kẹo chocolate và muốn chia cho ~N~ người bạn. Ban đầu, người bạn thứ ~i~ có ~a_i~ viên kẹo.

Có ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại:

• ~1~ ~l~ ~r~ ~k~: Với mọi ~l \le i \le r~, thay đổi ~a_i \leftarrow a_i \bmod k~;

• ~2~ ~l~ ~r~: Tính tổng số kẹo của những người bạn từ vị trí ~l~ đến vị trí ~r~.

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

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(N,Q \le 10^6)~;

• Dòng thứ hai chứa ~N~ số nguyên ~a_1,a_2,\dots,a_N~ ~(a_i \le 2 \cdot 10^5)~;

• Mỗi dòng trong ~Q~ dòng tiếp theo mô tả một trong hai loại thao tác:

  • ~1~ ~l~ ~r~ ~k~: Thực hiện ~a_i \leftarrow a_i \bmod k~ với mọi ~l \le i \le r~;

  • ~2~ ~l~ ~r~: Tính tổng ~a_l+a_{l+1}+\dots+a_r~.

Output

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~.

Scoring

Sample Input 1

6 3
5 6 2 3 8 10
1 1 3 3
2 1 4
2 3 6

Sample Output 1

7
23