Sao chép dữ liệu (Copying Data)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có hai mảng $A$ và $B$. Hỗ trợ sao chép một đoạn của $A$ sang đoạn tương ứng của $B$ và truy vấn một vị trí của $B$.

Input

Dòng đầu chứa $n,m$. Dòng 2 là $A$, dòng 3 là $B$. Mỗi truy vấn:

• 1 x y k: với $0\le d<k$, gán $B_{y+d}=A_{x+d}$.
• 2 x: in $B_x$.

Các truy vấn sao chép luôn nằm trong biên hai mảng.

Output

In một dòng cho mỗi truy vấn loại 2.

Subtask

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

Ví dụ

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

Giải thích

Các truy vấn sao chép không sửa mảng $A$ mà chỉ thay những vị trí tương ứng trong $B$. Vì các lần sao chép có thể chồng lấn, truy vấn điểm phải dùng lần gán gần nhất phủ vị trí đó. Dãy kết quả là 0 3 -1 3 2 3 -1.