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:
# -*- coding: utf-8 -*-

"""
参考：https://pitsbuffersolution.com/compro/atcoder/arc089d.php
　　　http://tutuz.hateblo.jp/entry/2018/06/20/212752
　　　https://paiza.hatenablog.com/entry/2014/05/28/%E3%82%82%E3%81%97%E5%A5%B3%E5%AD%90%E5%A4%A7%E7%94%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AB%E3%80%8E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%8F%E3%82%92%E5%9B%B3
　　　http://www.learning-algorithms.com/entry/2018/01/31/144519
　　　https://img.atcoder.jp/arc089/editorial.pdf
・2次元累積和
・0-indexedのまま行くか1-indexedにするか人によって色々で、
　それぞれに考慮する点があると思った。
・とりあえず理解重視で、処理を分けて実装したから、このままだと多分pypyでもTLEかと。
"""

import sys
def input(): return sys.stdin.readline().strip()

N, K = map(int, input().split())

# K*2の正方形を右下まで動かすので、K*4まで作っておく
B = [[0] * (K*4+1) for i in range(K*4+1)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 白に塗る条件はxかyにKずらして黒の条件にする(これで2色考えなくていい)
    if c == 'W':
        y += K
    # 循環するのでmod K*2でやる
    # 累積和でひとつ前を見に行くので、1-indexedにする
    B[x%(K*2)+1][y%(K*2)+1] += 1

for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        # K*2からはみ出る範囲も正しく累積和を出すため、K*2までの値を循環させる
        # 1-indexedにしているため、ここの加減がややこしい
        B[i][j] = B[(i-1)%(K*2)+1][(j-1)%(K*2)+1]

# 2次元累積和を取る
# 1-indexedなので、気にせず1からループすればいい
for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        B[i][j] += B[i][j-1]
for i in range(1, K*4+1):
    for j in range(1, K*4+1):
        B[i][j] += B[i-1][j]

# 2次元累積和に必要な4点の加減を行う
def get_sum(x1, y1, x2, y2, sm):
    # 1-indexedなので、x, yがマイナスの値になる考慮は必要ない
    res = sm[x2][y2] - sm[x1-1][y2] - sm[x2][y1-1] + sm[x1-1][y1-1]
    return res

ans = 0
for i in range(1, K*2+1):
    for j in range(1, K*2+1):
        # 1つ目の黒い正方形
        tmp = get_sum(i, j, i+K-1, j+K-1, B)
        # 2つ目の黒い正方形
        tmp += get_sum(i+K, j+K, i+K*2-1, j+K*2-1, B)
        ans = max(tmp, ans)
print(ans)