← 返回题目列表

Codeforces · 292/E

E. 复制数据

中文机器翻译题面 查看原题

我们经常需要复制大量信息。此类操作会占用大量计算机资源。因此,在这个问题中,建议您想出一种方法,将数字数组的某些部分快速复制到另一个数字数组中。

更正式地说,您有两个长度为 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