「CROI · R2」在相思树下 I

>年年桃树下 > >常看一个变成俩 > >小小心愿常比划 > >快快实现吧 > >却没看到他也在树下 > >相逢二字纵使隔天涯 > >转角总会遇上他 > >缘分缘分啊

**本题采用多组数据测试。** 现在欣欣有一个从 $1$ 到 $n$ 的序列，并想对这个序列进行如下两种操作。 操作一：删去所有的奇数项。 操作二：删去所有的偶数项。 欣欣发现她在进行 $k$ 次操作后，最后只剩下一个数，但她不知道这个数是多少，于是欣欣来找你求助，她会给你她所进行的 $k$ 次操作的种类，希望你告诉她最后的那个数是多少。

第一行一个正整数 $T$，表示数据组数。 对于每组数据： 第一行两个整数 $n$ 和 $k$，含义如题面所示。 第二行 $k$ 个整数，代表欣欣依次进行的操作种类，其中 $1$ 代表操作一，$2$ 代表操作二。

共 $T$ 行，每行一个数代表每组数据对应的答案。

4
5 2
1 1
8 3
2 2 2 
8 3 
1 1 1
8 3
1 2 1

4
1
8
6

**【样例解释】** 对于第一组数据，序列的变化如下： $\{1,2,3,4,5\} \to \{2,4\} \to \{4\}$。 **【数据范围】** 对于 $30\%$ 的数据， $n\le 5\times10^5$。 对于 $100\%$ 的数据，$1\le T \le 10$，$1\le n\le 10^{18}$。 保证对于所有的数据，操作 $k$ 次后均仅剩下一个数。