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~.