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 \leq n,q \leq 2 \cdot 10^5\)
• \(1 \leq p_i \leq 10^9\)
• \(1 \leq k \leq n\)
• \(1 \leq x \leq 10^9\)
• \(1 \leq a \leq b \leq 10^9\)

Example

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

3
2