問題文

$1, 2, \ldots , N$ が書かれたカードが $1$ 枚ずつ左からこの順に一列に並んでいます。ラスク君は次の操作をカードが残り $1$ 枚になるまで繰り返します。

1. 残っているカードのうち、左から $K x + 1$ 番目 ($x$ は非負整数) のカードすべてに印をつける。
2. 印のついたカードをすべて取り除く。

$N$ の値が $N_1, N_2, \ldots, N_Q$ の場合それぞれについて答えを求めてください。

入力

$K\ Q$
$N_1$
$N_2$
$\vdots$
$N_Q$

• $2\leq K\leq 10^4$
• $1\leq Q\leq 10^5$
• $1\leq N_i\leq 10^{18}$
• 入力はすべて整数である。

出力

$Q$ 行出力してください。$i$ 行目 ($1\leq i\leq Q$) には、$N=N_i$ の場合に、操作を繰り返し行ったとき最後に残るカードに書かれた数を出力してください。

サンプル

3 1
7

5

5 3
3
34
334

3
30
290

3141 5
9265358979
3238462643
3832795028
8419716939
9375105820

9263828525
3238177188
3832261774
8417162552
9373616394