题目背景

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

题目描述

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

岐岐一共有m种魔法，每种魔法可以使用任意次数，具体分为两类： 1 x ：将第x道题的难度改成任意整数；
2 x y：交换第x道题和第y道题的难度。

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

输入格式

输入共m+2行：

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

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

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

1 x
2 x y

其中1x表示将第x道题的难度改成任意整数；
2xy表示交换第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\leq n,k,a_{i}\leq 2\times 10^{5}$，$0\leq m\leq 2\times 10^{5}$，$1\leq x,y\leq n$。