the-pinkman-store

Walter White is a well known chemist. He has hired Skinny Pete to transport some of his products to The Pinkman Store.
Things were running smooth until his special ingredients started falling short. As it is difficult to get that chemical
Mr. White made some changes to his formula. Now he wants a chemical, call it BrB, that is available only in The Pinkman Store.
But Pinkman must cook that chemical in his lab.
Skinny Pete is the only man Walter White can trust, so he has to do all the transportations. But since Skinny Pete is very skinny he can't 
carry more than N chemicals.

Initially Skinny Pete is at White's Lab. It takes Pete T minutes to reach the Pinkman Store. Now he has move back and forth from the lab to the store.
When the product is ready he has to transport it to the store and when the chemical in the store is ready transport it to the lab. 

Whenever the products are ready at the lab, Pete takes up to N products to store. If there are more than N products, those that have been
waiting the longest are taken first. Chemicals at the store are also treated in the same way. If there are no Products/Chemmicals
waiting on either side, Pete waits until any one is ready, takes it (if it's on the same place where is), and transports it. 

It is known that there are M items.

Now, Tuco wants to find at what time each Chemical/Product reaches its destination?  But since Tuco is very busy handling his own business he wants you to help him.

Input:

The first line of input contains C, the number of test cases.
Each test case begins with N, T, M.
M lines follow, each giving the time when the item is ready (in minutes since the beginning of the day), and where it is (store/lab).

Output:

For each test case, output one line per item, in the same order as the input, giving the time at which
that item reaches its destination. 
Output an empty line between cases.

You may assume that 0 < N, T, M ≤ 10000. The item's available time for each test case are strictly increasing. 
Pete doesn't waste any time. Assume it takes him 0 minutes to drop any item at store/lab.

SAMPLE INPUT
2
2 10 10
0 lab
10 lab
20 lab
30 lab
40 lab
50 lab
60 lab
70 lab
80 lab
90 lab
2 10 3
10 store
25 lab
40 lab

SAMPLE OUTPUT
10
30
30
50
50
70
70
90
90
110

30
40
60

Explanation

2nd Case:

Pete is initially at the lab. When the chemical is ready at store at time 10, he goes to the store (takes 10 minutes) and brings it to the lab.
(Total 30 minutes)

He takes the product (it was ready at 25th minute) to store at time 40.

He then goes back to the lab (reaches lab at time 50) and gets the product at time 60.

Note: You have to output the time for each item in the order as given in the input

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: