题目描述

题目译自 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 的查询，输出一行表示答案。

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

以下表示第一个示例第一个查询：

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

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

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

最后，广播数字 $5$，实习生可以通过相应的道路，实习生最终在遗址 $1$，这是对应查询的答案。

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

数据范围与提示

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

• $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$

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