P7485 「Stoi2031」枫

> 缓缓飘落的枫叶像思念 为何挽回要赶在冬天来之前 爱你穿越时间 两行来自秋末的眼泪 让爱渗透了地面 我要的只是你在我身边 ——《枫》

冬很喜欢枫叶。她家门前有一棵枫树，树上落下了 $n$ 片叶子。冬将它们编号为 $1$ 到 $n$。她希望这些枫叶不要这样被人踩碎后烂在地里，所以决定把它们捡起来。她称将剩余未捡起来的枫叶按编号从小到大或从大到小的顺序排序后，先捡起第一片枫叶，然后每隔 $k$ 片捡起一片称为一次 **挽回**。她会一直进行 **挽回**，第一次 **挽回** 从小到大，之后每次 **挽回** 的顺序都和上次不同（即上次从小到大这次就从大到小，反之亦然），直到最后一片枫叶也被捡起。她认为最后一片捡起的枫叶代表了 **思念**，能带来幸福。她希望获得更多的幸福，所以她会很多次地问你 $n$ 和 $k$ 取某两个值时她得到的 **思念** 的编号。

第一行为数据组数 $t$，满足 $t=i$，$i$ 为数据点编号。 第 $2$ 到 $t+1$ 行，每行开头两个数 $q,m$，表示她要取 $q$ 次，每次的枫叶数 $n$ 不超过 $m$。接着输入 $q$ 个数表示每次的枫叶数 $n$。第 $x$ 行的所有询问中 $k=x-1$。

对于每行输出 $q$ 个数，表示每次询问的答案。

#### 简述版题意： 给定 $n,k$，对 $1,2,\dots,n$ 一直操作，每次操作交替从小到大或从大到小的顺序取走当前的第 $(k+1)x+1$ 个数（$x \in \mathbb{Z_{\ge 0}}$ 且 $(k+1)x+1$ 不超过剩余数总数），求最后一个取走的数的编号。多次询问。 #### 样例解释： 限于篇幅，只对样例 $2$ 作解释。 对于第 $2$ 行： 对于第一次询问，地上只有 $1$ 片枫叶，此即 **思念**。 对于第二次询问，冬第一次 **挽回** 时依次捡起了 $1,3$ 两片枫叶，转身后只剩下 $2$，即 **思念**。 对于第 $3$ 行： 对于第一次询问，冬第一次 **挽回** 时捡起了 $1$ 号枫叶，转身后剩下 $2$，即 **思念**。 对于第二次询问，冬第一次 **挽回** 时捡起了 $1,4$ 两片枫叶，第二次 **挽回** 捡起了 $3$，剩下 $2$，即 **思念**。 对于第三次询问，冬第一次捡起了 $1,4,7$，第二次捡起了 $6,2$，第三次捡起了 $3$，此时剩下 $5$，即 **思念**。 #### 数据范围： **本题每个数据点（除第 $1$ 个外）输入数据除数据组数 $t$ 以及最后一行（第 $t+1$ 行）外与前一个数据点输入数据完全相同。各个数据点的数据范围及特殊限制如下。** | Testdata No. | $q \le$ | $m \le$ | 特殊限制 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $2$ | $3$ | 为样例 $1$ | $3$ | | $2$ | $3$ | $7$ | 为样例 $2$ | $7$ | | $3$ | $7$ | $10$ | 为样例 $3$ | $3$ | | $4$ | $10$ | $30$ | 无 | $3$ | | $5$ | $30$ | $70$ | 无 | $7$ | | $6$ | $70$ | $100$ | 无 | $7$ | | $7$ | $100$ | $300$ | 无 | $7$ | | $8$ | $300$ | $700$ | 无 | $10$ | | $9$ | $700$ | $10^3$ | 无 | $3$ | | $10$ | $10^3$ | $3 \times 10^3$ | 无 | $3$ | | $11$ | $3 \times 10^3$ | $7 \times 10^3$ | 无 | $1$ | | $12$ | $7 \times 10^3$ | $10^4$ | 无 | $13$ | | $13$ | $10^4$ | $3 \times 10^4$ | 无 | $3$ | | $14$ | $3 \times 10^4$ | $7 \times 10^4$ | 无 | $3$ | | $15$ | $7 \times 10^4$ | $10^5$ | 无 | $10$ | | $16$ | $10^5$ | $3 \times 10^5$ | 无 | $13$ | | $17$ | $3 \times 10^5$ | $7 \times 10^5$ | 无 | $1$ | | $18$ | $7 \times 10^5$ | $10^6$ | 无 | $3$ | **本题读入量较大，可以选择使用比赛描述中的快速读入模板以加快读入速度。**