human
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
Solve the task in PYTHON3.

=====
Give me a Python code to print the maximum number of desires that can be satisfied at the same time?
assistant
#Here is Python code to print the maximum number of desires that can be satisfied at the same time.

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    
    imos2d = [[0]*(2*K+1) for _ in range(2*K+1)]
    
    def get_cord(x):
        if x<K-1:
            return [(0,x+1), (x+K+1,2*K)]
        else:
            return [(x-K+1,x+1)]

    for _ in range(N):
        x,y,c = ST().split()
        x,y = int(x), int(y)
        if c=="W":
            x+=K
        x,y = x%(2*K), y%(2*K)
        for base in [0,K]:
            for l,r in get_cord((x+base)%(2*K)):
                for u,d in get_cord((y+base)%(2*K)):
                    imos2d[l][u] += 1
                    imos2d[l][d] -= 1
                    imos2d[r][u] -= 1
                    imos2d[r][d] += 1

    for i in range(2*K):
        for j in range(2*K+1):
            imos2d[i+1][j] += imos2d[i][j]
    
    for i in range(2*K+1):
        for...