Một công ty có \(n\) nhân viên với mức lương nhất định. Nhiệm vụ của bạn là theo dõi tiền lương và xử lí truy vấn.

Input

Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số lượng nhân viên và truy vấn. Các nhân viên được đánh số \(1,2,...,n\).

Dòng tiếp theo gồm \(n\) số nguyên \(p_1, p_2,...p_n\): lương của mỗi nhân viên.

Sau đó, có \(q\) dòng mô tả các truy vấn, mỗi dòng có một trong những dạng sau:

• ! \(k\) \(x\): thay đổi lương của nhân viên thứ \(k\) thành \(x\)
• ? \(a\) \(b\): đếm số nhân viên có tiền lương trong khoảng \(a...b\)

Output

• In ra đáp án cho mỗi truy vấn ?.

Constraints

• \(1≤n,q≤2⋅10^5\)
• \(1≤p_i≤10^9\)
• \(1≤k≤n\)
• \(1≤x≤10^9\)
• \(1≤a≤b≤10^9\)

Example

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

3
2