题目描述

在遥远的未来，人类发明了时空传送网络。这个网络由 $N$ 个时空站和 $M$ 条单向时空通道组成。每条时空通道都有一个唯一的识别编号，从古至今依次编号为 $1 \sim M$。

最近，时空管理局在一次考古发掘中，发现了一段由失落文明留下的时空导航序列！这个序列由 $T$ 个 $1 \sim M$ 的数组成，代表了他们曾经使用过的通道编号。为了解密这段序列蕴含的意义，新来的时空旅行者实习生被要求执行一段路径重构模拟：

最开始，实习生会从某个指定的时空站出发。接着，系统会按顺序向他念出时空导航序列的一个子序列。假设当前实习生在第 $X$ 个时空站，系统念出的通道编号是 $Z$，那么：

• 如果第 $Z$ 条时空通道的起点恰好是 $X$，那么实习生将通过这条通道，瞬间移动到相连的终点时空站。

• 否则（即第 $Z$ 条通道的起点不是 $X$），实习生将留在原地，等待下一个指令。

时空管理局急需高效地利用这段导航序列。因此，他们希望你能帮助他们解决如下 $Q$ 个关于路径重构的问题：

• 1 L R S：管理局想知道，如果最开始实习生站在第 $S$ 个时空站处，然后他们按照时空导航序列中第 $L \sim R$ 项的顺序进行路径重构，那么实习生最终会停留在哪个时空站。

• 2 i K：由于导航序列在传输过程中可能出现错误，管理局需要将时空导航序列的第 $i$ 项的值修正为 $K$。

你需要对于所有类型为 1 的问题，给出实习生最终停留的时空站编号！

输入格式

第一行，两个正整数 $N,M$，分别表示时空站的数量和时空通道的数量；

接下来 $M$ 行，第 $i$ 行两个整数 $X_i,Y_i$，表示第 $i$ 条时空通道的起点站和终点站；

接下来一行一个正整数 $T$，表示时空导航序列的长度；

接下来一行 $T$ 个整数 $A_1,A_2,\dots,A_T$，表示时空导航序列；

接下来一行一个正整数 $Q$，表示需要解决的问题数量；

接下来 $Q$ 行，每行一个问题。格式见题目描述。

输出格式

对于所有类型为 1 的问题输出答案（即最终时空站的编号），每行一个。

5 6
1 2
3 2
4 2
2 5
5 1
4 5
6
2 1 4 2 5 3
3
1 3 5 2
1 3 5 2
1 1 2 3

1
1
2

3 3
1 2
2 3
3 1
4
3 1 1 2
4
1 1 2 3
2 2 2
1 1 2 3
1 1 4 2

2
1
3

2 3
1 1
1 2
1 2
4
1 1 2 3
3
1 1 2 1
2 1 2
1 1 2 1

1
2

提示

【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 50,1 \le M,T,Q\le 10^5,1\le X_i,Y_i\le N,1 \le A_i \le M,1 \le L \le R \le T,1 \le S \le N,1 \le i \le T,1\le K\le M$。