Tổng và thay thế (SUM and REPLACE)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Gọi $D(x)$ là số ước dương của số nguyên dương $x$. Cho dãy $a_1,\ldots,a_n$ và $m$ thao tác:

• 1 l r: với mọi $i\in[l,r]$, gán $a_i\leftarrow D(a_i)$.
• 2 l r: in tổng các phần tử trong đoạn $[l,r]$.

Input

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ phần tử. Mỗi trong $m$ dòng sau chứa t l r, với t=1 là REPLACE và t=2 là SUM.

Output

Với mỗi thao tác loại 2, in tổng trên một dòng.

Subtask

• Subtask 1 (20%): n,m≤30; các điều kiện khác giữ như bài đầy đủ.

• Subtask 2 (30%): n,m≤3000; các điều kiện khác giữ như bài đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,m\le3\cdot10^5$

• $1\le a_i\le10^6$

• có ít nhất một truy vấn loại 2

Ví dụ

Input

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

Output

30
13
4
22

Giải thích

Với mảng mẫu, tổng ban đầu là 30. Sau update 1 3 5, các giá trị 1,10,3 thành 1,4,2, nên phần tử thứ 4 là 4 và truy vấn 2 4 4 in 4.