Problem: AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K. Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square. Below is an example of a checked pattern of side 3:

cba927b2484fad94fb5ff7473e9aadef.png

AtCoDeer has N desires. The i-th desire is represented by x_i, y_i and c_i. If c_i is `B`, it means that he wants to paint the square (x_i,y_i) black; if c_i is `W`, he wants to paint the square (x_i,y_i) white. At most how many desires can he satisfy at the same time?

Constraints

* 1 ≤ N ≤ 10^5
* 1 ≤ K ≤ 1000
* 0 ≤ x_i ≤ 10^9
* 0 ≤ y_i ≤ 10^9
* If i ≠ j, then (x_i,y_i) ≠ (x_j,y_j).
* c_i is `B` or `W`.
* N, K, x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:


N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N


Output

Print the maximum number of desires that can be satisfied at the same time.

Examples

Input

4 3
0 1 W
1 2 W
5 3 B
5 4 B


Output

4


Input

2 1000
0 0 B
0 1 W


Output

2


Input

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W


Output

4

Solution (in PYTHON3):

Solution:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    K = k * 2
    """
    K * Kに点を全て移したので、この中で黒模様の左下の頂点を全探索。
    二次元累積和で各場合についてO(1)で計算可能。

    まず前準備として白マスはxかyに関してkずらすことで黒マスにできる。こうすれば記述量はもっと減らせた。
    """
    hope = [[0] * (K + 1) for _ in range(K + 1)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'B':
            """あとで累積和を0-indexedで取る都合上、頂点座標は1-indexedにしておく。"""
            hope[1 + y % K][1 + x % K] += 1
        if c == 'W':
            hope[1 + (y + k) % K][1 + x % K] += 1

    """
    二次元累積和の書き方に悩んでたのは失態。
    やってみて気づいたが、やはり累積和は0-indexedにしないと後々の取り扱いが非常に面倒。
    """
    sumB = [[0] * (K + 1) for _ in range(K + 1)]
    for y in range(1, K + 1):
        for x in range(1, K + 1):
            sumB[y][x] = sumB[y-1][x] + sumB[y][x-1] + hope[y][x] - sumB[y-1][x-1]

    def calc_sum(x0, y0, x1, y1):
        # (x0, y0)が左下、(x1, y1)が右上となる矩形領域の値を返す
        return sumB[y1][x1] - sumB[y0-1][x1] - sumB[y1][x0-1] + sumB[y0-1][x0-1]

    """
    あとは黒四角の左下頂点(x, y)に関して全探索。
    """
    ans = 0
    for y in range(1, K+1):
        for x in range(1, k+1):
            if y <= k:
                val = (calc_sum(1, 1, x-1, y-1) + calc_sum(x, y, x+k-1, y+k-1)
                        + calc_sum(x+k, y+k, K, K) + calc_sum(x+k, 1, K, y-1)
                        + calc_sum(1, y+k, x-1, K))
                ans = max(ans, val)
            else:
                val = (calc_sum(x, 1, x+k-1, y-k-1) + calc_sum(1, y-k, x-1, y-1)
                        + calc_sum(x+k, y-k, K, y-1) + calc_sum(x, y, x+k-1, K))
                ans = max(ans, val)
    print(ans)



if __name__ == "__main__":
    main()