Ferry

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.

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.

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

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