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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

# A:product
'''
data = input("")
data = data.split(" ")
a = int(data[0])
b = int(data[1])

if (a*b)%2 == 1: print("Odd")
else: print("Even")
'''

# B:1 21
'''
data = input()
data = int(data.replace(" ",""))
if data%(data**(1/2)) == 0: print("Yes")
else: print("No")
'''

# C:Traveling
'''
n = int(input(""))
data = [0]*n
t = [0]*n
x = [0]*n
y = [0]*n
flag = 0

for i in range(n):
    data[i] = input("")
    t[i] = int(data[i].split(" ")[0])
    x[i] = int(data[i].split(" ")[1])
    y[i] = int(data[i].split(" ")[2])

for i in range(n):
    if i == 0:
        if x[i]+y[i] > t[i] or (x[i]+y[i]-t[i])%2 != 0:
            print("No")
            flag = 1
            break
    else:
        if abs(x[i]-x[i-1])+abs(y[i]-y[i-1]) > t[i] or (x[i]+y[i]-t[i])%2 != 0:
            print("No")
            flag = 1
            break
if flag == 0:print("Yes")
'''

# D:Checker
def check(y,x,k):
    l = max(0,min(m,x))
    r = max(0,min(m,x+k))
    d = max(0,min(m,y))
    u = max(0,min(m,y+k))
    f[d][l] += 1
    f[d][r] -= 1
    f[u][l] -= 1
    f[u][r] += 1
n,k = LI()
m = k*2
f = [[0]*(m+1) for i in range(m+1)]
for i in range(n):
    x,y,c = input().split()
    x = int(x)%m
    y = int(y)%m
    if c == "W":
        y += k
        y %= m
    check(y-m+1,x-m+1,k)
    check(y+1,x-m+1,k)
    check(y-k+1,x-k+1,k)
    check(y+k+1,x-k+1,k)
    check(y-m+1,x+1,k)
    check(y+1,x+1,k)
    check(y-k+1,x+k+1,k)
    check(y+k+1,x+k+1,k)

for y in range(m+1):
    for x in range(m):
        f[y][x+1] += f[y][x]

for y in range(m):
    for x in range(m+1):
        f[y+1][x] += f[y][x]

ans = 0
for i in f:
    ans = max(ans,max(i))
print(ans)