Lihwy tuy là một Master Codeforces, Coordinator Bedao, Admin Vloy nhưng lại gặp khó khăn ở một bài toán sau, các bạn hãy giúp Lihwy nhé!

Cho hai số nguyên dương $n$ và $q$. Bạn cần thực hiện $q$ truy vấn sau trên ba dãy số nguyên dương $A$, $B$ và $C$ có $n$ phần tử:

$1$ $x$ $y$ $k$: Với mọi $0\le i<k$, ta thực hiện thao tác $B_{y+i}=A_{x+i}$.

$2$ $x$ $y$ $k$: Với mọi $0\le i<k$, ta thực hiện thao tác $C_{y+i}=B_{x+i}$.

$3$ $x$: In ra giá trị phần tử $C_x$.

Input

Dòng đầu tiên chứa hai số nguyên dương $n$ và $q$ $(1\le n,q\le 5\times {10}^5)$ - độ dài của dãy số nguyên dương và số lượng truy vấn.

Dòng thứ hai gồm $n$ số nguyên dương $A_1,A_2,...,A_n$ $(1\le A_i\le 5\times {10}^5)$.

Dòng thứ ba gồm $n$ số nguyên dương $B_1,B_2,...,B_n$ $(1\le B_i\le 5\times {10}^5)$.

Dòng thứ tư gồm $n$ số nguyên dương $C_1,C_2,...,C_n$ $(1\le C_i\le 5\times {10}^5)$.

$q$ dòng tiếp theo chứa một trong ba loại truy vấn. Với các truy vấn loại $1$ và $2$, dữ liệu đảm bảo $max(x,y)+k\le n+1$. Với các truy vấn loại $3$, ta luôn có $1\le x\le n$.

Output

Với mỗi truy vấn loại $3$, in ra đáp án.

Scoring

Sample Input 1

5 4
1 2 3 5 4
4 2 3 1 5
2 4 3 5 1
3 3
1 3 1 3
2 1 1 3
3 3

Sample Output 1

3
4

Notes

Tại trước thời điểm truy vấn $3$ đầu tiên, dãy $C$ là $[2,4,3,5,1]$. Do đó $C_3=3$.

Tại trước thời điểm truy vấn $3$ thứ hai, dãy $C$ là $[3,5,4,5,1]$. Do đó $C_3=4$.