Under construction

Still being built. Things may change

Ferry

Time limit2sMemory limit128 MB

Summary
Simulate a shuttling ferry with capacity M and crossing time t, picking up waiting passengers with priority for those who arrived earlier, and output each passenger's arrival time on the opposite bank.
Level

Medium6 of 10

Topics
Simulation, Queue, Greedy
Solved
No attempts yet

Problem

There are two docks on opposite sides of a river, labeled left and right. The ferry starts at the left dock. It can carry at most M people at a time, and each crossing takes t units of time in either direction.

When the ferry arrives at a dock, all passengers whose destination is that dock get off first. Then the ferry boards up to M passengers waiting at that dock. Boarding takes no time, and passengers who have waited longer board first. After boarding, the ferry crosses to the opposite dock.

If nobody is waiting at the dock where the ferry is located, the ferry waits there for the next passenger. If, while it is waiting, a passenger arrives first at the opposite dock, the ferry crosses to that dock.

Given the time and dock where each passenger arrives, determine when each passenger reaches the opposite dock, in the same order as the input.

Input

The first line contains three integers M, t, and N.

Each of the next N lines contains a passenger's arrival time and the dock where that passenger arrives. The dock is either left or right. Each arrival time is a nonnegative integer not greater than 100000.

Output

Print N lines. On the i-th line, print the time when the i-th passenger in the input reaches the opposite dock.

Constraints

  • 1 ≤ M ≤ 10,000
  • 1 ≤ t ≤ 10,000
  • 1 ≤ N ≤ 10,000

Examples2

  1. Example 1

    Input
    2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left
    Expected output
    10
30
30
50
50
70
70
90
90
110

  2. Example 2

    Input
    2 10 3
10 right
25 left
40 left
    Expected output
    30
40
60