在一个巨大的棋盘上放置了许多棋子$^{1}$——它们颜色相同。我们称一个棋子可以吃掉棋盘上的某个指定位置，当且仅当该棋子可以移动到该位置，且满足以下条件：

• 目标位置上没有其他棋子；
• 从初始位置到目标位置的路径上没有其他棋子（对于皇后、车和象而言）。

任何棋子都不能吃掉它自身所在的位置。注意，同一个位置可以被多个棋子同时吃掉。

编写一个程序：

• 从标准输入读取棋盘的描述；
• 对于每个棋子，计算该棋子可以吃掉的位置数量；
• 将结果写入标准输出。

$^{1}$你可以通过此处了解更多关于国际象棋和棋子的信息：http://en.wikipedia.org/wiki/Chess_piece。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 200\,000$, $1 \le m \le 10^{9}$)，由一个空格分隔，分别表示棋盘上放置的棋子数量和棋盘的边长 $m$。接下来的 $n$ 行，每行格式为 "$ F $ $ x $ $ y $", 其中 $ F $ 是一个字符，代表：

• G - 象 (bishop)，
• H - 皇后 (queen)，
• K - 王 (king)，
• S - 马 (knight)，
• W - 车 (rook)，

且 $(x, y)$ 是棋子的位置 ($1 \le x, y \le m$)。没有两个棋子位于同一位置。

输出格式

输出应包含 $n$ 行。第 $i$ 行应包含一个整数，表示输入中第 $i$ 个棋子可以吃掉的位置数量。

样例

输入 1

6 5
K 5 5
G 4 1
W 1 3
K 2 3
H 2 2
S 3 3

输出 1

3
2
4
5
7
7

上图展示了样例输入中的棋盘。不同样式的线条表示棋子可以吃掉的位置。马可以到达的目标位置用大圆点表示。