P7485 "Stoi2031" Maple.

> The maple leaves fall slowly like longing. Why must making up happen before winter comes. Loving you across time, two lines of tears from late autumn, letting love soak into the ground. All I want is you by my side. — "Maple"

Dong really likes maple leaves. There is a maple tree in front of her house, and $n$ leaves have fallen from it. Dong numbers them from $1$ to $n$. She does not want these maple leaves to be stepped on and rot on the ground, so she decides to pick them up. She calls the following process a **retrieval**: sort the remaining unpicked maple leaves by their numbers in increasing order or decreasing order, pick up the first leaf, then pick up one leaf every $k$ leaves. She will keep performing **retrieval**. The first **retrieval** is from small to large; after that, each **retrieval** uses the opposite order of the previous one (i.e., if last time was from small to large, this time is from large to small, and vice versa), until the last leaf is also picked up. She believes the last leaf picked up represents **longing**, which can bring happiness. She wants more happiness, so she will ask you many times: for given values of $n$ and $k$, what is the number of the **longing** leaf.

The first line contains the number of test groups $t$, satisfying $t=i$, where $i$ is the testdata point ID. Lines $2$ to $t+1$: each line starts with two integers $q,m$, meaning she will take $q$ queries, and in each query the number of leaves $n$ does not exceed $m$. Then $q$ integers follow, each being the value of $n$ for one query. For all queries on line $x$, $k=x-1$.

For each line, output $q$ integers, representing the answers to the queries on that line.

#### Brief statement: Given $n,k$, repeatedly operate on $1,2,\dots,n$. In each operation, alternately take numbers in increasing order or decreasing order, and remove the current $(k+1)x+1$-th number (where $x \in \mathbb{Z_{\ge 0}}$ and $(k+1)x+1$ does not exceed the total count of remaining numbers). Find the number removed last. There are multiple queries. #### Sample explanation: Due to space limits, only sample $2$ is explained. For line $2$: For the first query, there is only $1$ maple leaf on the ground, which is the **longing**. For the second query, in Dong's first **retrieval**, she picks up leaves $1,3$ in order; after turning around, only $2$ remains, which is the **longing**. For line $3$: For the first query, in Dong's first **retrieval**, she picks up leaf $1$; after turning around, $2$ remains, which is the **longing**. For the second query, in Dong's first **retrieval**, she picks up leaves $1,4$; in the second **retrieval**, she picks up $3$; $2$ remains, which is the **longing**. For the third query, Dong first picks up $1,4,7$, then picks up $6,2$, then picks up $3$; now $5$ remains, which is the **longing**. #### Constraints: **For each testdata point of this problem (except the $1$st), the input data is exactly the same as the previous testdata point, except for the number of test groups $t$ and the last line (line $t+1$). The constraints and special limits of each testdata point are as follows.** | Testdata No. | $q \le$ | $m \le$ | Special limit | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $2$ | $3$ | Sample $1$ | $3$ | | $2$ | $3$ | $7$ | Sample $2$ | $7$ | | $3$ | $7$ | $10$ | Sample $3$ | $3$ | | $4$ | $10$ | $30$ | None | $3$ | | $5$ | $30$ | $70$ | None | $7$ | | $6$ | $70$ | $100$ | None | $7$ | | $7$ | $100$ | $300$ | None | $7$ | | $8$ | $300$ | $700$ | None | $10$ | | $9$ | $700$ | $10^3$ | None | $3$ | | $10$ | $10^3$ | $3 \times 10^3$ | None | $3$ | | $11$ | $3 \times 10^3$ | $7 \times 10^3$ | None | $1$ | | $12$ | $7 \times 10^3$ | $10^4$ | None | $13$ | | $13$ | $10^4$ | $3 \times 10^4$ | None | $3$ | | $14$ | $3 \times 10^4$ | $7 \times 10^4$ | None | $3$ | | $15$ | $7 \times 10^4$ | $10^5$ | None | $10$ | | $16$ | $10^5$ | $3 \times 10^5$ | None | $13$ | | $17$ | $3 \times 10^5$ | $7 \times 10^5$ | None | $1$ | | $18$ | $7 \times 10^5$ | $10^6$ | None | $3$ | **The input size of this problem is large. You may choose to use the fast input template provided in the contest statement to speed up reading.** Translated by ChatGPT 5