Copying Data

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Given arrays $A$ and $B$, copy a subarray of $A$ into a corresponding subarray of $B$ and query single positions of $B$.

Input

The first line contains $n,m$, followed by arrays $A$ and $B$. Queries are:

• 1 x y k: for $0\le d<k$, set $B_{y+d}=A_{x+d}$.
• 2 x: print $B_x$.

Every copy range is guaranteed to fit both arrays.

Output

Print one line for every type 2 query.

Subtasks

• 20 points: $n,m\le50$.
• 30 points: $n,m\le5000$.
• 50 points: $n,m\le10^5$, $|A_i|,|B_i|\le10^9$.

Examples

Input

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

Output

0
3
-1
3
2
3
-1

Explanation

Copy operations never modify $A$; they only replace covered positions of $B$. Because copy ranges may overlap, a point query must use the most recent assignment covering that position. The outputs are 0 3 -1 3 2 3 -1.