Тавас живет в Канзасе. Канзас состоит из n городов, пронумерованных от 1 до n, соединенных m двусторонними дорогами. Из любого города можно добраться в любой другой город по этим дорогам. Канзас не менее странный, чем Тавас, поэтому дорога может соединять город с самим собой, а также несколько дорог могут соединять одну и ту же пару городов.

Тавас изобрел игру и назвал её "Дашти". Он хочет играть в Дашти со своей девушкой Нафас.

В этой игре к каждому городу в Канзасе сопоставляется произвольное целочисленное значение. Значение i-го города устанавливается равным p_i.

В процессе игры Тавас находится в городе s, а Нафас — в городе t. Они совершают ходы по очереди и Тавас ходит первым. Во время хода игрок должен выбрать неотрицательное целое число x и тогда его или её счет увеличивается на сумму значений всех городов, находящихся на расстоянии не более x до его/её города. Каждый город может быть использован только один раз, иными словами, после первого использования значение города обнуляется.

Есть дополнительное правило: игрок на каждом ходу обязан выбрать такой x, что как минимум один из городов на расстоянии x не был использован до этого. Город может исходно иметь значение ноль, такой город исходно не считается использованным, таким образом, такой город может быть использован на очередном ходу для исполнения дополнительного правила.

Игра заканчивается, когда никто не може сделать ход.

Счет игрока — это сумма баллов, заработанных им в процесса игры. Побеждает игрок с большим счетом, а если у игроков одинаковые значения счета, то объявляется ничья. Оба игрока начинают игру с нулем баллов.

Если победит Тавас, то он разобьет этим сердце своей девушки. А если победит Нафас, то Тавас заплачет. Но если у них образуется одинаковый счет, от оба игрока останутся довольны, а Тавас подарит Нафас цветы.

В конце концов, результат игры волнует Тавас и Нафас сильнее, чем их дальнейшие взаимоотношения, поэтому они будут играть оптимально. Ваша задача — сказать Тавасу, что произойдет, когда завершится игра.