Cặp ngăn xếp
Hai ngăn xếp \(A\) và \(B\) được lập trình với mối quan hệ như sau: phần tử bị POP ở \(A\) sẽ được PUSH vào \(B\) và phần tử bị POP ở \(B\) sẽ được PUSH vào \(A\).
Một số thao tác PUSH và POP được thực hiện một cách bí mật. Cho biết các phần tử trong \(A\) và \(B\) sau khi thực hiện các thao tác và thứ tự thực hiện các thao tác, bạn hãy xác đinh các thao tác PUSH ban đầu.
Đầu vào
Dòng đầu tiên chứa ba số nguyên \(m, n, p\) \((1 \le m + n, p \le 2*10^5)\) lần lượt là số phần tử trong ngăn xếp \(A\), \(B\) sau \(p\) thao tác.
Dòng thứ hai chứa \(m\) số nguyên là các phần tử của ngăn xếp \(A\).
Dòng thứ ba chứa \(n\) số nguyên là các phần tử của ngăn xếp \(B\).
Dòng cuối cùng chứa \(p\) xâu PUSH_A
, PUSH_B
, POP_A
hoặc POP_B
cho biết thứ tự các thao tác được thực hiện:
PUSH_A x
chèn số nguyên \(x\) vào ngăn xếp \(A\).PUSH_B x
chèn số nguyên \(x\) vào ngăn xếp \(B\).POP_A
xóa một số nguyên ở ngăn xếp \(A\).POP_B
xóa một số nguyên ở ngăn xếp \(B\).
Các phần tử của ngăn xếp được in ra theo thứ tự chèn: từ thêm trước tới thêm cuối cùng. Đầu vào đảm bảo luôn tìm được một lời giải.
Đầu ra
Một dãy số nguyên duy nhất là các phần tử được chèn vào tại từng lần PUSH.
Ví dụ
Đầu vào:
2 2 5
1 2
3 4
PUSH_A PUSH_A PUSH_A POP_A PUSH_B
Đầu ra:
2 1 4 3
Giải thích: Thực hiện \(5\) thao tác sau thu được ngăn xếp \(A: {1, 2}\) và \(B: {3, 4}\).
PUSH_A 2
PUSH_A 1
PUSH_A 4
POP_A
PUSH_B 3
Comments