题目描述

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

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

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

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

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

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

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

• 换句话说，小 Y 要通过魔法使的所有题目的难度都小于等于 $k$。

输入格式

从 train.in 文件读入数据。

第一行三个正整数 $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

样例2

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

说明/提示

样例 1 解释

首先通过 1 操作把第 2 道题的难度直接调整成 0 ，然后通过 2 操作把第 2 道题和第 3 道题的难度交换，然后再次通过 1 操作把第 2 道题的难度直接调整成 0 ，此时 3 道题的难度分别是 0 0 0，一共用了 3 次魔法。

数据范围

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

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

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

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

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