題目描述

这是 b059 もぺもぺ 的困难版本。

为了关停PhigrOS，统治局设计了乱序算法。乱序算法在PhigrOS中的体现便是幽蓝边界。幽蓝边界从巴别起便一直向像素塔的顶层吞噬而去。

被吞入幽蓝边界的人的数据会被乱序算法打乱。但作为碎数研 Firework Data Patcher 项目的负责人，你的任务便是复原这些数据。

统治局的乱序算法如下：

一个人的数据为一个长度为n的数列a，

算法总共会对a进行m轮乱序。

在每轮乱序中，算法新建一个数列b，并把a分为前半部分与后半部分。接着把后半部分最前的数字插入到b的最后，再把前半部分最前的数字插入到b的最后，如此交替下去。最后，算法把数列b的数字覆盖a原本的数字。

碎数研可以获得的信息只有数据的的长度和乱序的轮数，现在你需要尝试找出数据乱序后的第k个数是原本数列的第几个数。

輸入格式

有多组测资。

第一行包含一个整数 t —— 测资数量

对于每组测资，

第一行包括三个整数：n, m, k —— 数据长度，乱序轮数，目标数据的下标

保证n为偶数

輸出格式

对于每组测资输出一个整数 —— 乱序后的第k个数据在原数据的下标。

Samples

1
6 2 3

6

提示

范例一解释：

[1, 2, 3, 4, 5, 6] -> [4, 1, 5, 2, 6, 3] -> [2, 4, 6, 1, 3, 5]

乱序后第3个数字应是原本数据的第6个数字

 

本題測資較大，請使用較快的I/O方法。

1 ≤ t < 10⁵

1 ≤ k ≤ n < 10⁹

1 ≤ m < 10⁹

原始資料

• Zero1 題號：b062
• Hydro 題號：Z1062
• Locale：zh_TW
• Display：open