Problem K Min-Max Distance Game

Alice and Bob are playing the following game. Initially, $n$ stones are placed in a straight line on a table. Alice and Bob take turns alternately. In each turn, the player picks one of the stones and removes it. The game continues until the number of stones on the straight line becomes two. The two stones are called result stones. Alice's objective is to make the result stones as distant as possible, while Bob's is to make them closer.

You are given the coordinates of the stones and the player's name who takes the first turn. Assuming that both Alice and Bob do their best, compute and output the distance between the result stones at the end of the game.

Input

The input consists of a single test case with the following format.

$n$ $f$
$x_1$ $x_2$ ... $x_n$

$n$ is the number of stones $(3 \leq n \leq 10^5)$. $f$ is the name of the first player, either Alice or Bob. For each $i$, $x_i$ is an integer that represents the distance of the $i$-th stone from the edge of the table. It is guaranteed that $0 \leq x_1 < x_2 < ... < x_n \leq 10^9$ holds.

Output

Output the distance between the result stones in one line.

Sample Input 1

5 Alice
10 20 30 40 50

Sample Output 1

30

Sample Input 2

5 Bob
2 3 5 7 11

Sample Output 2

2

---