Alice 和 Bob 总是很难选择晚餐的餐厅。之前他们玩过 Eenie Meenie Miney Mo 游戏,但最终随着餐厅列表的增加,他们不得不创建一个新游戏。这个新游戏开始时,他们在 $$$N$$$ 卡片上写下餐馆名称,并将卡片排成一行。游戏开始前,双方都选择起始卡牌和起始方向。他们按照顺序依次轮流。每回合结束后,他们会朝当前方向移动一张牌。如果他们到达卡片行的末尾或开头,他们就会改变方向。一旦他们在一张卡片上相遇,该卡片就会被标记为要移除,并在他们离开该卡片的第一时间被移除。
如何移除卡的示例
他们重复这个过程,直到只剩下一张餐厅卡。由于餐厅卡有很多,他们厌倦了一遍又一遍地模拟这个过程,需要你的帮助来确定剩下的最后一张卡。你能帮助他们吗?
输入
输入的第一行是一个整数 $$$T$$$ ($$$1$$$ $$$\leq$$$ $$$T$$$ $$$\leq$$$ $$$10^{4}$$$) 表示测试用例的数量。每个测试用例包含 3 行: 第一行包含一个整数 $$$N$$$ 表示初始卡片数量。下一行包含两个整数值 $$$A,B$$$ ($$$0$$$ $$$\leq$$$ $$$A, B$$$ < $$$N$$$, $$$2$$$ $$$\leq$$$ $$$N$$$ $$$\leq$$$ $$$10^{18}$$$) 表示数组中卡片从 0 开始的索引。最后一行包含两个字符串 $$$D_A, D_B$$$ $$$\in$$$ {"left", "right"} 表示它们移动的起始方向。
输出
输出包含 $$$T$$$ 整数 – 每个测试用例按顺序保留的最后一张卡的从 0 开始的索引。
示例
输入 #1
1 4 0 1 left right
输出 #1
0
注意
请注意,由于爱丽丝是从行的开头开始的,即使她的初始方向是向左,所以在她的下一步移动中,她将向右走。