E. Копирование данных
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очень часто приходится копировать большие объемы данных. Такая операция может потребовать больших затрат компьютерных ресурсов. В связи с этим, в этой задаче вам предлагается придумать способ быстрого копирования некоторой части одного массива чисел в другой.

Более формально, вам задано два массива целых чисел a1, a2, ..., an и b1, b2, ..., bn длины n. Также есть m запросов двух типов:

  1. Скопировать подотрезок массива a длины k, начиная с позиции x, в массив b, начиная с позиции y, то есть выполнить by + q = ax + q для всех целых q (0 ≤ q < k). Операция задана корректно — оба подотрезка целиком содержатся в массивах a и b соответственно.
  2. Определить значение в позиции x массива b, то есть найти значение 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.

Выходные данные

Для каждого запроса второго типа в отдельную строку выведите результат.

Примеры
Входные данные
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