Bạn được cho một mảng gồm ~n~ phần tử và phải trả lời ~q~ truy vấn.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 2\times10^5)~ - số lượng phần tử của mảng và số lượng truy vấn. Dòng tiếp theo gồm ~n~ số nguyên ~a_1,a_2,..,a_n~ ~(1 \le a_i \le 10^7)~ - giá trị của phần tử thứ ~i~.

~q~ dòng tiếp theo mô tả các truy vấn, mỗi dòng có một trong hai dạng sau:

• ~1~ ~l~ ~r~ : Yêu cầu xác định số lượng số nguyên tố trong đoạn ~[l;r]~ ~(1 \le l \le r \le n)~.
• ~2~ ~p~ ~x~ : Cập nhật giá trị của phần tử tại vị trí ~p~ thành ~x~ ~(1 \le p \le n)~, ~(1 \le x \le 10^7)~.

Output

In ra một số nguyên đối với mỗi truy vấn loại ~1~.

Sample Input 1

5 3
1 2 3 4 5
1 1 3
2 2 5
1 1 5

Sample Output 1

2 
3

Sample Input 2

3 3
2 11 7
1 1 3
2 2 10
1 1 3

Sample Output 2

3
2