Minimum Permutation

問題文

正整数 $N,X,Y,K$ が与えられます。

$(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ であって $|P_X-P_Y|\le K$ を満たすもののうち、辞書順最小となるものを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le X<Y\le N$
• $1\le K<N$
• 全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

出力

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースにおける答えとなる $P$ の各要素を順に空白区切りで出力せよ。

サンプル 1

入力

3
5 1 5 2
2 1 2 1
7 2 6 2

出力

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

$1$ 番目のテストケースについて考えます。

$P=(1,2,4,5,3)$ は $|P_1-P_5|=2\le 2$ を満たし、これが辞書順最小です。