题目背景

译自 COCI 2024/2025 #4 T1。$\texttt{3s,0.5G}$。满分为 $50$。

题目描述

有一块 $n\times n$ 的国际象棋棋盘，上面摆放着 $m$ 个棋子。棋子的类型只有骑士（knight），车（rook）和皇后（queen）。

已知

• 骑士的攻击范围为：骑士所在的格子，以及骑士所在的格子走一列两行（或者一行两列）能走到的所有格子；
• 车的攻击范围为：与车所在的格子同一行或者同一列的格子（包括车所在的格子）；
• 皇后的攻击范围为：与皇后所在的格子同一行，同一列或者同一对角线的格子（包括皇后所在的格子）。

求出这个棋盘上有多少个格子被至少一个棋子攻击。

输入格式

第一行，两个正整数 $n,m$。

接下来 $m$ 行，每行一个字符和两个正整数 $C,x,y$，表示有一枚类型 $C$ 的棋子在 $(x,y)$。

• $C=\texttt{N}$，表示骑士；
• $C=\texttt{R}$，表示车；
• $C=\texttt{Q}$，表示皇后。

数据保证不会有两个棋子在一个格子里。

输出格式

输出一行一个正整数，表示答案。

7 1
Q 4 4

25

5 1
N 3 3

9

6 3
R 1 4
Q 2 1
N 5 2

25

提示

样例解释

样例 $1,2$ 解释见图片。注意，每个棋子也会攻击它所在的格子。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 200$；
• $1\le m\le n^2$；
• 不会有两个棋子在一个格子里。