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 CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

int x[100005];
int y[100005];
int B[2005][2005];
int W[2005][2005];

template<int VW, int VH> struct add2D {
	int v[VH][VW];
	void set(int x,int y,int c){v[y][x]=c;}
	void build(){
	int i,j;
	for(i=0;i<VH;i++){
		for(j=0;j<VW;j++){
			if(i>0){v[i][j]+=v[i-1][j];}
			if(j>0){v[i][j]+=v[i][j-1];}
			if(i>0&&j>0){v[i][j]-=v[i-1][j-1];}
		}
	}
	}
	int get(int sx,int sy,int tx,int ty){
	int ret=v[ty][tx];
	if(sy>0){ret-=v[sy-1][tx];}
	if(sx>0){ret-=v[ty][sx-1];}
	if(sy>0&&sx>0){ret+=v[sy-1][sx-1];}
	return ret;
	}
};

add2D<4005,4005>BR,WR;

int main() {

	int N,K;

	cin>>N>>K;

	int i,j;

	for(i=0;i<N;i++){
		char c;
		cin>>x[i]>>y[i]>>c;

		if(c=='W'){W[y[i]%(2*K)][x[i]%(2*K)]++;}
		else{B[y[i]%(2*K)][x[i]%(2*K)]++;}
	}
	for(i=0;i<4*K;i++){
		for(j=0;j<4*K;j++){
		BR.set(j,i,B[i%(2*K)][j%(2*K)]);
		WR.set(j,i,W[i%(2*K)][j%(2*K)]);
		}
	}
	BR.build();
	WR.build();

	int ans=0;

	for(i=0;i<2*K;i++){
		for(j=0;j<2*K;j++){
			int b=BR.get(j,i,j+K-1,i+K-1)+BR.get(j+K,i+K,j+(2*K)-1,i+(2*K)-1);
			int w=WR.get(j+K,i,j+(2*K)-1,i+K-1)+WR.get(j,i+K,j+K-1,i+(2*K)-1);
			if(ans<w+b){ans=w+b;}
		}
	}
	cout<<ans<<endl;

	return 0;
}