SUM và REPLACE

Với số nguyên dương $x$, gọi $D(x)$ là số ước dương của $x$. Ví dụ $D(2)=2$ (các ước là $1,2$), $D(6)=4$ (các ước là $1,2,3,6$).

Cho một dãy $a$ gồm $n$ số nguyên dương. Bạn phải xử lý $m$ truy vấn thuộc một trong hai loại sau:

1. REPLACE $l$ $r$ — với mọi $i$ mà $l\le i\le r$, thay $a_i$ bằng $D(a_i)$.
2. SUM $l$ $r$ — tính ${\sum }_{i=l}^r{a}_i$.

Với mỗi truy vấn loại 2, hãy in ra kết quả.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số phần tử của dãy và số truy vấn.
• 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 chứa ba số nguyên $t_i,l_i,r_i$. Nếu $t_i=1$ thì đây là truy vấn REPLACE $l_i$ $r_i$; nếu $t_i=2$ thì đây là truy vấn SUM $l_i$ $r_i$.

Đảm bảo có ít nhất một truy vấn loại 2.

Dữ liệu ra

Với mỗi truy vấn SUM, in ra kết quả trên một dòng.

Ràng buộc

• $1\le n,m\le 3·{10}^5$
• $1\le a_i\le {10}^6$
• $1\le t_i\le 2$
• $1\le l_i\le r_i\le n$

Ví dụ