Alice 和 Bob 正在玩一个游戏。最初，桌子上的直线上放置了 $n$ 颗石头。Alice 和 Bob 轮流进行操作。在每一轮中，玩家选择并移除其中一颗石头。游戏持续进行，直到直线上的石头数量变为两颗。这两颗石头被称为结果石头。Alice 的目标是使结果石头之间的距离尽可能大，而 Bob 的目标是使它们尽可能近。

给定石头的坐标以及先手的名字。假设 Alice 和 Bob 都采取最优策略，计算并输出游戏结束时结果石头之间的距离。

输入格式

输入包含单个测试用例，格式如下：

$n \ f$ $x_1 \ x_2 \ \dots \ x_n$

$n$ 是石头的数量 ($3 \le n \le 10^5$)。$f$ 是先手玩家的名字，为 Alice 或 Bob。对于每个 $i$，$x_i$ 是一个整数，表示第 $i$ 颗石头距离桌子边缘的距离。保证 $0 \le x_1 < x_2 < \dots < x_n \le 10^9$。

输出格式

输出一行，表示结果石头之间的距离。

样例

样例输入 1

5 Alice
10 20 30 40 50

样例输出 1

30

样例输入 2

5 Bob
2 3 5 7 11

样例输出 2

2