Mirko 和 Slavko 已经玩过一千次《风险》(Rizik) 游戏了，现在他们试图发明一种名为《侵略者》(Agresor) 的新游戏，该游戏在同一张地理地图形状的棋盘上进行。棋盘包含 $N$ 个国家，编号从 $1$ 到 $N$，并且已知哪些国家对是邻居。即使在物理上不共享边界，某些国家也可能是邻居。
在游戏开始前，他们在每个国家放置了特定数量的坦克，并将一些国家宣布为“侵略者”，其余国家为“和平”国家。完成这些设置后，Mirko 和 Slavko 将轮流进行操作。无法进行操作的玩家输掉游戏。Mirko 先手。
每当轮到一名玩家时，他可以选择以下两种操作之一：
攻击：
- 玩家首先选择一个拥有 $T_A$ 个坦克的侵略者国家 $A$，以及一个与之相邻的拥有 $T_M$ 个坦克的和平国家 $M$。
- 为了使操作合法，必须满足 $T_M > 0$。
- 然后，来自国家 $A$ 的每个坦克用导弹摧毁国家 $M$ 中的一个坦克。
- 操作结束时，国家 $M$ 中将剩下 $T_M - T_A$ 个坦克，如果 $T_A > T_M$，则剩下 $0$ 个。
援助：
- 玩家选择两个相邻的和平国家 $M$ 和 $O$，它们分别拥有 $T_M$ 和 $T_O$ 个坦克。
- 为了使操作合法，必须满足 $T_M > 0$。
- 如果 $T_M$ 是奇数，玩家首先在国家 $M$ 中增加一个新坦克。
- 然后，将国家 $M$ 中恰好一半的坦克转移到国家 $O$。
注意：国家不属于特定玩家，即每名玩家在自己的回合中可以选择任何两个相邻的国家，只要操作合法即可。
由于棋盘包含 $N$ 个国家，有 $2^N$ 种将国家划分为侵略者和和平国家的方式。对于每种可能的划分，Mirko 和 Slavko 将进行一局游戏。他们想知道在双方都采取最优策略的情况下，在这 $2^N$ 局游戏中，Mirko 会赢多少局，Slavko 会赢多少局。
对于某些划分，没有任何玩家能确保获胜。例如，如果没有任何国家是侵略者，那么就不可能摧毁任何坦克，游戏也就无法结束。
输入格式
第一行包含一个整数 $N$ ($2 \le N \le 40$)，表示国家的数量。 第二行包含 $N$ 个小于 $40000$ 的自然数，表示游戏开始时每个国家中的坦克数量，按编号从 $1$ 到 $N$ 的顺序排列。 第三行包含一个整数 $M$ ($1 \le M \le 780$)，表示相邻国家对的数量。 接下来的 $M$ 行中，每行包含两个自然数，表示一对相邻的国家。列表中不会出现重复的对。
输出格式
第一行输出 Mirko 获胜的总局数。 第二行输出 Slavko 获胜的总局数。
样例
输入 1
2 100 100 1 1 2
输出 1
2 1
输入 2
5 7 5 3 4 5 5 1 2 2 3 3 1 3 4 3 5
输出 2
5 8
说明
第一个测试样例的解释： 共有四局游戏，其中 Mirko 赢两局，Slavko 赢一局： 1. 国家 1 和国家 2 都是侵略者 - Mirko 无法进行操作，Slavko 获胜。 2. 国家 1 是侵略者，国家 2 是和平国家 - Mirko 可以一次性摧毁国家 2 中的所有坦克，之后 Slavko 无法进行操作，Mirko 获胜。 3. 国家 1 是和平国家，国家 2 是侵略者 - Mirko 以同样的方式获胜。 4. 国家 1 和国家 2 都是和平国家 - 援助操作中坦克数量不会减少，因此由于没有国家是侵略者，无论玩家如何操作，总能进行援助操作，在这种情况下游戏没有赢家。