题目描述

小明把 $n$ ($n$ 为偶数)张牌按编号顺序 $1,2,3,...,n$ 排成一堆，然后开始洗牌。一次洗牌的过程如下:

1.对于一堆牌编号为 $a_1,a_2....a_n$，首先将牌分成均匀的两堆:

$a_1,a_2...a_m$和 $a_{m+1},a_{m+2}...a_n$ (其中$m=n/2$)

2.然后按顺序交叉插入:

$a_1,a_{m+1},a_2,a_{m+2}...a_{m},a_n$

洗牌过程总共重复了$k$ 次，请你编程帮助小明模拟洗牌的过程。

例如 $n=6$，初始时牌堆中牌的编号为 1,2,3,4,5,6。

首次洗牌时，会将牌分成 1,2,3 和 4,5,6 两堆，交叉插入后的结果为 1,4,2,5,3,6。

再次洗牌，会将牌分成 1,4,2 和 5,3,6两堆。交叉插入后得到 1,5,4,3,2,6。

输入

正整数 $n$ (牌的数量), $k$ (洗牌的次数), $x$ (牌的位置)。

输出

$n$ 张牌洗牌 $k$ 次后，牌堆中第 $x$ 张牌的编号。

6 2 5

2

400 300 200

368

提示

$1≤n,k≤1,000,1≤x≤n$， 保证 $n$ 是偶数。