该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

"这道题也太难了，别人也肯定 A 不了的，这边好像还剩下一个简单点的，我们来看看这个。"

小 Z 被给予了一个包含 $n$ 个正整数的的数列 $a_1,a_2,\cdots,a_n$，并且满足 $a_i \in [1,k]$。

小 Z 将会收到 $m$ 条请求，请求有两种类型：

1. 类型 1：1 p v，表示小 Z 需要编号 $p$ 对应的数的权值改为 $v$，即将 $a_p$ 修改为 $v$。保证 $1\le p \le n, 1\le v \le k$。
2. 类型 2：2，表示需要求出最短的权值包含 $1,2,3,\cdots,k$ 中所有数的连续数列的长度。

"嗯......啊哈！我可以在的 $O(n^3)$ 复杂度内实现它。对了，$n$ 有多大？"

输入格式

第一行输入 $3$ 个整数 $n,k,m$，分别表示数列的长度，题目中的 $k$ 参数以及请求操作的次数。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$.

接下来是 $m$ 次请求，每次请求形如 1 p v 或 2。

输出格式

输出格式

对于相应的请求输出答案，如果没有答案则输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

3
-1
4

输入输出样例 #2

输入 #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

说明/提示

样例 3

此样例满足 $1\le n, m \le 5000, k \le 10$ 的限制。

样例 4

此样例满足 $1\le n, m \le 50000, k \le 30$ 的限制。

说明/提示

样例 1 解释

第一次请求遇到 2，此时数列为 $[2,3,1,2]$，包含 $[1,2,3$] 所有数的最短连续数列可以为 $2,3,1$，长度为 $3$。

第二次请求遇到 1 3 3，此时数列变为 $[2,3,3,2]$

第三次请求遇到 2，此时没有包含全部 $1,2,3$ 的数列

第四次请求遇到 1 1 1，此时数列变为 $[1,3,3,2]$

第五次请求遇到 2，包含 $1,2,3$ 所有数的最短连续数列可以为 $[1,3,3,2]$，长度为 $4$。

数据范围

对于 $20\%$ 的数据，$1\le n, m \le 300, k \le 10$。

对于 $50\%$ 的数据，$1\le n, m \le 5000, k \le 10$。

另有 $20\%$ 的数据，$1\le n, m\le 50000, k \le 3$。

对于 $90\%$ 的数据，$1\le n, m\le 50000, k \le 10$。

对于 $100\%$ 的数据，$1\le n, m\le 50000, k \le 30$。