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 <iostream>
#include <cstring>

using namespace std;

const int MAXN=10000;
const int MAXK=1000;

int y1[10*MAXK+5];//记录y=y1行黑色格子的个数 

struct point{
	int x;
	int y;
	int c;
}a[100000];

int main(int argc, char *argv[]) {
	int N,K;
	while(cin>>N>>K) {
		int Max=0,cnt=0;//cnt记录黑色格子的总个数 
		int i;
		for(i=0;i<N;i++) {
			char ch;
			cin>>a[i].x>>a[i].y>>ch;
			a[i].x%=(2*K);//降维,*2k或%2k都仅仅是改变了它的位置，而没有改变它的颜色。
			a[i].y%=(2*K);
			if(ch=='W')
				a[i].c=1;//白色格子标记为1
			else
				a[i].c=0;
		}
		
		for(i=0;i<K;i++) {//在那个2k*2k的格子里枚举长度为k的横竖边 
			cnt=0;
			memset(y1,0,sizeof(y1));
			int j;
			for(j=0;j<N;j++) {//依次遍历各点 
				int p=(i<=a[j].x&&a[j].x<i+K);
				int q=(0<=a[j].y&&a[j].y<K); 
				//cout<<"p="<<p<<" "<<"q="<<q<<endl;
				if(p^q==a[j].c) {//通过异或运算，被两条边都覆盖了的和都没被覆盖是一个颜色，其它的格子是另一个颜色。  
					cnt++;
					y1[a[j].y]++; 
				} 
				else
					y1[a[j].y]--;
				//cout<<"y1[a["<<j<<"].y]="<<y1[a[j].y]<<endl;
			}
			for(j=0;j<K;j++) {
				if(cnt>Max)
					Max=cnt;
				if(N-cnt>Max)//若白色格子比黑色格子多，则让Max取白色格子的个数 
					Max=N-cnt;
				if(j!=K)
					cnt=cnt-y1[j]-y1[j+K];
			}
		}
		
		cout<<Max<<endl; 
	}
	
	return 0;
}