Nolik and the Game

Nolik found an interesting game on Dim Dimych's phone. Its creators meant it to train reaction speed and attentiveness. For Dim Dimych, it is too hard.

The game works as follows. $n$ colored cubes stand in a row on the screen. At some moments the colors of some cubes change. At other times the game asks a question: it gives an interval $[l \dots r]$ ($1 \le l \le r \le n$), and the player must answer with the maximum number of distinct colors on a segment of length $k$ contained in $[l \dots r]$. The number $k$ is set at the start of the game and stays fixed throughout. Your goal is to answer every question correctly.

You play the programmer of this game and compute the correct answers to all questions.

The first line contains three integers $n$, $m$, $k$ ($1 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le k \le n$): the number of cubes, the number of events, and the segment length. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$), the initial colors of the cubes.

Each of the next $m$ lines describes one event:

• 1 i x: change the color of the $i$-th cube to $x$ ($1 \le i \le n$, $1 \le x \le 10^6$).
• 2 l r: answer the question for the interval $[l \dots r]$, where $r - l + 1 \ge k$.

For each event of type 2, print the answer on its own line, in the order the questions are asked.