P16872 [HackerEarth] Walter White is a well known chemist. He has hired Skinny Pete to transport some of his products to 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

输入格式

见题面

输出格式

见题面

样例输入
10 77 59 11 1 store 2 lab 3 store 4 store 5 store 6 store 7 lab 8 store 9 lab 10 store 11 lab 62 59 17 1 lab 2 store 3 lab 4 lab 5 store 6 lab 7 store 8 lab 9 store 10 store 11 store 12 store 13 store 14 lab 15 store 16 store 17 lab 8 11 5 1 store 2 store 3 store 4 store 5 lab 11 13 8 1 store 2 lab 3 lab 4 store 5 store 6 store 7 lab 8 store 2 96 29 1 lab 2 lab 3 lab 4 lab 5 store 6 store 7 store 8 store 9 store 10 store 11 store 12 lab 13 store 14 lab 15 store 16 lab 17 store 18 store 19 store 20 store 21 store 22 store 23 lab 24 store 25 store 26 store 27 lab 28 lab 29 store 96 87 65 1 store 2 store 3 store 4 lab 5 store 6 lab 7 lab 8 store 9 lab 10 lab 11 lab 12 store 13 lab 14 lab 15 lab 16 lab 17 store 18 lab 19 store 20 lab 21 store 22 store 23 store 24 lab 25 lab 26 store 27 store 28 lab 29 store 30 store 31 store 32 lab 33 lab 34 lab 35 lab 36 lab 37 store 38 lab 39 lab 40 store 41 lab 42 lab 43 store 44 lab 45 store 46 lab 47 store 48 lab 49 lab 50 store 51 store 52 lab 53 store 54 lab 55 lab 56 store 57 store 58 lab 59 lab 60 lab 61 lab 62 store 63 lab 64 lab 65 store 76 24 90 1 lab 2 lab 3 lab 4 store 5 lab 6 lab 7 lab 8 lab 9 lab 10 lab 11 lab 12 store 13 store 14 store 15 store 16 store 17 store 18 lab 19 store 20 store 21 store 22 store 23 lab 24 store 25 lab 26 lab 27 lab 28 store 29 store 30 lab 31 store 32 store 33 lab 34 lab 35 store 36 lab 37 store 38 store 39 store 40 store 41 store 42 lab 43 store 44 lab 45 store 46 lab 47 lab 48 lab 49 lab 50 store 51 lab 52 store 53 store 54 lab 55 store 56 store 57 store 58 lab 59 lab 60 lab 61 lab 62 lab 63 lab 64 lab 65 lab 66 store 67 store 68 store 69 store 70 store 71 store 72 lab 73 store 74 lab 75 lab 76 store 77 store 78 lab 79 lab 80 store 81 lab 82 lab 83 store 84 lab 85 lab 86 store 87 store 88 store 89 store 90 store 45 9 64 1 lab 2 store 3 lab 4 store 5 lab 6 lab 7 store 8 lab 9 lab 10 lab 11 store 12 store 13 lab 14 lab 15 lab 16 lab 17 lab 18 store 19 store 20 lab 21 lab 22 lab 23 lab 24 store 25 lab 26 store 27 lab 28 store 29 lab 30 store 31 store 32 lab 33 lab 34 store 35 store 36 lab 37 lab 38 lab 39 lab 40 store 41 lab 42 lab 43 store 44 lab 45 store 46 store 47 lab 48 store 49 lab 50 lab 51 lab 52 store 53 lab 54 store 55 lab 56 store 57 lab 58 lab 59 store 60 lab 61 store 62 lab 63 lab 64 lab 55 89 56 1 lab 2 store 3 lab 4 lab 5 store 6 lab 7 store 8 store 9 store 10 lab 11 store 12 store 13 lab 14 store 15 lab 16 lab 17 lab 18 store 19 lab 20 lab 21 store 22 lab 23 lab 24 store 25 lab 26 store 27 lab 28 store 29 lab 30 lab 31 lab 32 store 33 lab 34 store 35 lab 36 lab 37 store 38 store 39 lab 40 store 41 store 42 lab 43 store 44 lab 45 store 46 lab 47 lab 48 lab 49 lab 50 lab 51 store 52 lab 53 store 54 lab 55 store 56 store 38 55 96 1 store 2 lab 3 lab 4 store 5 store 6 store 7 store 8 store 9 store 10 store 11 lab 12 lab 13 store 14 lab 15 store 16 store 17 lab 18 lab 19 store 20 lab 21 lab 22 lab 23 lab 24 store 25 lab 26 store 27 store 28 lab 29 lab 30 store 31 store 32 lab 33 store 34 lab 35 lab 36 lab 37 store 38 lab 39 lab 40 lab 41 store 42 lab 43 lab 44 store 45 lab 46 store 47 lab 48 store 49 store 50 lab 51 lab 52 store 53 store 54 store 55 lab 56 store 57 lab 58 lab 59 lab 60 store 61 store 62 lab 63 store 64 store 65 store 66 lab 67 store 68 lab 69 lab 70 store 71 lab 72 store 73 lab 74 lab 75 lab 76 lab 77 store 78 store 79 lab 80 lab 81 store 82 lab 83 store 84 store 85 store 86 store 87 store 88 lab 89 lab 90 store 91 store 92 store 93 store 94 lab 95 lab 96 lab
样例输出
119 178 119 119 119 119 178 119 178 119 178 60 119 178 178 119 178 119 178 119 119 119 119 119 178 119 119 178 23 23 23 23 34 27 40 40 27 27 27 40 27 97 289 289 481 193 193 385 385 577 577 769 481 769 673 961 673 961 1153 1153 1345 1345 1537 865 1537 1729 1729 865 1057 1921 175 175 175 262 175 262 262 175 262 262 262 175 262 262 262 262 175 262 175 262 175 175 175 262 262 175 175 262 175 175 175 262 262 262 262 262 175 262 262 175 262 262 175 262 175 262 175 262 262 175 175 262 175 262 262 175 175 262 262 262 262 175 262 262 175 25 73 73 49 73 73 73 73 73 73 73 49 49 49 49 49 49 73 49 49 49 49 73 49 73 73 73 97 97 73 97 97 73 73 97 73 97 97 97 97 97 73 97 73 97 73 73 73 73 97 121 97 97 121 97 97 97 121 121 121 121 121 121 121 121 97 97 97 97 97 97 121 97 121 121 145 145 121 121 145 121 121 145 121 121 145 145 145 145 145 10 19 28 19 28 28 19 28 28 28 37 37 28 28 28 28 28 37 37 46 46 46 46 37 46 37 46 37 46 55 55 46 46 55 55 46 46 64 64 55 64 64 55 64 55 55 64 73 64 64 64 73 64 73 64 73 82 82 73 82 73 82 82 82 90 179 268 268 179 268 179 179 179 268 179 179 268 179 268 268 268 179 268 268 179 268 268 179 268 179 268 179 268 268 268 179 268 179 268 268 179 179 268 179 179 268 179 268 179 268 268 268 268 268 179 268 179 268 179 179 111 166 166 111 111 111 111 111 111 111 166 166 111 166 111 111 166 166 111 166 166 166 166 111 166 111 111 166 166 111 111 166 111 166 166 166 111 166 166 166 111 166 166 111 166 111 166 111 111 166 166 111 111 111 166 111 166 166 166 221 221 166 221 221 221 166 221 166 166 221 166 221 166 166 276 276 221 221 276 276 221 276 221 221 221 221 221 276 276 221 221 221 221 276 276 276