题目描述

在摩尔多瓦的鲁特河旁有一个著名古建筑群。这个古建筑群由 $N$ 个古建筑和 $M$ 条单向道路组成。每条道路根据输入顺序都有一个编号，从前到后分别编号为 $1 \sim M$。

最近，科学家发现了一个由 Cucuteni 文化留下的数列！这个数列由 $T$ 个 $1 \sim M$ 的数组成。为了寻找这个数列的神秘意义，新来的实习生被要求执行以下操作：

最开始，实习生在某个古建筑处。其他科学家则开始将神秘数列的子序列一一念给他。假设当前实习生在第 $X$ 个古建筑，科学家念出的数为 $Z$，那么：

• 如果第 $Z$ 条道路的起点恰好是 $X$，那么实习生沿着这条道路走到相连的古建筑。

• 否则，实习生站在原地不动。

正值第 $8$ 界 EJOI 的举行，当地的科学家希望你能帮助他们解决如下 $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

提示

【数据范围】

本题采用 $\text{Subtask}$ 捆绑测试。

对于 $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$。