Bessie đang chơi trò chơi nổi tiếng "Moo Hunt". Trong trò chơi này, có \(N\) (\(3\le N\le 20\)) ô nằm trên một hàng, được đánh số từ \(1\) đến \(N\). Mỗi ô chứa ký tự M hoặc O, trong đó ô thứ \(i\) chứa ký tự \(s_i\).

Bessie dự định thực hiện \(K\) (\(1\le K\le 2\cdot 10^5\)) lượt chơi. Trong lượt thứ \(i\), Bessie sẽ chạm vào \(3\) ô khác nhau \((x_i,y_i,z_i)\) (\(1\le x_i,y_i,z_i\le N\)). Bessie nhận được một điểm nếu \(s_{x_i}=M\) và \(s_{y_i}=s_{z_i}=O\). Nói cách khác, Bessie nhận được một điểm nếu tạo thành xâu MOO bằng cách lần lượt chạm vào các ô \(x_i,y_i,z_i\) theo thứ tự đó.

Farmer John muốn giúp Bessie lập kỷ lục mới. Ông muốn bạn tìm điểm số lớn nhất Bessie có thể đạt được trong số tất cả các bảng có thể có khi cô thực hiện \(K\) lượt chơi, đồng thời tìm số lượng bảng khác nhau cho phép Bessie đạt được điểm số lớn nhất này. Hai bảng được coi là khác nhau nếu tồn tại một ô mà ký tự tương ứng tại ô đó khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\), lần lượt là số ô và số lượt chơi Bessie sẽ thực hiện.

Mỗi dòng trong \(K\) dòng tiếp theo chứa \(x_i,y_i,z_i\), mô tả lượt chơi thứ \(i\) của Bessie (\(x_i,y_i,z_i\) đôi một khác nhau).

Dữ liệu ra

In ra điểm số lớn nhất Bessie có thể đạt được, tiếp theo là số lượng bảng khác nhau cho phép Bessie đạt được điểm số lớn nhất này.

Ví dụ

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

Phân nhóm

• Test 3–5: \(N\le 8\), \(K\le 10^4\).
• Test 6–12: Có một test ứng với mỗi \(N\in\{14,15,16,17,18,19,20\}\) và không có thêm ràng buộc nào đối với \(K\).

Nguồn

USACO 2026 Contest 2, Bronze Division — bài gốc Moo Hunt, tác giả: Alex Liang.
https://usaco.org/index.php?page=viewproblem2&cpid=1564