Salary Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

A company has $n$ employees, and employee $i$ currently has salary $p_i$. Process $q$ queries:

• ! k x: change employee $k$'s salary to $x$.
• ? a b: count employees whose salary is in $[a,b]$.

Input

The first line contains $n,q$.

The second line contains $p_1,p_2,\ldots,p_n$.

The next $q$ lines contain the queries.

Output

For every ? query, print the required count.

Subtasks

• Subtask 1 — 20%: $1\le n,q\le50$.
• Subtask 2 — 30%: $1\le n,q\le5000$.
• Subtask 3 — 50%: $1\le n,q\le2\cdot10^5$, and all salary values/query bounds are in $[1,10^9]$.

Examples

Input

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

Output

3
2

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.