You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

"嘿！在星期五我们会有一场很棒的比赛。"

"那就去呗..."

……

"这道题也太难了，别人也肯定 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$ 有多大？"

输入格式

从 truth.in 文件读入数据。

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

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

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

输出格式

输出到 truth.out 文件。

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

样例

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

3
-1
4

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

3
3
4

样例 3

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

点击链接 ex_truth3.in 和 ex_truth3.out 下载大样例 3 的输入数据和输出数据。

样例 4

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

点击链接 ex_truth4.in 和 ex_truth4.out 下载大样例 4 的输入数据和输出数据。

说明/提示

样例 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$。