You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小$A$有$n$只编号为$1, 2, 3, ..., n-1, n$的狗狗。初始时，狗狗们按编号升序排列在位置上（位置从$1$到$n$）。它们正在玩一个交换游戏，游戏规则如下：

每秒进行一次交换操作。

当秒数为奇数时（第$1$、$3$、$5$...秒），交换位置为 $2i-1$ 和 $2i$ 的狗狗（其中 $1 \leq i \leq \lfloor \frac{n}{2} \rfloor$）。

例如，当 $n=5$ 时，初始序列为 $1, 2, 3, 4, 5$，第$1$秒后（奇数秒），序列变为 $2, 1, 4, 3, 5$。

当秒数为偶数时（第$2$、$4$、$6$...秒），交换位置为 $2i$ 和 $2i+1$ 的狗狗（其中 $1 \leq i \leq \lfloor \frac{n-1}{2} \rfloor$）。

例如，当 $n=5$ 且当前序列为 $2, 1, 4, 3, 5$（第$1$秒后），第$2$秒（偶数秒）后，序列变为 $2, 4, 1, 5, 3$。

小$A$想知道，经过k秒后，编号为q的狗狗位于哪个位置？

输入描述

输入包含多个测试用例。第一行是整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。

每个测试用例占一行，包含三个整数 $n, k, q$（$1 \leq n, k, q \leq 10^9$）。

输出描述

对每个测试用例，输出一个整数，表示经过k秒后，编号为q的狗狗所在的位置。

示例输入

3  
5 1 3  
5 2 3  
6 1 4  

示例输出

4  
5  
3  

示例解释

第一个测试用例：初始序列为 $1, 2, 3, 4, 5$。1秒后（奇数秒），交换位置$1-2$和$3-4$，序列变为 $2, 1, 4, 3, 5$。编号为$3$的狗狗位于位置$4$。

第二个测试用例：$2$ 秒后（第$2$秒是偶数秒），在$1$秒后的序列 $2, 1, 4, 3, 5$ 基础上，交换位置$2-3$和$4-5$（注意 $i \leq \lfloor (5-1)/2 \rfloor=2$，即$i=1$时交换$2-3$，$i=2$时交换$4-5$），序列变为 $2, 4, 1, 5, 3$。编号为$3$的狗狗位于位置5。

第三个测试用例：$n=6$，$k=1$（奇数秒），交换位置$1-2、3-4、5-6$（因为 $\lfloor 6/2 \rfloor=3$），初始序列 $1,2,3,4,5,6$ 变为 $2,1,4,3,6,5$。编号为$4$的狗狗位于位置$3$。

限制与约定

对于 $40\%$的样例，保证 $1 \le t \le 10$ $n, k, q$（$1 \leq n, k, q \leq 100$）。

对于 $100\%$的样例，保证 $1 \le t \le 10^5$ $n, k, q$（$1 \leq n, k, q \leq 10^9$）

• 时间限制: $1 s$
• 空间限制: $256 MB$