P12359 [eJOI 2024] 古迹漫步 / Old Orhei

在摩尔多瓦的鲁特河旁有一个著名古建筑群。这个古建筑群由 $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` 输出答案，每行一个。

**【数据范围】** **本题采用 $\text{Subtask}$ 捆绑测试。** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$7$|$Q=1$，且唯一一个问题是问题 `1`| |$2$|$16$|$N=2$| |$3$|$17$|$M=N-1,X_i=i,Y_i=i+1$| |$4$|$31$|保证没有问题 `2`，且 $T \le 3 \times 10^4$| |$5$|$29$|无| 对于 $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$。