Phà vận chuyển hai bờ

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

Một phà chở tối đa cap xe mỗi chuyến và mất cross phút để sang bờ bên kia. Phà bắt đầu ở bờ trái lúc 0. Mỗi xe có thời điểm đến và bờ chờ. Xe ở mỗi bờ được phục vụ FIFO. Khi phà ở một bờ, nó chở tối đa cap xe đã đến ở bờ đó; nếu không có xe ở bờ hiện tại nhưng bờ kia đã có xe chờ, phà chạy rỗng sang đó; nếu cả hai chưa có xe, thời gian nhảy tới thời điểm xe tiếp theo đến.

Yêu cầu

Tính thời điểm mỗi xe tới bờ đối diện, theo đúng thứ tự xe trong input.

Input

• Dòng 1: cap cross m.
• m dòng tiếp theo: arrival side, với side là left hoặc right; arrival không giảm.

Output

In m dòng, dòng i là thời điểm xe i tới bờ đối diện.

Ràng buộc

• 1 <= cap <= 100
• 1 <= cross <= 1000
• 1 <= m <= 10^4
• 0 <= arrival <= 10^9

Chấm điểm

Ví dụ 1

Input

2 10 4
0 left
10 left
10 right
20 right

Output

10
30
20
40

Giải thích. Xe 1 đi chuyến 0→10; tại 10 phà ở phải nên chở xe 3 về trái tới20; sau đó lần lượt xử lý xe 2 và 4.

Ví dụ 2

Input

1 5 3
0 left
0 right
10 left

Output

5
10
15

Giải thích. Phà luân phiên hai bờ do mỗi chuyến chỉ chở một xe.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 10901 – Ferry Loading III.

Tham khảo: https://onlinejudge.org/external/109/10901.pdf