Mirko and Slavko have played the game Risk a thousand times, so they are now trying to invent a new game called Aggressor, which is played on the same board in the form of a geographical map. The board contains $N$ countries labeled with numbers from $1$ to $N$, and it is known which pairs of countries are neighbors. Some countries may be neighbors even if they do not physically share a border.

Before the game starts, they place a certain number of tanks in each country and declare some countries as "aggressors," while the remaining ones are "peaceful." Once they have done this, Mirko and Slavko will take turns making one move each. The player who cannot make a move loses the game. Mirko goes first.

Each time a player is on turn, they choose one of two types of moves:

1. Attack:

   • The player first chooses an aggressor country $A$ with $T_A$ tanks, and a neighboring peaceful country $M$ with $T_M$ tanks.
   • For the move to be allowed, it must hold that $T_M > 0$.
   • Then, each tank from country $A$ destroys one tank from country $M$ with a projectile.
   • At the end of the move, country $M$ will have $T_M - T_A$ tanks remaining, or $0$ if $T_A > T_M$.

2. Help:

   • The player chooses two neighboring peaceful countries $M$ and $O$, with $T_M$ and $T_O$ tanks respectively.
   • For the move to be allowed, it must hold that $T_M > 0$.
   • If $T_M$ is odd, the player first adds a new tank to country $M$.
   • Then, exactly half of the tanks from country $M$ are moved to country $O$.

Note: Countries do not belong to individual players, i.e., each player can choose any two neighboring countries in their turn, provided the move is allowed.

Since the board contains $N$ countries, there are $2^N$ ways to distribute the countries into aggressors and peaceful ones. For every possible distribution, Mirko and Slavko will play one game. They are interested in how many of these $2^N$ games Mirko will win, and how many Slavko will win, assuming both play optimally.

For some distributions, neither player can guarantee a win. For example, if no country is an aggressor, it is not possible to destroy any tanks, so the game cannot end.

Input

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

The second line contains $N$ natural numbers less than $40000$, representing the number of tanks in the countries at the start of the game, in order from country $1$ to country $N$.

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

Each of the following $M$ lines contains two natural numbers representing a pair of neighboring countries. No pair of countries will appear more than once in this list.

Output

The first line should contain the total number of games in which Mirko wins.

The second line should contain the total number of games in which Slavko wins.

Examples

Input 1

2
100 100
1
1 2

Output 1

2
1

Input 2

5
7 5 3 4 5
5
1 2
2 3
3 1
3 4
3 5

Output 2

5
8

Note

Explanation of the first test case: There are four games, of which Mirko wins two and Slavko wins one:

1. Country 1 and country 2 are aggressors - Mirko cannot make a move, so Slavko wins.
2. Country 1 is an aggressor and country 2 is peaceful - Mirko can destroy all tanks in country 2 in one move, after which Slavko cannot make a move, so Mirko wins.
3. Country 1 is peaceful and country 2 is an aggressor - Mirko wins in the same way.
4. Country 1 and country 2 are peaceful - The number of tanks cannot be reduced in a help move, and since no country is an aggressor, it will always be possible to make a help move regardless of how the players play, so the game has no winner in this case.