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

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
• \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
• \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
• \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Output

• In ra kết quả cho truy vấn \(?\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(2\) (\(30\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(3\) (\(40\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Example

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

3
2