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

Solution:


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Reader.init(System.in);
		int nReq = Reader.nextInt();
		int len = Reader.nextInt();
		int cntB[][] = new int[len][len];
		int cntW[][] = new int[len][len];
		for(int i = 0; i < nReq; i++) {
			int x = Reader.nextInt();
			int y = Reader.nextInt();
			char ch = Reader.next().charAt(0);
			int rx = (x / len) % 2;
			int ry = (y / len) % 2;
			if( (ch == 'B' && (rx + ry) % 2 == 0) ||
				(ch == 'W' && (rx + ry) % 2 == 1) ){
				cntB[x % len][y % len]++;
			}
			else if( (ch == 'W' && (rx + ry) % 2 == 0) || 
					 (ch == 'B' && (rx + ry) % 2 == 1) ){
				cntW[x % len][y % len]++;
			}
		}

		int[][] sumW = new int[len][len];
		int[][] sumB = new int[len][len];
		for(int i = 0; i < len; i++) {
			for(int j = 0; j < len; j++) {
				sumW[i][j] = (i == 0 ? 0 : sumW[i - 1][j]) + 
						(j == 0 ? 0 : sumW[i][j - 1]) - 
						( (i == 0 || j == 0) ? 0 : sumW[i - 1][j - 1]) + 
						cntW[i][j];
				sumB[i][j] = (i == 0 ? 0 : sumB[i - 1][j]) + 
						(j == 0 ? 0 : sumB[i][j - 1]) - 
						( (i == 0 || j == 0) ? 0 : sumB[i - 1][j - 1]) + 
						cntB[i][j];
			}
		}

		int ans = 0;
		for(int i = 0; i < len; i++) {
			for(int j = 0; j < len; j++) {
				int amo = 0;
				amo = (sumB[i][j] + sumB[len - 1][len - 1] - sumB[i][len - 1] - sumB[len - 1][j] + sumB[i][j]) +
						(sumW[i][len - 1] + sumW[len - 1][j] - 2 * sumW[i][j]);
				if(amo > ans)
					ans = amo;
				amo = (sumW[i][j] + sumW[len - 1][len - 1] - sumW[i][len - 1] - sumW[len - 1][j] + sumW[i][j]) +
						(sumB[i][len - 1] + sumB[len - 1][j] - 2 * sumB[i][j]);
				if(amo > ans)
					ans = amo;
			}
		}
		System.out.println(ans);
	}

}

/** Class for buffered reading int and double values */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
	
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
    public static void main(String[] args) {
    	
    }
}