You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

迷宫（$\texttt{maze}$）

【题目描述】

露娜建造了一个迷宫，她要和朝日在这个迷宫里玩游戏。

露娜的迷宫有 $n$ 个房间，由 $m$ 条单向道路连接，保证每条道路都是从编号较小的房间连向编号较大的房间。

迷宫的每个房间 $u$ 里都有一个数字 $a_u$，初始都是 $0$。

朝日会对这个迷宫进行 $q$ 次操作，每次操作都是如下三种之一：

• 1 u x ，对于所有房间 $u$ 能通过迷宫道路到达的房间 $v$，令 $a_v\gets x$。
• 2 u x ，对于所有房间 $u$ 能通过迷宫道路到达的房间 $v$，令 $a_v\gets \min(a_v,x)$。
• 3 u，查询 $a_u$ 的值。

请你帮露娜回答所有朝日给出的询问。

【输入格式】

从 $\texttt{maze.in}$ 中读入数据。

第一行三个整数 $n,m,q$。

接下来 $m$ 行每行两个整数 $s_i,t_i$ 表示迷宫里一条 $s_i\to t_i$ 的道路。

接下来 $q$ 行每行两个或三个整数表示一次操作，输入格式见题目描述。

【输出格式】

输出到 $\texttt{maze.out}$ 中。

对于每个询问操作输出一行一个整数表示答案。

【样例 1 输入】

6 5 18
1 2
1 3
3 4
2 4
5 6
1 1 3
3 1
3 2
3 3
3 4
1 2 2
3 1
3 2
3 3
3 4
2 6 7
3 5
3 6
2 1 3
3 1
3 2
3 3
3 4

【样例 1 输出】

3
3
3
3
3
2
3
2
0
0
3
2
3
2

【数据范围】

对于所有测试数据：$n,m,q\le 10^5,s_i<t_i,0\le x\le 10^9$。