最近，Rikka 对有向无环图（DAG）的数据结构产生了浓厚的兴趣。她梦想着将诸如“加权链分解”之类的经典树算法推广到 DAG 上，那一定会非常酷！

现在，她提出了一个简单的问题，并邀请你和她一起解决。

给定一个包含 $n$ 个节点和 $m$ 条边的 DAG $G$。每个节点 $u$ 都有一个非负整数值 $val_u$。所有值初始均为 0。

Rikka 想要执行以下三种类型的 $q$ 次操作：

1. 给定 $u$ 和 $x$，将所有从 $u$ 可达的节点 $v$ 的 $val_v$ 设置为 $x$；
2. 给定 $u$ 和 $x$，将所有从 $u$ 可达的节点 $v$ 的 $val_v$ 设置为 $\min\{val_v, x\}$；
3. 给定 $u$，输出其当前的 $val_u$。

你能足够快地完成所有这些操作吗？

如果存在一条从 $u$ 开始并以 $v$ 结束的路径，则称节点 $v$ 可从 $u$ 可达。路径是一个节点序列 $p_1, p_2, \dots, p_k$，满足对于每个 $i = 1, 2, \dots, k - 1$，都有 $(p_i, p_{i+1}) \in G$。

输入格式

第一行包含三个整数 $n, m, q$ ($1 \le n, m, q \le 10^5$)。

接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示图中的一条有向边 $(x, y)$ ($1 \le x, y \le n$)。保证输入图是一个 DAG。

接下来 $q$ 行，每行包含两个或三个整数，格式如下：

• “1 $u$ $x$” 表示第一种操作；
• “2 $u$ $x$” 表示第二种操作；
• “3 $u$” 表示第三种操作。

上述操作中的所有参数满足 $1 \le u \le n$ 且 $0 \le x \le 10^9$。

输出格式

对于每个第三种类型的操作，输出一行，包含一个整数：当前的 $val_u$。

样例

输入 1

4 4 7
1 2
1 3
3 4
2 4
1 1 5
1 2 1
3 3
3 4
2 1 3
3 2
3 3

输出 1

5
1
1
3