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

题目背景

妙妙最近在一次编程比赛中发挥失常，下定决心要苦练算法题。她列出了一份包含若干题目的题单，请求好友岐岐施展魔法，让她能顺利通过所有练习。

题目描述

妙妙的题单中共有 $n$ 道题，第 $i$ 道题的难度为 $a_i$。假设妙妙当前的能力上限是 $k$，也就是说，她最多能做出所有难度不超过 $k$ 的题目。岐岐希望妙妙能够做完这份题单，于是使用了魔法。

岐岐一共有 $m$ 种魔法，每种魔法可以使用任意次数，具体分为两类：

1. 1 x：将第 $x$ 道题的难度改成任意整数；
2. 2 x y：交换第 $x$ 道题和第 $y$ 道题的难度。

请问是否可以通过这些魔法，使得妙妙最终能够做完所有 $n$ 道题（即所有题目的难度都不超过 $k$）？如果可以，最少需要使用多少次魔法；否则输出 $-1$。

输入格式

输入共 $m+2$ 行：

第 1 行：三个正整数 $n, m, k$，分别表示题目数量、魔法种类数以及妙妙当前的能力上限。

第 2 行：$n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 道题的初始难度。

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

• 1 x
• 2 x y

其中 1 x 表示将第 $x$ 道题的难度改成任意整数；
2 x y 表示交换第 $x$ 道题和第 $y$ 道题的难度。

输出格式

输出一行，若无法使所有题目难度均不超过 $k$，则输出 -1；否则输出一个整数，表示最少需要使用的魔法次数。

样例

3 2 2
0 3 4
1 2
2 2 3

3

样例解释

妙妙当前能力上限为 $2$，最初题目难度分别是 $[0,3,4]$。
岐岐可以按如下方式操作（共 3 次魔法）：

1. 使用 1 2 将第 2 题难度改为 $2$，题目变为 $[0,2,4]$；
2. 使用 1 2 再次将第 2 题难度改为 $2$（可认为等价操作，计入次数）；
3. 使用 2 2 3 交换第 2 题和第 3 题难度，题目变为 $[0,4,2]$，再用一次 1 2（或其他方式）即可使所有题目 ≤ $2$。

数据范围

• 对于全部数据，$1 \le n, k, a_i \le 2\times10^5$，$0 \le m \le 2\times10^5$，$1 \le x, y \le n$。

附件