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
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10~ | ~n, q \le 5000~ |
2 | ~20~ | ~x = y~ trong mọi truy vấn |
3 | ~30~ | Chỉ có truy vấn loại ~2~ và ~3~ |
4 | ~40~ | Không có ràng buộc gì thêm |
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~.
Comments