题目描述

在桥梁还不普遍的时候，渡船被用来运送汽车过河。与大型渡船不同，内河渡船沿着一条引导线行驶，并由河流的水流提供动力。汽车从渡船的一端驶上渡船，渡船过河后，汽车从渡船的另一端驶出。

有一艘渡船，它能在 $t$ 分钟内运送 $n$ 辆汽车过河，然后再花 $t$ 分钟返回。汽车可以到达河岸的任意一侧，等待渡船将其运送到对岸。只要渡船上载有汽车，或者在河岸的任意一侧至少有一辆汽车等待，渡船就会在两岸之间持续往返。每当渡船到达其中一岸时，它会卸载货物，并装载最多 $n$ 辆等待过河的汽车。如果等待的汽车数量超过 $n$ 辆，会先装载等待时间最长的那些汽车。如果两岸都没有汽车等待，渡船会一直等待，直到有汽车到达，然后装载该汽车（如果汽车到达的是渡船所在的那一岸）并过河。那么每辆汽车在什么时间到达对岸呢？

输入

输入的第一行包含 $c$，表示测试用例的数量。每个测试用例以 $n$、$t$、$m$ 开始。接下来有 $m$ 行，每行给出一辆汽车的到达时间（从当天开始经过的分钟数），以及汽车到达的河岸（$“left” 或 “right”$）。

输出

对于每个测试用例，按照输入的顺序，为每辆汽车输出一行，给出该汽车在对岸卸载的时间。每个测试用例之间输出一个空行。

你可以假设 $0 < n, t, m \leq 10000$。每个测试用例中汽车的到达时间严格递增。渡船初始在左岸。装载和卸载的时间可视为 0。

输入数据 1

2
2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left
2 10 3
10 right
25 left
40 left

输出数据 1

10
30
30
50
50
70
70
90
90
110

30
40
60

题目来源

Waterloo local 2005.09.17