Hey! I have an awesome task with chameleons, 5^th task for Saturday's competition.

Go ahead…

(…)

That's too difficult, I have an easier one, they won't even solve that one.

You are given an array of $N$ integers from the interval $[1,K]$. You need to process $M$ queries. The first type of query requires you to change a number in the array to a different value, and the second type of query requires you to determine the length of the shortest contiguous subarray of the current array that contains all numbers from $1$ to $K$.

Hm, I can do it in $\mathcal{O}(N^6)$. What's the limit for $N$?

Input Specification

The first line of input contains the integers $N$, $K$ and $M$ $(1\le N,M\le 100000,1\le K\le 50)$. The second line of input contains $N$ integers separated by space, the integers from the array. After that, $M$ queries follow, each in one of the following two forms:

• 1 p v - change the value of the $p^{th}$ number into $v$ $(1\le p\le N,1\le v\le K)$
• 2 - what is the length of the shortest contiguous subarray of the array containing all the integers from $1$ to $K$

In test cases worth 30% of total points, it will hold $1\le N,M\le 5000$.

Output Specification

The output must consist of the answers to the queries of the second type, each in its own line.

If the required subarray doesn't exist, output -1.

Sample Input 1

4 3 5
2 3 1 2
2
1 3 3
2
1 1 1
2

Sample Output 1

3
-1
4

Sample Input 2

6 3 6
1 2 3 2 1 1
2
1 2 1
2
1 4 1
1 6 2
2

Sample Output 2

3
3
4