题目描述

小 Z 最近某场比赛打的很烂，痛定思痛之后，决定刻苦刷题 ！

于是小 Z 列出了一份题单，一共有 $n$ 个题目，第 $i$ 道题目的难度是 $a_i$ 。

假设小 Z 的上限水平是 $k$ ，极限情况下，小 Z 能做出难度不超过 $k$ 的所有题目。

小 Y 知道，如果小 Z 有可能做出所有题目，那么他会非常开心！于是决定使用魔法帮帮他：

小 Y 只能使用给出的 $m$ 种魔法，但每种魔法可以使用 任意次数 ，具体的，魔法有下面两类：

• 1 x 把第 $x$ 道题的难度改成任意整数
• 2 x y 交换第 $x$ 道题和第 $y$ 道题的难度

请问小 Y 能不能通过魔法使得小 Z 有可能做出全部题目？如果可以的话，最少需要使用多少次魔法？

输入格式

从文件 train.in 中读取数据。

输入共 $m +2$ 行。

第一行三个正整数 $n,m,k$ ，代表题目的数量，小 Y 能使用的魔法种类数，和小 Z 现在的上限水平。

接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 道题的难度。

接下来 $m$ 行，每行描述一种魔法，格式为下面两种之一：

• 1 x 表示可以把第 $x$ 道题的难度改成任意整数
• 2 x y 表示可以交换第 $x$ 道题和第 $y$ 道题的难度

输出格式

输出到文件 train.out 中。

共一行，如果不能通过魔法使得小 Z 有可能做出全部题目，输出 -1 ；

否则输出一个整数，代表最少需要使用魔法的次数。

3 2 2
0 3 4
1 2
2 2 3

3

数据规模与约定

对于 $20\%$ 的数据， $m=0$

对于另外 $20\%$ 的数据，只有第一种类型的魔法（即修改某一道题的难度）

对于另外 $20\%$ 的数据，第一种类型的魔法只有一个

对于 $80\%$ 的数据， $n\le 10^5$

对于全部数据， $1\le n,k,a_i\le 2\ast 10^6，0\le m \le 2\ast 10^6，1\le x,y\le n$

下发样例

附件