给定一个由 $$$n$$$ 个顶点和 $$$m$$$ 边组成的无向图。最初,每个顶点上都写有一个整数:顶点 $$$i$$$ 上写有 $$$p_i$$$。所有 $$$p_i$$$ 都是从 $$$1$$$ 到 $$$n$$$ 的不同整数。
您必须处理两种类型的 $$$q$$$ 查询:
- $$$1$$$ $$$v$$$ — 使用图的边(包括顶点 $$$v$$$ 本身)从顶点 $$$v$$$ 可到达的所有顶点中,找到其上写有最大数字 $$$p_u$$$ 的顶点 $$$u$$$,打印 $$$p_u$$$ 并将 $$$p_u$$$ 替换为$$$0$$$;
- $$$2$$$ $$$i$$$ — 从图中删除第 $$$i$$$ 条边。
注意,在第一种类型的查询中,有可能从$$$v$$$可到达的所有顶点都写有$$$0$$$。在本例中,$$$u$$$ 没有明确定义,但由于 $$$u$$$ 的选择不会影响任何内容,因此您可以选择从 $$$v$$$ 可到达的任何顶点并打印其值(即 $$$0$$$)。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 3 \cdot 10^5$$$; $$$1 \le q \le 5 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 不同的整数 $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$,其中 $$$p_i$$$ 是最初写在顶点 $$$i$$$ 上的数字 ($$$1 \le p_i \le n$$$)。
接下来是 $$$m$$$ 行,其中第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$),表示第 $$$i$$$ 条边连接顶点$$$a_i$$$ 和 $$$b_i$$$。保证图不包含多边。
接下来是 $$$q$$$ 行,描述查询。每行由以下格式之一给出:
- $$$1$$$ $$$v$$$ — 表示具有顶点 $$$v$$$ ($$$1 \le v \le n$$$) 的第一类型查询。
- $$$2$$$ $$$i$$$ — 表示带有边 $$$i$$$ ($$$1 \le i \le m$$$) 的第二种类型的查询。对于第二类型的每个查询,保证相应的边还没有从图中删除。
输出
对于第一种类型的每个查询,打印写在所选顶点 $$$u$$$ 上的 $$$p_u$$$ 的值。
示例
输入 #1
5 4 6 1 2 5 4 3 1 2 2 3 1 3 4 5 1 1 2 1 2 3 1 1 1 2 1 2
输出 #1
5 1 2 0