「CROI · R2」在相思树下 I

题目背景

年年桃树下

常看一个变成俩

小小心愿常比划

快快实现吧

却没看到他也在树下

相逢二字纵使隔天涯

转角总会遇上他

缘分缘分啊

题目描述

本题采用多组数据测试。

现在欣欣有一个从

1

到

n

的序列，并想对这个序列进行如下两种操作。

操作一：删去所有的奇数项。

操作二：删去所有的偶数项。

欣欣发现她在进行

k

次操作后，最后只剩下一个数，但她不知道这个数是多少，于是欣欣来找你求助，她会给你她所进行的

k

次操作的种类，希望你告诉她最后的那个数是多少。

输入格式

第一行一个正整数

T

，表示数据组数。

对于每组数据：

第一行两个整数

n

和

k

，含义如题面所示。

第二行

k

个整数，代表欣欣依次进行的操作种类，其中

1

代表操作一，

2

代表操作二。

输出格式

共

T

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

样例 #1

样例输入 #1

CPP

样例输出 #1

CPP

提示

【样例解释】

对于第一组数据，序列的变化如下：

\{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

次后均仅剩下一个数。 6666666666666666666666666666666666666666

666

讨论操作