Restaurant Game

题意翻译

Alice 和 Bob 又在玩游戏。有 $n$ 个格子，下标分别为 $0,1,2 \cdots n-1$。 初始 Alice 和 Bob 各有一颗棋子，位置分别在 $A,B$，并且有个方向（左或者右）。 Alice 和 Bob 将轮流移动棋子，Alice 先手。 他们会将棋子按照现在的方向移动一格，如果到头了就调转方向。 如果 Alice 和 Bob 的棋子同时放到某个格子上后，这个格子将会在他们的棋子都离开这个格子后被删除。 现在，你需要求出，最后剩下的格子是哪个。

题目描述

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 removedThey 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?

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

1
4
0 1
left right

输出样例 #1

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.