Aggressor

Mirko and Slavko have played Risk a thousand times, so they are inventing a new game called Aggressor that uses the same board, a map. The board has $N$ countries numbered 1 to $N$, and it is known which pairs of countries are neighbors. Two countries can be neighbors even when they do not share a physical border.

Before the game starts, the two players put a number of tanks in every country and declare some of the countries aggressors. The remaining countries are peaceful. Mirko and Slavko then alternate, one move each. A player who cannot move loses the game. Mirko moves first.

On his turn a player picks one of two kinds of moves.

1. Attack:

   • The player picks an aggressor country $A$ holding $T_A$ tanks and a neighboring peaceful country $P$ holding $T_P$ tanks.
   • The move is allowed only when $T_P > 0$.
   • Every tank in $A$ destroys one tank in $P$ with a missile.
   • After the move $P$ holds $T_P - T_A$ tanks, or 0 tanks when $T_A > T_P$.

2. Help:

   • The player picks two neighboring peaceful countries $P$ and $Q$, holding $T_P$ and $T_Q$ tanks.
   • The move is allowed only when $T_P > 0$.
   • If $T_P$ is odd, the player first adds one new tank to $P$.
   • Then exactly half of the tanks in $P$ move to $Q$.

Countries belong to neither player. On his turn a player may pick any two neighboring countries as long as the move is allowed.

The board has $N$ countries, so there are $2^N$ ways to split them into aggressors and peaceful countries. Mirko and Slavko play one game for each way. Count how many of those $2^N$ games Mirko wins and how many Slavko wins when both play optimally.

For some splits neither player can force a win. If no country is an aggressor, for example, no tank can ever be destroyed, so the game never ends.

The first line contains the integer $N$ ($2 \le N \le 40$), the number of countries.

The second line contains the number of tanks in each country at the start of the game, from country 1 to country $N$. Each of those $N$ numbers is a positive integer smaller than 40000.

The third line contains the integer $M$ ($1 \le M \le 780$), the number of neighboring pairs.

Each of the next $M$ lines contains the numbers of two countries that are neighbors. No pair appears more than once in this list.

In the first line, print the total number of games Mirko wins.

In the second line, print the total number of games Slavko wins.

Take two countries that are neighbors, each holding 100 tanks. Of the four splits, Mirko wins two and Slavko wins one.

1. Both countries are aggressors. Mirko cannot move, so Slavko wins.
2. Country 1 is an aggressor and country 2 is peaceful. Mirko destroys every tank in country 2 in a single move, after which Slavko cannot move, so Mirko wins.
3. Country 1 is peaceful and country 2 is an aggressor. Mirko wins the same way.
4. Both countries are peaceful. A help move never lowers the number of tanks and no country is an aggressor, so a help move is always available no matter how the players move. This split has no winner.