노릭과 게임

노릭이 Дим Димыч의 휴대폰에서 재미있는 게임을 찾았다. 제작자들은 이 게임이 반응 속도와 집중력을 기르도록 만들었다. 하지만 Дим Димыч에게는 너무 어렵다.

게임은 다음과 같이 진행된다. 화면에는 색이 있는 큐브 $n$개가 한 줄로 놓여 있다. 어떤 시점에는 일부 큐브의 색이 바뀐다. 또 게임은 가끔 질문을 던진다. 구간 $[l \dots r]$($1 \le l \le r \le n$)이 주어지면, 플레이어는 $[l \dots r]$에 포함된 길이 $k$인 구간 중에서 서로 다른 색의 최대 개수를 답해야 한다. $k$는 게임 시작 시 정해지며 게임 내내 바뀌지 않는다. 목표는 모든 질문에 정확히 답하는 것이다.

당신은 이 게임의 프로그래머가 되어 모든 질문의 정답을 계산한다.

첫 줄에 정수 $n$, $m$, $k$($1 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le k \le n$)가 주어진다. 각각 큐브의 개수, 이벤트의 개수, 구간의 길이이다. 둘째 줄에는 처음 시점의 큐브 색 $a_i$($1 \le a_i \le 10^6$)가 $n$개 주어진다.

이어지는 $m$개의 줄에 이벤트가 한 줄에 하나씩 주어진다.

• 1 i x: $i$번째 큐브의 색을 $x$($1 \le i \le n$, $1 \le x \le 10^6$)로 바꾼다.
• 2 l r: 구간 $[l \dots r]$에 대해 질문에 답한다. 이때 $r - l + 1 \ge k$이다.

종류 2의 이벤트마다 답을 질문이 주어진 순서대로 한 줄에 하나씩 출력한다.