题目描述

题目译自 eJOI2024 Day1 T3. Old Orhei

古奥尔海 (Orheiul Vechi) 是位于拉乌河狭窄河湾上的一个自然和历史遗址。这里有 $N$ 处考古遗址和 $M$ 条单向道路连接这些遗址。每条道路的编号唯一，按输入顺序 $1$ 到 $M$ 给出。

最近，当地科学家发现了一个由库库特尼-特里皮利亚文明留下的数组。该数组由 $T$ 个 $1$ 到 $M$ 之间的整数组成。为了弄清楚这个数组的神秘含义，新来的实习生将被指导遵循以下步骤：

• 一开始，实习生会在某个考古遗址。
• 其他科学家开始向他依次广播数组的一个连续子数组（先广播子数组的第一个元素，然后是第二个元素，依此类推）。
• 实习生根据以下规则更改其位置：
  • 如果实习生当前的位置等于相应道路的起点，实习生将通过该道路前往相应道路的终点。
  • 否则，实习生什么也不做，留在当前位置。

借第八届欧洲青少年信息学奥林匹克竞赛的机会，当地科学家请你帮助他们执行以下 $Q$ 个操作：

• 1 L R S - 科学家们想知道如果实习生最初位于第 $S$ 处遗址，并且只广播初始数组中从编号 $L$ 开始到 $R$ 结束的连续子数组，实习生的最终位置会是什么。
• 2 i K - 科学家们将数组 $A$ 的第 $i$ 个元素修改为 $K$。更改是永久的。

你的任务是正确回答所有类型 $1$ 的询问。

---

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$，分别表示考古遗址和单向道路的数量。

接下来的 $M$ 行包含道路的描述。具体来说，第 $i$ 行将包含两个用空格分隔的数字，表示第 $i$ 条道路从 $X_{i}$ 开始，到 $Y_{i}$ 结束。可能存在道路 $X_{i}=Y_{i}$ 以及成对的道路 $X_{i}=X_{j}$, $Y_{i}=Y_{j}$ 但 $i \neq j$。

接下来的第 $T$ 行包含一个整数 $T$，表示发现的数组的长度。

接下来的一行包含 $T$ 个用空格分隔的整数 $A_{1}, A_{2} \ldots A_{T}$，表示数组元素。

接下来的一行包含一个整数 $Q$，表示操作的数量。

接下来的 $Q$ 行每行描述了一个操作：

• 1 L R S 表示类型 $1$ 的询问。
• 2 i K 表示类型 $2$ 的操作。

---

输出格式

对于每个类型 $1$ 的查询，输出一行表示答案。

---

样例 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

解释
第一个查询的过程：

1. 实习生从遗址 $2$ 开始，广播的子数组是 $[4,2,5]$。

2. 

3. 广播数字 $4$：可以通过编号为 $4$ 的道路，实习生移动到遗址 $5$。

4. 

5. 广播数字 $2$：编号为 $2$ 的道路无法使用，实习生保持在同一位置。

6. 广播数字 $5$：可以通过相应的道路，实习生移动到遗址 $1$。

7. 

8. 最终答案：$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

---

样例 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

---

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 50$
• $1 \leq M, T, Q \leq 10^{5}$
• $1 \leq X_{i}, Y_{i} \leq N$
• $1 \leq A_{i} \leq M$
• $1 \leq L \leq R \leq T$
• $1 \leq S \leq N$
• $1 \leq i \leq T$
• $1 \leq K \leq M$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
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 \leq 3 \cdot 10^{4}$
5	29	无附加限制

---