down

题目描述

给定两个长度为 $m$ 的整数序列 $a,b$ 。

我们会进行 $q$ 次操作，操作包含两种：

一. 修改操作：给定 $x,a',b'$ ，令 $a_x:=a',b_x:=b'$ 。

二. 查询操作：给定 $t,z,o$ ，你需要回答以下问题：

有一个长度为 $n$ 的排列 $p$ ，初始满足 $\forall 1\le i\le n,p_i=i$ 。

接下来枚举 $i=1,2,\dots,t$ ，并交换 $p_{a_i}$ 和 $p_{b_i}$ 的值。

若 $o=1$ ，你需要输出此时 $p_z$ 的值；若 $o=2$ ，你需要求出 $1\le y\le n$ ，满足 $p_y=z$ 并输出 $y$ 。

输入格式

第一行包含三个整数 $n,m,q$ 。

第二行包含 $m$ 个整数，其中第 $i$ 个整数为 $a_i$ 。

第三行包含 $m$ 个整数，其中第 $i$ 个整数为 $b_i$ 。

接下来 $q$ 行，每行包含四个整数，代表一次操作。设其中第一个整数为 $opt$ 。

若 $opt=1$ ，则这是一个修改操作，接下来三个整数为 $x,a',b'$ 。

若 $opt=2$ ，则这是一个查询操作，接下来三个整数为 $t,z,o$ 。

输出格式

对于每个 $opt=2$ 的操作，输出一行一个整数，表示这次查询的答案。

样例

样例 1 输入

8 8 10
8 5 3 2 2 6 7 5 
7 2 6 3 8 8 4 1
1 8 1 5
2 3 5 2
1 6 4 5
2 3 7 2
2 7 5 2
2 6 2 1
2 1 7 1
1 6 6 4
2 1 4 1
1 4 5 7

样例 1 输出

2
8
3
7
8
4

样例 2~5

见下发文件。

数据范围

所有数据满足：$1\le n,m,q\le 3*10^5,1\le a_i,b_i\le n,1\le opt\le 2,a_i\neq b_i$ 。

对于一次修改操作，$1\le x\le m,1\le a',b'\le n,a'\neq b'$ 。

对于一次查询操作，$1\le t\le m,1\le z\le n,1\le o\le 2$ 。

特殊性质 A ：$\forall 1\le i\le m,a_i=1$ ；$a'=1$ 。