Description

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.

Input Format

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$.

Output Format

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

1
2 3 1 3

1 2

2
2 3 1 3
3 7 2 4 7

1 2
2 2 5

3
2 3 1 3
3 7 2 4 7
7 10 1 2 3 6 7 8 10

1 2
2 2 5
1 2 2 3 4 6 6

Hint

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.

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