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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def query_cumsum2d(s, x1, y1, x2, y2):
    # [x1, x2) × [y1, y2)
    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1
    return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]

def main():
    N, K = LI()
    G = [[0 for _ in range(2*K)] for __ in range(2*K)]
    cumsum2d = [[0 for _ in range(2*K + 1)] for __ in range(2*K + 1)]
    xyc = []
    for _ in range(N):
        x, y, c =  LS()
        x = int(x)
        y = int(y)
        if c == 'W':
            x += K
        x = x % (2 * K)
        y = y % (2 * K)
        G[x][y] += 1
        xyc.append((x, y, c))
    for x in range(2*K):
        for y in range(2*K):
            cumsum2d[x+1][y+1] = (
                cumsum2d[x+1][y]
                + cumsum2d[x][y+1]
                - cumsum2d[x][y]
                + G[x][y]
            )
    ans = 0
    # import pdb
    # print('cum: ')
    # for row in cumsum2d:
    #     print(row)
    # print()
    # print('g: ')
    # for row in G:
    #     print(row)
    for x in range(K):
        for y in range(K):
            # pdb.set_trace()
            cnt = (
                  query_cumsum2d(cumsum2d, 0, 0, x, y)
                + query_cumsum2d(cumsum2d, x, y, x+K, y+K)
                + query_cumsum2d(cumsum2d, x+K, 0, 2 * K, y)
                + query_cumsum2d(cumsum2d, 0, y+K, x, 2 * K)
                + query_cumsum2d(cumsum2d, 2*K, 2*K, x+K, y+K)
            )

            ans = max(ans, cnt, N - cnt)
    print(ans)



main()