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.