Bạn muốn làm một lá cờ JOI cấp \(K\) để dùng làm lá cờ mới cho Olympic Tin học Nhật Bản. Cờ JOI được định nghĩa như sau:

• Cờ JOI cấp \(0\) là một bảng \(1\times1\), trong ô duy nhất có một trong các ký tự J, O, I.
• Với số nguyên \(m>0\), cờ JOI cấp \(m\) là một bảng \(2^m\times2^m\), mỗi ô chứa một trong các ký tự J, O, I. Khi chia bảng thành bốn hình vuông \(2^{m-1}\times2^{m-1}\), bốn phần này phải gồm: một cờ JOI cấp \(m-1\), một phần chỉ chứa J, một phần chỉ chứa O và một phần chỉ chứa I. Bốn phần có thể nằm ở các vị trí bất kỳ trong bốn góc.

Chẳng hạn, bảng sau là một cờ JOI cấp \(2\):

OIJJ
JJJJ
OOII
OOII

Bảng sau là một cờ JOI cấp \(3\):

IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO

Bạn đang có một lá cờ gồm \(2^K\times2^K\) ô, trong đó một số ô đã được viết một ký tự J, O hoặc I. Bạn muốn điền thêm ký tự vào các ô trống và sửa một số ký tự đã có để hoàn thành một cờ JOI cấp \(K\). Viết một ký tự vào ô trống có chi phí \(0\); thay đổi ký tự đã có trong một ô có chi phí \(1\).

Yêu cầu

Hãy tính tổng chi phí nhỏ nhất để hoàn thành lá cờ.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(K,N\) cách nhau bởi dấu cách, lần lượt là cấp của cờ JOI cần tạo và số ô đã có ký tự. Các ký tự đã có được đánh số từ \(1\) đến \(N\).
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa \(X_i,Y_i,C_i\) cách nhau bởi dấu cách, cho biết ký tự \(C_i\) nằm ở cột thứ \(X_i\) từ trái sang và hàng thứ \(Y_i\) từ trên xuống.

Dữ liệu ra

In ra đầu ra chuẩn trên một dòng một số nguyên là tổng chi phí nhỏ nhất để tạo cờ JOI cấp \(K\).

Ràng buộc

• \(1\le K\le30\).
• \(1\le N\le1\,000\).
• \(1\le X_i\le2^K\) và \(1\le Y_i\le2^K\) với \(1\le i\le N\).
• \(C_i\) là một trong các ký tự J, O, I.
• Các cặp \((X_i,Y_i)\) đôi một khác nhau.
• \(K,N,X_i,Y_i\) đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(K\le10\).

Ví dụ

2 10
2 2 J
3 3 I
1 3 I
1 1 O
3 2 J
2 1 I
4 1 O
3 4 I
4 4 O
2 3 O

3

OI-O
-JJ-
IOI-
--IO

OIJJ
JJJJ
OOII
OOII

4 30
16 14 J
2 8 O
10 9 J
10 13 I
6 6 O
11 14 I
1 2 I
3 2 O
3 10 O
1 12 I
4 11 I
9 5 J
15 1 O
12 4 I
16 5 J
10 7 J
3 8 J
4 10 I
4 7 I
2 11 I
2 12 O
15 5 J
15 7 J
6 9 J
5 7 O
14 5 J
12 11 J
15 10 O
13 16 I
13 11 I

9