CFCF2207B.One Night At Freddy's

Five Nights at Freddy's 1 Song — The Living Tombstone 设 $ n, m, \ell $ 为正整数。你做了一个不幸的决定，要在弗雷迪·法兹熊披萨店当夜间保安，这里有 $ m $ 个机械玩偶，编号为 $ 1, \ldots, m $，等着吓你一跳。

夜晚持续 $ \ell $ 秒，编号为 $ 1, \ldots, \ell $。第 $ j $ 个机械玩偶有一个危险等级 $ d_j $，初始时 $ d_1 = \ldots = d_m = 0 $。每一秒，恰好有一个机械玩偶的危险等级会增加 $ 1 $，在整个夜晚期间，你可以随时观察到所有 $ d_j $ 的值。例如，如果 $ m = 2 $，5 秒后危险等级的一种可能情况是 $ [d_1, d_2] = [2, 3] $。

不过，你并非毫无防备。在 $ n $ 个固定的时间点 $ a_i $ ( $ 1 \leq a_1 < \ldots < a_n \leq \ell $ )，你可以将手电筒照向恰好一个你选择的机械玩偶 $ j_i $。这发生在第 $ a_i $ 秒结束后，并会将其危险等级重置为零，即 $ d_{j_i} := 0 $。注意，每次使用手电筒 $ a_i $ 时，这个选择是独立做出的。接之前的例子，如果 $ a_1 = 5 $ 并且你选择在此时照向第二个机械玩偶，那么 5 秒后的危险等级将是 $ [d_1, d_2] = [2, 0] $。

设总体危险度为所有机械玩偶中危险等级的最大值，即 $ \max_{1 \leq j \leq m} d_j $。如果夜晚结束时（$ \ell $ 秒后）的总体危险度大于 $ x $，你就会输。找出最小的 $ x $ 值，使得无论机械玩偶如何行动，你都能保证最终总体危险度小于或等于 $ x $。

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $ ( $ 1 \le t \le 10^4 $ )。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $ n $、$ m $ 和 $ \ell $ ( $ 1 \leq n, m, \ell \leq 2 \cdot 10^5 $, $ n \leq \ell $, $ 1 \leq m \cdot \ell \leq 2 \cdot 10^5 $ ) — 分别是手电筒使用次数、机械玩偶数量和夜晚时长。

下一行包含 $ n $ 个整数 $ a_i $ ( $ 1 \leq a_1 < \ldots < a_n \leq \ell $ ) — 你可以使用手电筒的时间点。

保证所有测试用例的 $ m \cdot \ell $ 之和不超过 $ 2 \cdot 10^5 $。

对于每个测试用例，输出一个整数 — 保证最终危险度不超过 $ x $ 的最小 $ x $ 值。

在第一个测试用例中，有 $2$ 个机械玩偶，夜晚长度为 $10$ 秒，你可以在第 $10$ 秒结束后使用手电筒。我们将证明 $ x = 5 $ 总是可行的。$10$ 秒后，注意到一个机械玩偶的危险等级至少为 $5$，另一个最多为 $5$。因此，我们可以照向危险等级较高的那个，最终危险度最多为 $5$。可以证明 $ 5 $ 是 $ x $ 的最小可能值。

在第二个测试用例中，只有一个机械玩偶，夜晚长度为 $32$ 秒。注意在这种情况下，机械玩偶每秒危险等级增加 $1$。因此，在第 $25$ 秒结束后，我们将其危险等级重置为 $0$。夜晚结束前又过去了 $7$ 秒，所以我们得到的最终危险度始终是 $7$。

在第三个测试用例中，可以证明 $ x $ 的最小可能值是 $19$。
由 DeepSeek 完成翻译，人工为 Hint 的数字添加 Katex。