我们经常需要复制大量信息。此类操作会占用大量计算机资源。因此,在这个问题中,建议您想出一种方法,将数字数组的某些部分快速复制到另一个数字数组中。
更正式地说,您有两个长度为 n 的整数数组 a1, a2, ..., an 和 b1, b2, ..., bn。另外,您还有两种类型的 m 个查询:
1、将数组a中从位置x开始长度为k的子段复制到数组b中从位置y开始,即对所有整数q(0 ≤ q < k)执行 + q = ax + q。给定的操作是正确的——两个子段都没有触及不存在的元素。
2、确定数组b的位置x的值,即求值bx。
对于第二种类型的每个查询,打印结果 — 数组 b 的相应元素的值。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — 相应地,数组中的元素数量和查询数量。第二行包含整数数组 a1, a2, ..., an (|ai| ≤ 109)。第三行包含整数数组 b1, b2, ..., bn (|bi| ≤ 109)。
接下来的 m 行包含查询的描述。第 i 行首先包含整数 ti — 第 i 个查询的类型 (1 ≤ ti ≤ 2)。如果ti = 1,则第i次查询意味着复制操作。如果ti = 2,则第i次查询意味着取数组b中的值。如果 ti = 1,则查询类型后跟三个整数 xi, yi, ki (1 ≤ xi, yi, ki ≤ n) — 复制查询的参数。如果 ti = 2,则查询类型后跟整数 xi (1 ≤ xi ≤ n) — 数组 b 中的位置。
行中的所有数字均以单个空格分隔。保证所有查询都是正确的,即复制边界适合数组a和b的边界。
输出
对于每个第二种类型的查询,将结果打印在一行上。
示例
输入 #1
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
输出 #1
0 3 -1 3 2 3 -1