Tavas lives in Kansas. Kansas has n cities numbered from 1 to n connected with m bidirectional roads. We can travel from any city to any other city via these roads. Kansas is as strange as Tavas. So there may be a road between a city and itself or more than one road between two cities.

Tavas invented a game and called it "Dashti". He wants to play Dashti with his girlfriends, Nafas.

In this game, they assign an arbitrary integer value to each city of Kansas. The value of i-th city equals to p_i.

During the game, Tavas is in city s and Nafas is in city t. They play in turn and Tavas goes first. A player in his/her turn, must choose a non-negative integer x and his/her score increases by the sum of values of all cities with (shortest) distance no more than x from his/her city. Each city may be used once, or in the other words, after first time a player gets score from a city, city score becomes zero.

There is an additional rule: the player must choose x such that he/she gets the point of at least one city that was not used before. Note that city may initially have value 0, such city isn't considered as been used at the beginning of the game, i. e. each player may use it to fullfill this rule.

The game ends when nobody can make a move.

A player's score is the sum of the points he/she earned during the game. The winner is the player with greater score, or there is a draw if players score the same value. Both players start game with zero points.

If Tavas wins, he'll break his girlfriend's heart, and if Nafas wins, Tavas will cry. But if their scores are equal, they'll be happy and Tavas will give Nafas flowers.

They're not too emotional after all, so they'll play optimally. Your task is to tell Tavas what's going to happen after the game ends.