说明

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 将获得一分。换句话说，如果她按照顺序点击格子 $x_{i}, y_{i}, z_{i}$ 形成的字符串是 $MOO$，她就会得分。

Farmer John 想要帮助 Bessie 获得一个新的高分。他希望你在所有可能的棋盘配置中，找出 Bessie 进行这 $K$ 次移动所能获得的最大可能得分，以及能使 Bessie 达到这个最大可能得分的不同棋盘的数量。两个棋盘被认为是不同的，当且仅当存在一个格子，其上的字符不同。

输入格式

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

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

输出格式

输出 Bessie 所能获得的最大可能得分，以及能使 Bessie 达到这个最大得分的不同棋盘的数量。

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

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

6 3

提示

样例 1 解释

棋盘 $MOOOM$ 和 $MOOMM$ 可以使 Bessie 获得最大得分 $4$。在这两个棋盘上，Bessie 将在第 $1, 2, 5, 6$ 次移动中得分。可以证明这是 Bessie 能够获得的最大得分，并且只有这两个棋盘能使 Bessie 获得 $4$ 分。

样例 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$ 没有额外限制。

翻译由 DeepSeek 完成