Problem Background

The gently falling maple leaves are like thoughts. Why do I have to save them before winter comes? Loving you through time, two lines of tears from late autumn. Let love seep into the ground. All I want is you by my side. ——"Maple"

Problem Description

Dong loves maple leaves very much. There is a maple tree in front of her house, and it has shed $n$ leaves. Dong numbers them from $1$ to $n$. She hopes these maple leaves won't be crushed and rot on the ground, so she decides to pick them up. She calls the process of picking up the remaining unpicked leaves in ascending or descending order of their numbers, starting with the first leaf and then picking every $k$-th leaf, a salvage. She will continue to perform salvages, alternating the order each time (i.e., ascending first, then descending, and so on), until the last leaf is picked up. She believes that the last picked leaf represents thoughts, which can bring happiness. She hopes to gain more happiness, so she will ask you many times for the number of the thoughts when $n$ and $k$ take certain values.

Input Format

The first line is the number of data sets $t$, where $t=i$ and $i$ is the data point number.

From the second to the $t+1$-th line, each line starts with two numbers $q$ and $m$, indicating that she will ask $q$ times, with each time's number of leaves $n$ not exceeding $m$. Then $q$ numbers follow, representing each time's number of leaves $n$. For all queries in the $x$-th line, $k=x-1$.

Output Format

For each line, output $q$ numbers, representing the answers to each query.

Sample Input and Output

Input Sample #1

1
2 3 1 3

Output Sample #1

1 2

Input Sample #2

2
2 3 1 3
3 7 2 4 7

Output Sample #2

1 2
2 2 5

Input Sample #3

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

Output Sample #3

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

Notes

Simplified Problem Statement:

Given $n$ and $k$, for the sequence $1, 2, \dots, n$, keep performing operations where each operation alternates between picking the $(k+1)x+1$-th number in ascending or descending order (where $x \in \mathbb{Z_{\ge 0}}$ and $(k+1)x+1$ does not exceed the total number of remaining numbers), and find the number of the last picked leaf. Multiple queries are given.

Sample Explanation:

Due to space limitations, only the explanation for Sample 2 is provided.

For the second line:

For the first query, there is only one leaf on the ground, which is the thoughts.

For the second query, Dong first salvages by picking up leaves $1$ and $3$, then turns around and only leaf $2$ remains, which is the thoughts.

For the third line:

For the first query, Dong first salvages by picking up leaf $1$, then turns around and only leaf $2$ remains, which is the thoughts.

For the second query, Dong first salvages by picking up leaves $1$ and $4$, then salvages again and picks up leaf $3$, leaving only leaf $2$, which is the thoughts.

For the third query, Dong first picks up leaves $1$, $4$, and $7$, then picks up leaves $6$ and $2$, and finally picks up leaf $3$, leaving only leaf $5$, which is the thoughts.

Data Range:

For each data point (except the first one), the input data, excluding the number of data sets $t$ and the last line (the $t+1$-th line), is identical to the input data of the previous data point. The data range and special constraints for each data point are as follows.

The input is large, and you can use the fast input template provided in the contest description to speed up input reading.

见题面 Input 部分

见题面 Output 部分