题目描述

给定两个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$。

接下来有 $m$ 次操作，操作分为如下两种类型：

• $\mathtt{1\ x\ y\ k}$：将数列 $b$ 中下标从 $y$ 开始的连续 $k$ 个元素用数列 $a$ 中下标从 $x$ 开始的连续 $k$ 个数替换，即：$b_y \leftarrow a_x$，$b_{y+1} \leftarrow a_{x+1}$，$b_{y+2} \leftarrow a_{x+2}$，……，$b_{y+k-1} \leftarrow a_{x+k-1}$；
• $\mathtt{2\ x}$：查询 $b_x$ 的数值。

对于每次查询操作，输出对应的结果。

输入格式

第一行，两个整数 $n$ 和 $m$，分别表示数列长度以及操作次数（$1 \le n,m \le 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(|a_i| \le 10^9)$。

第三行，$n$ 个整数 $b_1, b_2, \ldots, b_n(|b_i| \le 10^9)$。

接下来 $q$ 行，每行包含依次操作，格式为 $\mathtt{1\ x\ y\ k}$（$1 \le x,y,k \le n$ 且 $\max\{ x+k-1, y+k-1 \} \le n$）或 $\mathtt{2\ x}$（$1 \le x \le n$）。

输出格式

对于每次查询操作 $\mathtt{2\ x}$，输出一行，包含一个整数，表示 $b_x$ 的数值。

样例

5 10
1 2 0 -1 3
3 1 5 -2 0
2 5
1 3 3 3
2 5
2 4
2 1
1 2 1 4
2 1
2 4
1 4 2 1
2 2

0
3
-1
3
2
3
-1

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n,m \le 10$
• 对于 $50\%$ 的数据，$n,m \le 1000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^5$