Alice 和 Bob 正在进行一场游戏，Claire 正在帮助他们。游戏中有 $n$ 块石头，编号从 $1$ 到 $n$。游戏由三个阶段组成。

在第一阶段，Alice 和 Bob 交替进行操作，Alice 先手。在每次操作中，玩家声明他们打算拿走一块石头，但他们不说具体是哪一块，而是给出两个选项。这两个选项可以是相同的。玩家也可以说出之前操作中已经提到过的石头。在第一阶段中，石头并不会被真正拿走——玩家只是声明他们对第二阶段的意图。当进行了 $n+1$ 次声明后，第一阶段结束。

以下是 $n=3$ 时第一阶段的一个示例：

1. Alice：“我将拿走石头 1 或石头 3”
2. Bob：“我将拿走石头 2 或石头 2”
3. Alice：“我将拿走石头 3 或石头 2”
4. Bob：“我将拿走石头 1 或石头 3”

在第二阶段，对于已经做出的 $n+1$ 次声明中的每一次，Claire 通过说“第一个”或“第二个”来从两个选项中选择一个。我们将 Claire 做出的每一组选择序列称为一个“场景”。注意，总共有 $2^{n+1}$ 种可能的场景。（即使在某个声明中，第一个选项和第二个选项相同，我们也认为选择“第一个”或“第二个”选项会导致不同的场景。）

以下是上述示例中 Claire 可以选择的 16 种场景之一：

1. “第一个”：Alice 将拿走石头 1
2. “第一个”：Bob 将拿走石头 2
3. “第二个”：Alice 将拿走石头 2
4. “第一个”：Bob 将拿走石头 1

最后，在第三阶段，Alice 和 Bob 根据 Claire 的决定开始真正拿走石头。第一个无法进行必要操作的玩家（因为对应的石头已经被拿走）输掉游戏。注意，由于有 $n$ 块石头和 $n+1$ 次移动，其中一名玩家最终一定会输掉游戏。

在上面的例子中，Alice 开始时拿走了石头 1。Bob 接着拿走了石头 2。Alice 想继续拿走石头 2，但它已经被拿走了，所以 Alice 输掉了游戏，Bob 获胜。

给定数字 $n$ 以及游戏在第一阶段进行到某一点时的状态：已经做出的 $k$ 次声明序列。这些声明可以是完全任意的。

从这一点开始，Alice 和 Bob 将按照以下段落所述进行最优博弈。

无论 Alice 和 Bob 如何博弈，Claire 选择每一种 $2^{n+1}$ 种可能场景的概率是相等的。Alice 和 Bob 都知道这一点，因此在进行最优博弈时，他们都在试图最小化自己输掉的场景数量。

假设 Alice 和 Bob 将按照上述方式进行剩余的游戏。请为这两名玩家分别找出他们获胜的场景数量。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $k$ ($1 \le n \le 35$, $0 \le k \le n+1$)：石头的数量和已经做出的声明数量。

接下来的 $k$ 行，每行描述一次声明，按声明顺序排列。每行包含两个空格分隔的整数：两块石头的编号（均在 $1$ 到 $n$ 之间，包含边界，且不一定不同）。

注意，当 $k < n+1$ 时，下一个进行声明的玩家取决于 $k$ 的奇偶性。

输出格式

输出一行，包含两个空格分隔的整数：假设两名玩家都按照题目描述进行剩余博弈，Alice 获胜的场景数量和 Bob 获胜的场景数量。

注意，你打印的两个数字之和必须等于 $2^{n+1}$。

子任务

• 子任务 1 (15 分)：$n \le 4$。
• 子任务 2 (34 分)：$n \le 10$。
• 子任务 3 (20 分)：$n \le 25$。
• 子任务 4 (10 分)：$k = 0$。
• 子任务 5 (21 分)：无附加限制。

样例

样例输入 1

3 4
1 3
2 2
3 2
1 3

样例输出 1

4 12

样例输入 2

2 0

样例输出 2

4 4

说明

第一个样例对应题目描述中的例子。没有更多的声明需要做出，所以我们只需要看 Claire 的可能决定中有多少导致 Alice 获胜，有多少导致 Bob 获胜。如果 Claire 在第一步为 Alice 选了石头 1，在第二步为她选了石头 3，Alice 就会获胜，在所有其他情况下她都会输。

在第二个样例中，如果 Alice 开始时声明“1 1”，Bob 将继续“2 2”，无论 Alice 在第三步声明什么，她都会输，因为 Claire 将不得不为第一步选石头 1，为第二步选石头 2，而第三步将没有石头留给 Alice。然而，这不是 Alice 的最优首步：相反，她应该从声明“1 2”开始。然后，无论 Bob 在第二步做什么，Alice 在第三步做什么，他们每个人都会在 8 种情况中的 4 种里获胜。