你决定制作一面 $K$ 级的 JOI Flag 作为日本信息学奥林匹克竞赛的新旗帜。

定义如下： $0$ 级 JOI Flag 是一个 $1 \times 1$ 的方格，上面写有 'J', 'O', 'I' 中的任意一个字符。 对于整数 $m > 0$，$m$ 级 JOI Flag 是一个 $2^m \times 2^m$ 的方格，每个格子上都写有 'J', 'O', 'I' 中的一个字符，且满足以下条件：将整个方格平分为 4 个 $2^{m-1} \times 2^{m-1}$ 的正方形时，这 4 个部分分别由一个 $m-1$ 级 JOI Flag、一个仅由 'J' 组成的区域、一个仅由 'O' 组成的区域和一个仅由 'I' 组成的区域组成。

例如：

OIJJ
JJJJ
OOII
OOII

是一个 $2$ 级 JOI Flag。此外，

IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO

是一个 $3$ 级 JOI Flag。

你手头有一个 $2^K \times 2^K$ 的旗帜，其中一些格子上已经写有 'J', 'O', 'I' 中的字符。你可以通过添加字符或修改已有的字符来完成 $K$ 级 JOI Flag。在没有字符的格子上写字符的代价为 $0$，而修改已有格子的字符代价为 $1$。

请计算完成 $K$ 级 JOI Flag 所需的最小代价。

题目描述

给定你手头旗帜的信息，编写一个程序，计算完成 $K$ 级 JOI Flag 所需的最小代价。

数据范围

• $1 \le K \le 30$
• $1 \le N \le 1000$
• $1 \le X_i \le 2^K$
• $1 \le Y_i \le 2^K$
• $C_i$ 为 'J', 'O', 'I' 中的任意一个。
• 所有坐标组 $(X_i, Y_i)$ 均不相同。

输入格式

从标准输入读取以下内容： 第一行包含两个整数 $K$ 和 $N$，以空格分隔。$K$ 表示 JOI Flag 的级别，$N$ 表示已填入字符的格子数量。 接下来的 $N$ 行包含字符信息。第 $i+1$ 行包含 $X_i, Y_i, C_i$，以空格分隔，表示字符 $C_i$ 位于从左往右第 $X_i$ 列，从上往下第 $Y_i$ 行。

输出格式

将完成 $K$ 级 JOI Flag 所需的最小代价作为整数输出到标准输出。

子任务

在所有测试数据中，有 $40\%$ 的分数满足 $K \le 10$。

样例

样例输入 1

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

样例输出 1

3

说明

该输入表示如下旗帜（用 '-' 表示未填写的格子）：

OI-O
-JJ-
IOI-
--IO

代价为 $3$ 时，可以将其变为：

OIJJ
JJJJ
OOII
OOII

样例输入 2

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

样例输出 2

9