Chessboard

On a very large chessboard stand many chessmen, all of the same colour. A chessman is said to capture a square when it can move onto that square in a single move. In particular, a destination square is captured only when both of the following hold:

• no chessman stands on the destination square, and
• for a queen, a rook, or a bishop, no chessman lies on any square between the piece and the destination.

A chessman never captures the square it currently stands on. A single square may be captured by several chessmen at once.

Each chessman moves by the standard chess rules:

• K (king) moves one square in any of the 8 directions.
• S (knight) jumps in an L-shape (2 squares then 1 square) and is never blocked by other chessmen.
• W (rook) slides any distance horizontally or vertically.
• G (bishop) slides any distance diagonally.
• H (queen) slides any distance horizontally, vertically, or diagonally.

For every chessman, determine how many squares it captures.

The first line contains two integers $n$ and $m$, separated by a single space ($1 \le n \le 200\,000$, $1 \le m \le 10^9$): the number of chessmen and the side length of the square board.

Each of the next $n$ lines has the form F x y, where F is a letter describing the chessman:

• G - bishop
• H - queen
• K - king
• S - knight
• W - rook

and $(x, y)$ is the position of that chessman ($1 \le x, y \le m$). No two chessmen occupy the same position.

Output $n$ lines. The $i$-th line contains a single integer: the number of squares captured by the $i$-th chessman from the input.

The figure illustrates the board from the example. Lines of different styles mark the squares captured by the sliding pieces, and the large dots mark the squares reachable by the knight.