F1ow3rC0n

인문예술탐사주간에 세종호수공원에 가서 사진도 찍고 나무에서 사용할 꽃잎도 딴 태영이는 나중에 이 나무의 꽃잎을 뜯으면 안 된다는 사실을 들었다. 그래서 태영이는 본드를 이용해 꽃잎을 나무에 다시 붙이려는 계획을 세웠다.

세종호수공원에는 일렬로 나열된 나무가 총 $N$ 그루 있으며, $i$번째 나무에 핀 꽃의 종류 번호는 $K\_i$이다. 태영이는 다음과 같은 방법으로 $Q$일 동안 꽃잎을 나무에 붙일 예정이다.

$i$번째 날에는 다음 두 일 중 하나가 일어난다.

• 태영이가 본드를 이용해서 $A\_i, A\_i+1, \cdots, B\_i$번째 나무에 순서대로 꽃잎을 붙인다.
• $A\_i$번째 나무에 핀 꽃의 종류 번호가 $B\_i$로 바뀐다.

태영이는 꽃잎의 구조를 살펴보던 중에, 나무에 핀 꽃의 종류 번호와 같은 종류 번호의 본드를 사용해야 한다는 사실을 깨달았고, $i$번째 날에는 다음과 같은 방법으로 꽃잎을 본드에 붙이기로 했다. 매일, 처음에 태영이는 본드를 들고 있지 않다.

• 태영이는 $A\_i$번째부터 $B\_i$번째까지의 나무에 순서대로 꽃잎을 붙인다. 꽃잎을 붙이는 순서가 정해져 있음에 유의하여라.
• 태영이가 본드를 들고 있지 않은 경우, 원하는 종류의 본드를 하나 구매할 수 있다.
• 태영이가 본드를 들고 있는 경우, 해당 본드를 버릴 수 있다.
• 태영이가 꽃잎을 붙이려는 나무의 꽃의 종류 번호와 태영이가 들고 있는 본드의 종류 번호가 같은 경우에만 꽃잎을 붙일 수 있다.

태영이는 꽃잎을 붙이는 각 날마다, 본드를 최소 몇 개 구매해야 하는지 궁금해졌다.

첫번째 줄에는 나무의 개수 $N$과, 태영이가 꽃잎을 붙이는 일수 $Q$가 공백으로 구분되어 주어진다.

두번째 줄에는 각 나무의 꽃의 종류 번호 $K\_1, K\_2, \cdots, K\_N$이 공백으로 구분되어 주어진다.

다음 $Q$개 줄의 $i$번째 줄에는 일어나는 일의 종류 $T\_i$와 일에 해당하는 $A\_i$, $B\_i$가 공백으로 구분되어 주어진다.

• $T\_i = 1$이면, $A\_i$번째부터 $B\_i$번째까지의 나무에 차례로 꽃잎을 붙인다.
• $T\_i = 2$이면, $A\_i$번째 나무에 핀 꽃의 종류 번호가 $B\_i$로 바뀐다.

$T\_i = 1$인 날에 대해, 구매해야 하는 본드의 최소 개수를 한 줄에 하나씩 출력하여라.

• $1 \le N, Q \le 100\,000$
• $1 \le K\_i \le 100$ ($1 \le i \le N$)
• $1 \le T\_i \le 2$ ($1 \le i \le Q$)
• $T\_i = 1$일 때, $1 \le A\_i \le B\_i \le N$ ($1 \le i \le Q$)
• $T\_i = 2$일 때, $1 \le A\_i \le N$ ($1 \le i \le Q$)
• $T\_i = 2$일 때, $1 \le B\_i \le 100$ ($1 \le i \le Q$)
• $T\_i = 1$인 $i$가 적어도 하나 존재한다. ($1 \le i \le Q$)