该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

白糖糕是一种流行于南昌民间的传统糕类小吃，起源于明清时期，被誉为``江西五大传统名点''。其特点香糯、柔软、洁白，造型上与一般白糖糕比独具一格，风味独特，深受大家喜爱。Orange_Ice 作为南昌人，从小就很喜欢吃白糖糕。这道菜也是亲朋好友聚会时，饭桌上必不可少的一道甜品。

在 Orange_Ice 的印象中，白糖糕外观是雪白的。然而每次和奶奶提起白糖糕时，作为老南昌人的她总会感慨：``现在的白糖糕都是雪白雪白的，我们那时候吃的白糖糕都是带一些淡黄色的，那个才正宗！''

这话激起了 Orange_Ice 的兴致，他决定前往南昌老城区------万寿宫、大士院一带，寻找老一辈人吃的正宗白糖糕。

在老城区，Orange_Ice 发现了 $n$ 家售卖白糖糕的店铺。由于每家店的工艺略有不同，糕点的颜色是深浅不一的。而他无法确定奶奶所说的淡黄色''究竟长什么样子。为了尽可能找到最正宗的白糖糕，他将第 $i$ 家白糖糕所带黄色的程度用一个非负整数 $a_i$ 表示，称为色泽''，其中 $a_i\in[0,k]$，数值越小表示糕点越白，数值越大则表示越黄。

由于预算有限，他最多只能购买 $m$ 家店铺的白糖糕。为了保证无论奶奶心中的那个``标准色'' $x$ 是多少，他都能拿出一块色泽最接近于 $x$ 的糕点，他决定这样规划：他要挑选不超过 $m$ 家店铺购买，使得最坏情况下（即对于所有可能的 $x$），手中的糕点色泽最接近于 $x$ 的值，与 $x$ 的差距尽可能小。注意：$x\in[0,k]$，且为整数。

形式化地说，设选定的店铺集合为 $S$，定义对于任意目标色泽 $x$ 的偏差为 $f(x,S)=\min_{s\in S}|x-s|$。目标是求出最小的最坏偏差 $ans$：

请你帮 Orange_Ice 计算，这个``最坏情况下的最小偏差''是多少？

Format

Input

第一行包含三个整数 $n,m,k$，分别代表店铺数量、最多能购买的店铺数量和``色泽''的上限值。

第二行包含 $n$ 个整数，表示第 $i$ 家店铺的白糖糕的色泽值为 $a_i$。

对于全部数据，满足 $1\le m\le n\le 5\times 10^5$, $0\le a_i\le k\le 10^{12}$。

来自 Orange_Ice 的提示：本题读入量较大，建议选用较快的读入方式，尤其是非 C/C++ 语言。

Output

仅一行一个整数，表示最坏情况下的最小偏差，具体含义见题面描述。

Samples

5 3 20
18 2 8 3 15

5

5 2 20
2 2 11 5 9

9