题目描述

一个团队只有当所有成员的能力值都十分接近时，才能被称为一个优秀的团队。

现在你接手了一个团队，团队共有 $n$ 名成员，每个人的能力值都用一个整数 $a_i$ 表示。

现在你必须调整其中 $m$ 个成员的能力值，使其增加 $k$ 或者减少 $k$，即如果调整第 $i$ 名成员的话， $a_i = a_i + k$ 或者 $a_i = a_i - k$。

请问你如何调整这 $m$ 名成员的能力值，使得团队的能力值差距最小?

能力值差距定义为：团队中最大的能力值减去团队中最小的能力值。

输入格式

第一行三个整数 $n, m, k$，分别表示团队成员的数量、需要调整的成员数量和每个成员能力值的调整幅度。

第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每个成员的能力值。

输出格式

输出一个整数，表示调整后团队的能力值差距的最小值。

样例

输入样例1

5 2 3
1 5 4 3 2

输出样例1

2

解释：调整第 $1$ 名成员的能力值为 $1 + 3 = 4$，调整第 $2$ 名成员的能力值为 $5 - 3 = 2$，调整后的能力值为 $4, 2, 4, 3, 2$，最大值为 $4$，最小值为 $2$，差距为 $4 - 2 = 2$。

输入样例2

5 2 3
2 2 2 2 2

输出样例2

3

解释：无论你调整（同时调大/调小）哪 $2$ 名成员的能力值，能力值差距都为 $3$。

数据范围

对于所有的数据有：$1 \le m \le n \le 2 \times 10^5$， $1 \le k \le 10^9$，$1 \le a_i \le 10^9$。

各测试点的说明如下表所示。