「CROI · R2」在相思树下 I

题目背景

年年桃树下

常看一个变成俩

小小心愿常比划

快快实现吧

却没看到他也在树下

相逢二字纵使隔天涯

转角总会遇上他

缘分缘分啊

题目描述

本题采用多组数据测试。

现在欣欣有一个从 $1$ 到 $n$ 的序列，并想对这个序列进行如下两种操作。

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

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

欣欣发现她在进行 $k$ 次操作后，最后只剩下一个数，但她不知道这个数是多少，于是欣欣来找你求助，她会给你她所进行的 $k$ 次操作的种类，希望你告诉她最后的那个数是多少。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n$ 和 $k$，含义如题面所示。

第二行 $k$ 个整数，代表欣欣依次进行的操作种类，其中 $1$ 代表操作一，$2$ 代表操作二。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #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$ 次后均仅剩下一个数。 6666666666666666666666666666666666666666