Chess Pieces Attack Coverage

Given an \(n \times n\) chessboard with \(m\) chess pieces placed on it, count the number of squares that are attacked by at least one piece. The pieces can be of three types: knight, rook, and queen. Their attack patterns are defined as follows:

• Knight: Attacks its own square and all squares that can be reached by a knight's move (i.e. two squares in one direction and one square in the perpendicular direction). In particular, from position \((r, c)\), it can attack \((r, c)\) as well as \((r+2, c+1)\), \((r+2, c-1)\), \((r-2, c+1)\), \((r-2, c-1)\), \((r+1, c+2)\), \((r+1, c-2)\), \((r-1, c+2)\), and \((r-1, c-2)\) if those cells are within the board.
• Rook: Attacks all squares in the same row and the same column as its position, including the square it occupies.
• Queen: Attacks all squares in the same row, the same column, and along both diagonals as its position, including its own square. The diagonal attack covers all squares \((r+i, c+i)\), \((r+i, c-i)\), \((r-i, c+i)\), and \((r-i, c-i)\) until going out of bounds.

Your task is to compute the total number of distinct squares that are attacked by at least one piece.

Note: The board uses 1-indexed coordinates.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the size of the chessboard and the number of chess pieces respectively.

The next \(m\) lines each contain two integers \(r\) and \(c\) and a string \(type\). Here \(r\) and \(c\) denote the row and column where a piece is placed and \(type\) is one of "knight", "rook", or "queen".

outputFormat

Output a single integer representing the number of squares that are attacked by at least one chess piece.

sample

3 1
2 2 queen

9