問題ヴィジュアル

問題文

$N$ 人の守人 (マモリビト) はある $1$ 本の桜の木の周りにある長さ $L$ の円周の道上にいる. 道上にはただ $1$ つの拠点がある.

$i$ 番目の守人は拠点から円周の道上を反時計回りに $X_i$ だけ進んだ地点を立ち位置としている.

それぞれの守人はたくましさという非負実数のパラメータを持っている. たくましさが $p$ であるとき, 立ち位置から距離 $p$ 以下だけ円周の道上を辿って到達できる点 (端点を含む) を守ることができる.

以下が成り立つ時, そしてその時に限り「桜は完璧に守られている」という.

• 円周の道上の任意の点において, その点を守ることが可能な守人が $K$ 人以上いる.

次の条件を満たすような $P$ の最小値を $\widetilde{P}$ とする.

• $N$ 人の守人全員のたくましさを $P$ としたとき, 桜は完璧に守られている.

では, $\widetilde{P}$ の切り上げ $\left \lceil \widetilde{P} \right \rceil$ を求めよ.

$T$ 個のテストケースに答えよ.

制約

• $1 \leq T \leq 10^4$.
• 各テストケースに対する制約.
  • $1 \leq N \leq 2 \times 10^4$.
  • $1 \leq L \leq 10^9$.
  • $1 \leq K \leq N$.
  • $0 \leq X_i < L \quad (1 \leq i \leq N)$.
• テストファイルに対する制約
  • $T$ 個のテストケースにおける $N$ の総和は $2 \times 10^4$ 以下である.
• 入力は全て整数である.

入力

$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$

$N$ $L$ $K$
$X_1$ $X_2$ $\dots$ $X_N$

出力

出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には第 $t$ テストケースに対する解答を整数で出力せよ.

サンプル

3
3 11 2
0 2 5
10 400 5
0 0 139 100 200 74 384 100 248 41
1 46 1
0

5
150
23

1
11 2023 7
113 109 725 707 412 217 1108 509 818 215 122

958