문제

3 seconds, 512 MB, 140 points "Hey! I have an awesome task with chameleons, 5th 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 O(N6). What’s the limit for N?”

입력

The first line of input contains the integers N, K and M (1 ⩽N, M ⩽100 000, 1 ⩽K ⩽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 pth number into v (1 ⩽p ⩽N, 1 ⩽v ⩽K)

• “2” - what is the length of the shortest contiguous subarray of the array containing all the integers

from 1 to K

출력

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.

예제 입력 1

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

예제 출력 1

3
-1
4

예제 입력 2

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

예제 출력 2

3
3
4