题目描述

Bessie 正在玩一款流行的游戏“Moo Hunt”。在这个游戏中，有 $N$ ($3 \le N \le 20$) 个排成一行的格子，编号从 $1$ 到 $N$。每个格子要么包含字符 $M$，要么包含字符 $O$，其中第 $i$ 个格子包含字符 $s_i$。

Bessie 计划进行 $K$ ($1 \le K \le 2 \cdot 10^5$) 次移动。在第 $i$ 次移动中，Bessie 将点击 $3$ 个不同的格子 ($x_{i},y_{i},z_{i}$) ($1 \le x_{i},y_{i},z_{i} \le N$)。如果 $s_{x_i}=M$ 且 $s_{y_i}=s_{z_i}=O$，Bessie 就会得一分。换句话说，如果 Bessie 按顺序点击格子 $x_{i},y_{i},z_{i}$ 构成了字符串 $MOO$，她就能得一分。

Farmer John 想要帮助 Bessie 获得新的最高分。他希望你求出 Bessie 在所有可能的棋盘配置下能够获得的最高分数，以及能够让 Bessie 达到此最高分的不同棋盘的数量。如果两个棋盘中存在至少一个格子对应的字符不同，则这两个棋盘被视为不同。

输入格式

第一行包含 $N$ 和 $K$，分别表示格子的数量和 Bessie 将要进行的移动次数。

接下来的 $K$ 行，每行包含 $x_i, y_i, z_i$，描述 Bessie 的第 $i$ 次移动（$x_i, y_i, z_i$ 两两不同）。

输出格式

输出 Bessie 可能达到的最高分数，以及能够让 Bessie 达到此最高分的不同棋盘的数量。

样例

样例输入 1

5 6
1 2 3
1 2 3
1 3 5
2 3 4
5 3 2
5 2 3

样例输出 1

4 2

说明 1

棋盘 $MOOOM$ 和 $MOOMM$ 允许 Bessie 达到 $4$ 分的最高分。在这两个棋盘中，Bessie 都会在第 $1, 2, 5, 6$ 次移动中得分。可以证明这是 Bessie 能达到的最高分数，且这两个棋盘是仅有的能让 Bessie 达到 $4$ 分的棋盘。

样例输入 2

6 12
2 4 3
2 3 4
3 5 2
3 5 1
3 1 5
3 1 2
6 1 5
1 6 4
2 3 6
3 6 2
4 1 6
3 4 2

样例输出 2

6 3

说明 2

能够让 Bessie 达到 $6$ 分最高分的棋盘是 $OOMOOO$、$OOMMOO$ 和 $OOMOOM$。

子任务

• 测试点 3-5：$N \le 8, K \le 10^4$
• 测试点 6-12：对于每个 $N \in \{14,15,16,17,18,19,20\}$ 均有一个测试用例，对 $K$ 无额外限制。