Reimu is currently out of money, so she asked Marisa to catch $n$ chameleons to sell. The $i$-th chameleon has color $A_i$. There are $q$ days, and each day one of the following events will occur:
- The $i$-th chameleon changes its color to $x$.
- Customers come to see the chameleons from $l$ to $r$. The customers want to know how many colors have exactly $k$ chameleons.
Because there are too many chameleons, Reimu asks you to count them.
Many customers come to see the chameleons, but unfortunately, they never buy. Reimu remains poor and eats chameleons.
### Input
- The first line consists of three integers $n$, $q$, $k$.
- The second line contains $n$ integers $1 \le A_i \le n$, representing the colors of the chameleons.
- $q$ lines follow, representing the events of the days:
+ The first type of event is in the form `1 i x`, which means the $i$-th chameleon changes its color to $x$.
+ The second type of event is in the form `2 l r`, where customers come to see the chameleons from $l$ to $r$.
### Output
- For each event of the second type, you need to print the number of colors of chameleons that appear exactly $k$ times.
### Constraints
- $1 \le n,q \le 10^5$.
- $1 \le k \le n$.
- $1 \le A_i \le n$.
- $1 \le i,x \le n$.
- $1 \le l \le r \le n$.
### Example
Input
```
7 6 1
1 3 2 2 2 3 3
2 1 4
2 7 7
2 7 7
1 4 2
2 2 2
1 7 1
```
Output
```
2
1
1
1
