珅泽教育的小婷老师正在组织一项队列实践，她请小泽按下面的规则完成记录。

有多组渡船调度。渡船初始在左岸，每次最多装 $N$ 辆车，过河需要 $T$ 分钟。每辆车给出到达码头的时刻和岸边 left 或 right；同岸车辆必须按到达顺序上船。

渡船在当前岸有已到车辆时立即装满或装完并过河；当前岸无车但对岸已有等待车辆时空船过河；两岸都没有已到车辆时等待下一辆车到达。请按输入顺序输出每辆车到达对岸的时刻。

输入格式

第一行输入测试组数 C。

每组先输入 N,T,M，随后 M 行输入到达时刻和岸边。

输出格式

每组输出 M 行到达对岸时刻，组间空一行。

1
2 3 7
4 right
8 left
9 left
9 right
13 left
15 left
17 right

10
13
13
16
19
19
22

1
3 4 9
4 right
5 left
8 left
8 right
8 left
8 left
9 right
12 left
12 left

12
16
16
12
16
24
20
24
24

1
4 5 11
3 right
5 left
5 left
9 right
9 left
10 left
13 right
16 left
20 left
22 right
25 left

13
18
18
23
18
18
23
28
28
33
38

数据范围与约定

• $1 \le N,T,M \le 10^4$
• 车辆按到达时刻不下降给出