최대 최소 거리 게임

앨리스와 밥이 다음 게임을 한다. 처음에 탁자 위 직선 하나에 돌 n개가 놓여 있다. 두 사람은 번갈아 차례를 진행하고, 자기 차례에는 남아 있는 돌 중 하나를 골라 없앤다. 직선 위의 돌이 두 개가 되면 게임이 끝나며, 남은 두 돌을 결과 돌이라고 한다. 앨리스는 결과 돌 사이의 거리를 최대한 멀게 만들려 하고, 밥은 최대한 가깝게 만들려 한다.

돌의 좌표와 첫 차례를 맡는 사람의 이름이 주어진다. 두 사람이 모두 최선을 다한다고 할 때, 게임이 끝난 뒤 결과 돌 사이의 거리를 구하라.

입력은 테스트 케이스 하나로 이루어지고 형식은 다음과 같다.

n f
x1 x2 ... xn

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$이 성립한다.

결과 돌 사이의 거리를 한 줄에 출력한다.