Cặp ngăn xếp


Submit solution

Points: 2.4 (partial)
Time limit: 1.0s
Memory limit: 67M

Author:
Problem type

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
QDUY

Comments

There are no comments at the moment.