CF1599B.Restaurant Game

Alice and Bob always had hard time choosing restaurant for the dinner. Previously they performed Eenie Meenie Miney Mo game, but eventually as their restaurant list grew, they had to create a new game. This new game starts as they write restaurant names on $N$ cards and align the cards in one line. Before the game begins, they both choose starting card and starting direction they are going to. They take turns in order one after another. After each turn, they move one card in their current direction. If they reach the end or beginning of the line of cards they change direction. Once they meet in a card, the card is marked for removal and is removed the first moment they both leave the card.

Example of how card is removed

They repeat this process until there is only one restaurant card left. Since there are a lot of restaurant cards, they are bored to simulate this process over and over and need your help to determine the last card that remains. Can you help them?

爱丽丝和鲍勃在晚餐时总是难以决定去哪家餐厅。以前他们玩“Eenie Meenie Miney Mo”游戏，但随着餐厅列表不断变长，他们不得不设计一个新游戏。这个新游戏开始时，他们将餐厅名称写在 $N$ 张卡片上，并将这些卡片排成一行。游戏开始前，两人各自选择一个起始卡片和一个初始移动方向。然后他们按顺序轮流行动。每次行动后，他们向当前方向移动一张卡片。若到达卡片行的最左端或最右端，则立即改变移动方向。一旦两人同时到达同一张卡片，该卡片即被标记为待移除，并在两人首次同时离开该卡片的时刻被移除。

卡片被移除过程示意图

他们不断重复这一过程，直到仅剩一张餐厅卡片为止。由于餐厅卡片数量众多，他们厌倦了一次又一次地手动模拟该过程，因此需要你的帮助来确定最后剩下的那张卡片。你能帮他们吗？

The first line of the input is one integer $T$ ($1$ $\leq$ $T$ $\leq$ $10^{4}$) representing number of test cases. Each test case contains 3 lines: The first line contains an integer $N$ representing initial number of cards. Next line contains two integer values $A,B$ ($0$ $\leq$ $A, B$ < $N$, $2$ $\leq$ $N$ $\leq$ $10^{18}$) representing starting 0-based index of the card in the array. Last line contains two strings $D_A, D_B$ $\in$ {"left", "right"} representing starting direction of their movement.

输入的第一行是一个整数 $T$（$1 \leq T \leq 10^{4}$），表示测试用例的数量。每个测试用例包含 3 行：第一行包含一个整数 $N$，表示初始的卡片数量；第二行包含两个整数 $A, B$（$0 \leq A, B < N$，且 $2 \leq N \leq 10^{18}$），表示数组中卡片的起始 0-based 索引；第三行包含两个字符串 $D_A, D_B \in \{\text{"left"}, \text{"right"}\}$，表示它们初始移动方向。

The output contains $T$ integer number – the 0-based index of the last card that remains for every test case in order.

输出包含 $T$ 个整数——依次为每个测试用例中最后剩余的卡片的从 0 开始计数的索引。

Note that since Alice is starting at the beginning of the line even though her initial direction is left, on her next move she will go right.

注意，尽管爱丽丝的初始方向是向左，但由于她从队列的起始位置开始，因此她的下一步将向右移动。