You have decided to create a level $K$ JOI Flag as the new flag for the Japanese Olympiad in Informatics.

A level $K$ JOI Flag is defined as follows: A level $0$ JOI Flag is a $1 \times 1$ grid containing one of the characters 'J', 'O', or 'I'. For an integer $m > 0$, a level $m$ JOI Flag is a $2^m \times 2^m$ grid where each cell contains one of the characters 'J', 'O', or 'I', satisfying the following condition: when the entire grid is divided into four $2^{m-1} \times 2^{m-1}$ squares, they consist of a level $m-1$ JOI Flag, a part consisting only of cells with 'J', a part consisting only of cells with 'O', and a part consisting only of cells with 'I'.

For example,

OIJJ
JJJJ
OOII
OOII

is a level $2$ JOI Flag. Also,

IIIIIIOO
IIIIIIOO
IIIIJOJJ
IIIIOIJJ
JJJJOOOO
JJJJOOOO
JJJJOOOO
JJJJOOOO

is a level $3$ JOI Flag.

You have a $2^K \times 2^K$ flag with some cells already filled with 'J', 'O', or 'I'. You want to complete a level $K$ JOI Flag by adding characters to some empty cells or modifying some of the characters already written on the flag. Writing a character in an empty cell costs $0$, while modifying a character in a cell that is already filled costs $1$.

Find the minimum cost required to complete a level $K$ JOI Flag.

Input

Read the following input from standard input: The first line contains two integers $K$ and $N$, separated by a space. $K$ represents the level of the JOI Flag, and $N$ represents the number of cells already filled with characters. The characters are numbered $1, 2, \dots, N$. The following $N$ lines contain information about the characters. The $(i+1)$-th line contains $X_i$, $Y_i$, and $C_i$, separated by spaces. This indicates that the character $C_i$ is written in the $X_i$-th column from the left and the $Y_i$-th row from the top.

Output

Output the minimum cost required to create a level $K$ JOI Flag as an integer on a single line.

Constraints

• $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$ is one of 'J', 'O', or 'I'.
• All pairs $(X_i, Y_i)$ are distinct.

Subtasks

For 40% of the test cases, $K \le 10$ is satisfied.

Examples

Input 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

Output 1

3

Note 1

This input represents the following flag (where '-' denotes an empty cell):

OI-O
-JJ-
IOI-
--IO

This can be transformed into the following flag with a cost of $3$:

OIJJ
JJJJ
OOII
OOII

Input 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

Output 2

9