We often have to copy large volumes of information. Such operation can take up many computer resources. Therefore, in this problem you are advised to come up with a way to copy some part of a number array into another one, quickly.

More formally, you've got two arrays of integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ and $*b*_{1}, *b*_{2}, ..., *b*_{*n*}$ of length $*n*$. Also, you've got $*m*$ queries of two types:

1. Copy the subsegment of array $*a*$ of length $*k*$, starting from position $*x*$, into array $*b*$, starting from position $*y*$, that is, execute $*b*_{*y* + *q*} = *a*_{*x* + *q*}$ for all integer $*q*$ $(0 ≤ *q* < *k*)$. The given operation is correct — both subsegments do not touch unexistent elements.
2. Determine the value in position $*x*$ of array $*b*$, that is, find value $*b*_{*x*}$.

For each query of the second type print the result — the value of the corresponding element of array $*b*$.

Input

The first line contains two space-separated integers $*n*$ and $*m*$ $(1 ≤ *n*, *m* ≤ 10^{5})$ — the number of elements in the arrays and the number of queries, correspondingly. The second line contains an array of integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(|*a*_{*i*}| ≤ 10^{9})$. The third line contains an array of integers $*b*_{1}, *b*_{2}, ..., *b*_{*n*}$ $(|*b*_{*i*}| ≤ 10^{9})$.

Next $*m*$ lines contain the descriptions of the queries. The $*i*$-th line first contains integer $*t*_{*i*}$ — the type of the $*i*$-th query $(1 ≤ *t*_{*i*} ≤ 2)$. If $*t*_{*i*} = 1$, then the $*i*$-th query means the copying operation. If $*t*_{*i*} = 2$, then the $*i*$-th query means taking the value in array $*b*$. If $*t*_{*i*} = 1$, then the query type is followed by three integers $*x*_{*i*}, *y*_{*i*}, *k*_{*i*}$ $(1 ≤ *x*_{*i*}, *y*_{*i*}, *k*_{*i*} ≤ *n*)$ — the parameters of the copying query. If $*t*_{*i*} = 2$, then the query type is followed by integer $*x*_{*i*}$ $(1 ≤ *x*_{*i*} ≤ *n*)$ — the position in array $*b*$.

All numbers in the lines are separated with single spaces. It is guaranteed that all the queries are correct, that is, the copying borders fit into the borders of arrays $*a*$ and $*b*$.

Output

For each second type query print the result on a single line.