Old Orhei (Orheiul Vechi) 是一个位于 Răut 河狭窄河湾处的自然和历史遗迹群。它由 $N$ 个考古遗迹和 $M$ 条连接某些遗迹对的单向道路组成。每条道路都有一个介于 $1$ 和 $M$ 之间的唯一编号，由输入中给出的顺序定义。请参考“样例”部分以可视化此类配置。

最近，当地科学家发现了一串由 Cucuteni–Trypillia 文明留下的数组。该数组由 $T$ 个介于 $1$ 和 $M$ 之间的整数组成。为了弄清这个数组的神秘含义，实习生被要求遵循以下程序：

起初，实习生从某个初始考古遗迹出发。其他科学家开始向他广播主数组的一个连续子数组（首先广播子数组的第一个元素，然后是第二个，依此类推）。实习生随后根据以下规则改变他的位置：

• 如果实习生可以使用当前广播编号对应的道路（换句话说，实习生当前所在位置等于相应道路的起点），则实习生穿过该道路（前往相应道路的终点）。
• 否则，实习生不执行任何操作，并保持在当前位置。

值此第 8 届欧洲青少年信息学奥林匹克竞赛之际，当地科学家请求你帮助他们执行以下 $Q$ 次查询：

• $1\ L\ R\ S$ - 科学家想知道，如果实习生最初位于第 $S$ 个遗迹，且仅广播初始数组中从索引 $L$ 到索引 $R$ 的连续子数组，实习生最终会位于何处。
• $2\ i\ K$ - 科学家将数组的第 $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$ 个空格分隔的整数 $A_1, A_2, \dots, A_T$，表示数组元素。

下一行包含一个整数 $Q$，表示查询的数量。

接下来的 $Q$ 行包含查询描述： $1\ L\ R\ S$ 表示类型 1 的查询。 $2\ i\ K$ 表示类型 2 的查询。

输出格式

对于每个类型 1 的查询，在单独的一行中输出答案。

样例

注意，某些样例对于所有测试组而言并非有效输入。

以下是第一个样例中第一个查询的表示： 最初，实习生从遗迹 2 出发，广播的子数组为 $[4, 2, 5]$。

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

随后，广播数字 2。实习生保持在相同位置，因为编号为 2 的道路无法使用。

最后，广播数字 5，实习生可以穿过相应的道路，因此实习生最终停在遗迹 1，这就是该查询的答案。

第三个样例的说明： 对于第一个查询，实习生将连续两次穿过从遗迹 1 到其自身的第 1 条道路，因此该查询的答案为 1。

第二个查询将数组的第一个元素更新为 2。

在第三个查询期间，数字 2 首先被广播给位于遗迹 1 的实习生。由于相应的道路与该遗迹相邻，实习生穿过它并移动到遗迹 2。最后，广播数字 1，实习生无法穿过相应的道路，因此实习生的最终位置是遗迹 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
1
2

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

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

样例输出 3

1
2

数据范围

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

子任务

Figure 1. 实习生从遗迹 2 出发