L - LIS Triangle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N,K,L が与えられます。次の条件を全て満たす長さ N の整数列 P が存在するか判定し、存在する場合は 1 つ示してください。

  • P は整数列 (K, K + 1, \dots, K + N - 1) の順列
  • P の最長増加部分列の長さは L
  • 1 \leq i \leq N - 2 を満たす i に対して、P_i, P_{i+1}, P_{i+2} を 3 辺の長さとする（非退化な）三角形が存在する

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

最長増加部分列とは 数列 P の部分列とは、P の要素をいくつか抜き出して元の順に並べてできる列のことを指します。 数列 P の最長増加部分列とは、P の狭義単調増加な部分列であって、長さが最大のものを指します。
非退化な三角形とは 非退化な三角形とは、3 つの頂点が同一直線上に並ばないような三角形のことを指します。

制約

  • 入力は全て整数
  • 1 \leq T \leq 50000
  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq L \leq N
  • 1 つの入力に含まれるテストケースについて、N の総和は 2 \times 10^5 以下

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N K L

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

あるテストケースについて、条件を全て満たす P が存在しない場合は No を出力せよ。存在する場合は、条件を全て満たす整数列 P のうち 1 つを、以下の形式で出力せよ。条件を全て満たす整数列 P が複数存在する場合は、いずれを出力しても正解となる。

Yes
P_1 P_2 \dots P_N

入力例 1

3
6 3 4
5 5 5
7 1 2

出力例 1

Yes
3 6 4 7 5 8
Yes
5 6 7 8 9
No

1 つ目のテストケースについて、条件を満たす整数列の 1 つに、P=(3, 6, 4, 7, 5, 8) があります。条件を満たす整数列は他にも存在します。

2 つ目のテストケースについて、P=(5, 6, 7, 8, 9) が条件を満たす唯一の整数列です。

3 つ目のテストケースについて、条件を満たす整数列 P は存在しません。