Net Profit 

Thomas has just designed a new game called "Net Profit". The game is played by two players on a "net" of business ventures, each of which offers a certain amount of profit (or loss) in dollars. The term "net" refers to the fact that ventures are connected to each other by randomly generated links (chosen in such a way that all the ventures are connected).

\epsfbox{p11932.eps}

The first player may pick any venture to start, and he scores the associated profit or loss. This venture is now referred to as exhausted. Afterward, the players take turns exhausting ventures and collecting profits, following two simple rules:

  1. An exhausted venture may not be selected again (by either player)
  2. Only ventures connected to an already exhausted venture are eligible for exhaustion

The game ends once all the ventures are exhausted, and the winner is the player with the greatest profit (or smallest loss). With a given "net" of ventures and associated profits, Thomas would like to know the final outcome of the game assuming optimal play from both players.

Input 

Input consists of several test cases. Each test case begins with an integer N ( 1$ \le$N$ \le$16), representing the number of ventures in the net. This is followed by a line containing N integers p1, p2,..., pN; where pk is the profit associated with venture k ( | pk|$ \le$1000).

Next is a line containing a non-negative integer M, followed by M lines, each describing a link in the net. Each link description consists of two integers a and b ( 1$ \le$a, b$ \le$N, a$ \ne$ b), which means that ventures a and b are linked.

You may assume that the described net connects all the ventures in one component, and that a given link is described at most once (so if link a b is given, link b a will not be).

The input is terminated by a line containing `0' which should not be processed.

Output 

For each test case, output a line with the final result and score of the game assuming optimal play by both players (see the sample output for details).

Sample Input  

2
25 -20
1
1 2
3
15 15 -5
2
1 2
2 3
2
30 30
1
1 2
0

Sample Output  

First player wins! 25 to -20.
Second player wins! 15 to 10.
Tie game! 30 all.