Problem E
Endangered Safari Zone
Pichuu has just entered the Safari Zone and is amazed by all
the rare Pokemon in the Safari Zone. The Safari Zone can be
divided into different zones labelled $1$ to $N$ arranged in a line from left to
right. Using the binoculars from the viewing platform, Pichuu
was able to scout all the different zones and notice that there
is exactly one pokemon in each zone of species $P_ i$ (These Pokemon may be highly
territorial).
Since, time in the Safari Zone is limited, Pichuu is
planning different routes before entering the area. Each route
consist of Pichuu taking the tram to Zone $A$ and walking right till Zone
$B$ and then taking the
tram back to the entrance. Due to Pichuu’s severe "Gotta Catch
Em All" syndrome, he must and will catch any Pokemon on his
route (He is a very good catcher), inclusive of the zone he
starts and end in.
However, as the Pokemon in the Safari Zone are endangered,
if Pichuu catches more than $K$ of same species of Pokemon after
he finishes his route, the Pokemon Ranger will confiscate all
of Pichuu’s Pokemon of that species. He wishes to catch as many
different species of Pokemon as possible to add to his team.
Thus, he needs to calculate the number of different species
that can be obtained in each of his routes.
However, while planning routes, he may occasionally use the
binoculars again to check a zone $A$, and realise that the Pokemon in a
zone has changed to species $B$ (Maybe the original Pokemon lost
the territory battle). Thus, all of his future plans need to
take into account this change when calculating number of
different species that can be obtained.
Pichuu is bad at counting and still has to use the Poketch Counter function to count, please help him instead!
Constraints
$1 \leq N, M, K \leq
10^5$
$1\leq P_ i, A_ i, B_ i \leq
N$
$1 \leq Q_ i \leq 2$
If $Q_ i = 2$, then
$A_ i \leq B_ i$
Input
The first line contains three integers, $N, M, K$, which are the number of
zones, total number of plans and changes in Pokemon, limit of
number of Pokemon of the same species that can be caught
without being confiscated.
The second line contains $N$ integers, $P_ i$ which is the original species
of the Pokemon in zone $i$.
$M$ lines then follow each
with three integers: $Q_ i, A_ i,
B_ i$

If $Q_ i = 1$, then the Pokemon in zone $A_ i$ changes to species $B_ i$

If $Q_ i = 2$, then Pichuu is planning a route from zone $A_ i$ to $B_ i$
Output
For each query with $Q_ i = 2$, output a single integer representing the number of different species that can be obtained from the route.
Sample Input 1  Sample Output 1 

5 5 2 1 2 2 2 1 2 1 4 1 3 3 2 1 4 1 3 3 2 1 5 
1 3 3 
Sample Input 2  Sample Output 2 

10 10 3 5 2 5 2 5 2 5 2 3 2 2 6 10 2 1 9 1 7 2 1 9 2 1 2 3 2 5 9 1 10 3 2 1 9 2 3 10 2 2 8 
3 1 1 2 2 2 