Reimu is currently out of money, so she asked Marisa to catch n chameleons to sell. The i-th chameleon has color Ai. 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≤Ai≤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 1ix, which means the i-th chameleon changes its color to x.
+ The second type of event is in the form 2lr, 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≤n,q≤105.
- 1≤k≤n.
- 1≤Ai≤n.
- 1≤i,x≤n.
- 1≤l≤r≤n.
### Example
Input
7611322233214277277142222171
Output
`
2
1
1
1
