Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ thuộc một trong hai dạng:

1. Cho hai số nguyên ~k, x~, gán ~a_k \leftarrow x~.

2. Cho ba số nguyên ~l, r, y~, đếm số phần tử trong đoạn con ~a_l, a_{l+1}, \dots, a_r~ có giá trị là ~y~. Nói cách khác, đếm số giá trị ~j~ sao cho ~l \leq j \leq r~ và ~a_j = y~.

Yêu cầu: Với mỗi truy vấn loại 2, in ra giá trị cần tìm.

Input

Dòng đầu tiên chứa hai số nguyên ~n, q~ là kích thước mảng ~a~ và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~1 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Đối với truy vấn loại 1, dòng này chứa ba số nguyên ~1 \space k \space x~ (với ~1 \leq k \leq n~ và ~1 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, dòng này chứa bốn số nguyên ~2 \space l \space r \space y~ (với ~1 \leq l \leq r \leq n~ và ~1 \leq y \leq 10^9~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~2~ (chiếm ~30\%~ số điểm): ~1 \leq n, q \leq 10^5~; ~1 \leq y \leq 10~.

• Subtask ~3~ (chiếm ~50\%~ số điểm): ~1 \leq n, q \leq 10^5~.

Sample Input 1

10 3
7 8 9 1 7 8 9 9 1 2
2 1 10 7
1 5 9
2 4 9 9

Sample Output 1

2
3