Hàng đợi theo nhóm

Bối cảnh và bài toán

Một trung tâm dịch vụ có nhiều nhóm khách. Khi một người vào hàng, nếu nhóm của họ đã có người đang chờ thì người mới đứng ngay sau người cuối cùng của chính nhóm; nếu chưa có ai của nhóm đó, nhóm được xếp cuối hàng. Khi phục vụ, lấy người đầu của nhóm đầu hàng.

Yêu cầu

Xử lý các lệnh ENQUEUE x và DEQUEUE; với mỗi DEQUEUE, in ID người được phục vụ.

Input

• Dòng 1: số nhóm T.
• T dòng tiếp theo: k rồi k ID thuộc nhóm đó.
• Dòng tiếp: số lệnh q.
• q dòng lệnh. Mọi ID trong ENQUEUE đều đã khai báo; mọi DEQUEUE đều hợp lệ.

Output

Mỗi DEQUEUE in một ID trên một dòng.

Ràng buộc

• 1 <= T <= 1000
• Tổng số ID khai báo <= 2 * 10^5
• 1 <= q <= 2 * 10^5

Chấm điểm

Ví dụ 1

Input

2
3 101 102 103
2 201 202
6
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
DEQUEUE
DEQUEUE
DEQUEUE

Output

101
102
201

Giải thích. 102 cùng nhóm với 101 nên được đặt sau 101 và trước nhóm của 201.

Ví dụ 2

Input

1
3 1 2 3
4
ENQUEUE 3
ENQUEUE 1
DEQUEUE
DEQUEUE

Output

3
1

Giải thích. Trong một nhóm, thứ tự vẫn FIFO.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 540 – Team Queue.

Tham khảo: https://onlinejudge.org/external/5/540.pdf