Problem:
 Score : 500 points    Problem Statement 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 :     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.        Sample Input 1 4 3
0 1 W
1 2 W
5 3 B
5 4 B      Sample Output 1 4  He can satisfy all his desires by painting as shown in the example above.       Sample Input 2 2 1000
0 0 B
0 1 W      Sample Output 2 2       Sample Input 3 6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W      Sample Output 3 4

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
acc = [[0] * 3 * k for _ in range(2 * k)]
for _ in range(n):
    x, y, c = LS()
    x = int(x); y = int(y)
    if c == 'W':
        x += k
    x %= 2 * k
    y %= 2 * k
    acc[y][x] += 1
    for i, j in ((1, 1), (1, -1), (-1, 1), (-1, -1), (0, 2)):
        if 0 <= y + k * i < 2 * k and 0 <= x + k * j < 3 * k:
            acc[y + k * i][x + k * j] += 1



acc = [[0] * (3 * k + 1)] + [list(accumulate([0] + acc[y])) for y in range(2 * k)]
for y in range(2 * k):
    for x in range(3 * k + 1):
        acc[y + 1][x] += acc[y][x]


ans = 0
for y in range(k + 1):
    for x in range(2 * k + 1):
        ans = max(ans, acc[y + k][x + k] - acc[y][x + k] - acc[y + k][x] + acc[y][x])


print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    L = 2*K
    state = [[[0, 0] for _ in range(L+1)] for _ in range(K+1)]

    for _ in range(N):
        x, y, c = map(str, input().split())
        a, b = int(x)%L, int(y)%L
        k = 0 if c == 'W' else 1
        if a >= K:
            if b >= K:
                a -= K
                b -= K
            else:
                a -= K
                b += K
        state[a+1][b+1][k] += 1


    for i in range(K):
        for j in range(L):
            for k in [0, 1]:
                state[i+1][j+1][k] += state[i+1][j][k] + state[i][j+1][k] - state[i][j][k]

    ans = 0
    for x in range(K):
        for y in range(K):
            for k in [0, 1]:
                count = 0
                count += state[x][y][k]
                count += state[x][L][k] - state[x][y+K][k]
                count += state[K][y+K][k] - state[x][y+K][k] - state[K][y][k] + state[x][y][k]

                l = k ^ 1
                count += state[K][y][l] - state[x][y][l]
                count += state[x][y+K][l] - state[x][y][l]
                count += state[K][L][l] - state[K][y+K][l] - state[x][L][l] + state[x][y+K][l]

                ans = max(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
n, k = map(int, input().split())
list_subj = []
for i in range(n):
  x, y, c = input().split()
  if c == "W":
    list_subj.append([int(x) % (2*k), int(y) % (2*k)])
  else:
    list_subj.append([(int(x) + k) % (2*k), int(y) % (2*k)])

imos_field = [[0] * (2*k+1) for _ in range(2*k+1)]
for x, y in list_subj:
  for place in (0, k):
    adj_y = (y + place) % (2 * k)
    if adj_y >= k - 1:
      imos_y = [(adj_y-k+1, adj_y+1)]
    else:
      imos_y = [(0, adj_y+1), (adj_y+k+1, 2*k)]
    adj_x = (x + place) % (2 * k)
    if adj_x >= k - 1:
      imos_x = [(adj_x-k+1, adj_x+1)]
    else:
      imos_x = [(0, adj_x+1), (adj_x+k+1, 2*k)]
    for bottom, top in imos_y:
      for left, right in imos_x:
        imos_field[bottom][left] += 1
        imos_field[top][left] -= 1
        imos_field[bottom][right] -= 1
        imos_field[top][right] += 1

result = np.cumsum(imos_field, axis=1)
result = np.cumsum(result, axis=0)
result = int(np.max(result))
print(result)

Solution (Python):
import numpy as np
import sys

def sum2d(i1,j1,i2,j2):
    A[i1][j1] += 1
    A[i1][j2] -= 1
    A[i2][j1] -= 1
    A[i2][j2] += 1

N,K = map(int,input().split())
XYC = [list(input().split()) for _ in range(N)]

A = [[0 for _ in range(K*2+1)] for _ in range(K*2+1)]

for x,y,c in XYC:
    i = (int(x) if c=="W" else int(x)+K) % (K*2)
    j = int(y) % (K*2)
    i0 = i%K
    j0 = j%K
    if (i<K and j<K) or (i>=K and j>=K):
        sum2d(0,0,i0,j0) 
        sum2d(i0+K,0,K*2,j0) 
        sum2d(i0,j0,i0+K,j0+K) 
        sum2d(0,j0+K,i0,K*2) 
        sum2d(i0+K,j0+K,K*2,K*2) 
    else:
        sum2d(i0,0,i0+K,j0) 
        sum2d(0,j0,i0,j0+K) 
        sum2d(i0+K,j0,K*2,j0+K) 
        sum2d(i0,j0+K,i0+K,K*2) 


AA = np.array(A)
for i in range(K*2):
    AA[i+1, :] += AA[i, :]
for j in range(K*2):
    AA[:, j+1] += AA[:, j]

print(AA.max())

Solution (Python):
N,K = map(int, input().split())

grid = [[0 for _ in range(2*K)] for _ in range(2*K)]

for _ in range(N):
    x, y, c = input().split()
    i, j = int(x), int(y)
    if c == "B":
        j += K
    i %= (2*K)
    j %= (2*K)
    grid[i][j] += 1

for i in range(2*K):
    for j in range(2*K):
        if i == 0:
            if j != 0:
                grid[i][j] += grid[i][j-1]
        else:
            if j == 0:
                grid[i][j] += grid[i-1][j]
            else:
                grid[i][j] += (grid[i-1][j] + grid[i][j-1] - grid[i-1][j-1])
        

ans = 0
M = grid[2*K-1][2*K-1]
for i in range(K):
    for j in range(K):
        temp = 0
        c = 0
        temp += (M-grid[i+K-1][-1]-grid[-1][j+K-1]+grid[i+K-1][j+K-1])
        temp += grid[i+K-1][j+K-1]
        if i > 0 and j == 0:
            temp += (grid[i-1][-1]-2*grid[i-1][j+K-1])
        if i == 0 and j > 0:
            temp += (grid[-1][j-1]-2*grid[i+K-1][j-1])
        if i > 0 and j > 0:
            temp += (grid[i-1][-1]-2*grid[i-1][j+K-1])
            temp += (grid[-1][j-1]-2*grid[i+K-1][j-1])
            temp += 2*grid[i-1][j-1]
        ans = max(ans, temp, M-temp)
        
print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return


def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return


def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            pre = (x, y, t)
            continue
        print("No")
        return
    print("Yes")
    return












def D():
    n, k = LI()
    dp = [[0] * (2 * k + 1) for i in range(2 * k + 1)]
    for _ in range(n):
        x, y, c = LS()
        x, y = int(x), int(y)
        if c == "W":
            dp[y % (2 * k) + 1][(x + k) % (2 * k) + 1] += 1
        else:
            dp[y % (2 * k) + 1][x % (2 * k) + 1] += 1
    for y in range(2 * k + 1):
        for x in range(1, 2 * k + 1):
            dp[y][x] += dp[y][x - 1]
    for y in range(1, 2 * k + 1):
        for x in range(2 * k + 1):
            dp[y][x] += dp[y - 1][x]
    
    def count(l, r, d, u):
        return dp[d][l] - dp[d][r] - dp[u][l] + dp[u][r]
    
    ans = 0
    for i in range(k):
        for j in range(k):
            tmp = count(j, j + k, i, i + k) + count(0, j, 0, i) + count(j + k, 2 * k, 0, i) + \
                 count(0, j, i + k, 2 * k) + count(j + k, 2 * k, i + k, 2 * k)
            ans = max(ans, tmp, n - tmp)
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k):
    for j in range(1,k):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ans,b[k-1][k-1]-b[i][k-1]-b[k-1][j]+2*b[i][j]+w[i][k-1]+w[k-1][j]-2*w[i][j])
        ans=max(ans,w[k-1][k-1]-w[i][k-1]-w[k-1][j]+2*w[i][j]+b[i][k-1]+b[k-1][j]-2*b[i][j])
print(ans)

Solution (Python):
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k+1):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k+1):
    for j in range(1,k+1):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k):
    for j in range(k):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Solution (Python):
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k+1):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k+1):
    for j in range(1,k+1):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Solution (Python):
import sys
import numpy as np
def main():
    input = sys.stdin.readline
    def gen_pattern(x):
        if x < K-1:
            return [[0, x+1], [x+K+1, 2*K]]
        else:
            return [[x-K+1, x+1]]
    def inputs():
        return [int(x) for x in input().split()]
    def inputstr():
        return list(input().split())
    N,K = inputs()
    BB = [[0]*(2*K+1) for _ in range(2*K+1)]
    for i in range(N):
        x,y,c = inputstr()
        if c=="W":
            y = int(y)+K
        x = int(x)%(2*K)
        y = int(y)%(2*K)
        
        for shift in [0,K]:
            for b,t in gen_pattern((y+shift)%(2*K)):
                for l,r in gen_pattern((x+shift)%(2*K)):
                    BB[b][l] +=1
                    BB[b][r] -=1
                    BB[t][l] -=1
                    BB[t][r] +=1
    ans = (np.max(np.cumsum(np.cumsum(BB, axis=1), axis=0)))
    
    print(int(ans))
main()

Solution (Python):
def d_checker():
    
    
    import numpy as np
    N, K = [int(i) for i in input().split()]

    def get_bound(p):
        """ある希望を満たすような角のマスの集合はKxK正方形区間のようになっている
        p<K-1 のときはその正方形を分割しないとならない"""
        return [(0, p + 1), (p + K + 1, 2 * K)] if p < K - 1 else [(p - K + 1, p + 1)]

    
    
    requests_black = [[0] * (2 * K + 1) for _ in range(2 * K + 1)]
    for _ in range(N):
        x, y, c = input().split()
        x = int(x) % (2 * K)
        y = int(y) % (2 * K) if c == 'B' else (int(y) + K) % (2 * K)

        for shift in (0, K):  
            
            for b, t in get_bound((y + shift) % (2 * K)):
                for l, r in get_bound((x + shift) % (2 * K)):
                    
                    requests_black[b][l] += 1
                    requests_black[t][l] -= 1
                    requests_black[b][r] -= 1
                    requests_black[t][r] += 1
    
    return int(np.max(np.cumsum(np.cumsum(requests_black, axis=1), axis=0)))

print(d_checker())

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,K = II()
x = [0]*N
y = [0]*N
z = ['0']*N
for i in range(N):
    a,b,c = input().split()
    x[i],y[i],z[i] = int(a),int(b),c

x,y = y,x

for i in range(N):
    if z[i]=='B':
        x[i] = (2*K-1)-x[i]%(2*K)
        y[i] = y[i]%(2*K)
    else:
        x[i] += K
        x[i] = (2*K-1)-x[i]%(2*K)
        y[i] = y[i]%(2*K)

kukan = []
for i in range(N):
    if x[i]+K-1<=2*K-1:
        if y[i]-K+1>=0:
            kukan.append([x[i],x[i]+K-1,y[i]-K+1,y[i]])
        else:
            kukan.append([x[i],x[i]+K-1,0,y[i]])
            kukan.append([x[i],x[i]+K-1,K+y[i]+1,2*K-1])
    else:
        if y[i]-K+1>=0:
            kukan.append([0,x[i]-K-1,y[i]-K+1,y[i]])
            kukan.append([x[i],2*K-1,y[i]-K+1,y[i]])
        else:
            kukan.append([0,x[i]-K-1,0,y[i]])
            kukan.append([0,x[i]-K-1,K+y[i]+1,2*K-1])
            kukan.append([x[i],2*K-1,0,y[i]])
            kukan.append([x[i],2*K-1,K+y[i]+1,2*K-1])

tiles = [[0]*(2*K+1) for _ in range(2*K+1)]
for k in kukan:
    tiles[k[0]][k[2]] += 1
    tiles[k[0]][k[3]+1] -= 1
    tiles[k[1]+1][k[2]] -= 1
    tiles[k[1]+1][k[3]+1] += 1

for i in range(2*K):
    for j in range(1,2*K):
        tiles[i][j] += tiles[i][j-1]

for i in range(1,2*K):
    for j in range(2*K):
        tiles[i][j] += tiles[i-1][j]

ans = 0
for i in range(2*K):
    for j in range(2*K):
        if tiles[i][j]+tiles[(i+K)%(2*K)][(j+K)%(2*K)]>ans:
            ans = tiles[i][j]+tiles[(i+K)%(2*K)][(j+K)%(2*K)]

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
grid = [[0]*k for i in range(k)]
black = 0
for i in range(n):
    a,b,c =input().split()
    a,b = int(a), int(b)
    f = a//k + b//k
    a %= k
    b %= k
    if (c == "W" and f%2==0) or (c == "B" and f%2==1):
        grid[a][b] += 1
    else:
        grid[a][b] -= 1
        black += 1

s = [[0]*(k+1) for i in range(k+1)]
for i in range(k):
    for j in range(k):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + grid[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        a = s[k][k] - s[i][k] - s[k][j] + 2*s[i][j] + black
        ans = max(ans, max(a, n-a))
print(ans)

Solution (Python):
n, k = map(int, input().split())
info = [list(input().split()) for i in range(n)]

cnt_b = [[0]*k for i in range(k)]
cnt_w = [[0]*k for i in range(k)]

for i in range(n):
    x, y, c = info[i]
    x, y = int(x), int(y)
    move_cnt = (x//k) + (y//k)
    if move_cnt % 2 == 0:
        if c == "B":
            cnt_b[x % k][y % k] += 1
        if c == "W":
            cnt_w[x % k][y % k] += 1
    else:
        if c == "B":
            cnt_w[x % k][y % k] += 1
        if c == "W":
            cnt_b[x % k][y % k] += 1

ruiseki_b = [[0]*(k+1) for i in range(k+1)]
ruiseki_w = [[0]*(k+1) for i in range(k+1)]
for i in range(k):
    for j in range(k):
        ruiseki_b[i+1][j+1] = ruiseki_b[i+1][j] + cnt_b[i][j]
        ruiseki_w[i+1][j+1] = ruiseki_w[i+1][j] + cnt_w[i][j]
for j in range(k):
    for i in range(k):
        ruiseki_b[i+1][j+1] += ruiseki_b[i][j+1]
        ruiseki_w[i+1][j+1] += ruiseki_w[i][j+1]
ans = 0
for i in range(k+1):
    for j in range(k+1):
        ans_b = ruiseki_b[k][k] - ruiseki_b[i][k] - ruiseki_b[k][j] + 2*ruiseki_b[i][j]
        ans_w = ruiseki_w[i][k] + ruiseki_w[k][j] - 2*ruiseki_w[i][j]
        ans = max(ans_w + ans_b, ans)
        ans_w = ruiseki_w[k][k] - ruiseki_w[i][k] - ruiseki_w[k][j] + 2*ruiseki_w[i][j]
        ans_b = ruiseki_b[i][k] + ruiseki_b[k][j] - 2*ruiseki_b[i][j]
        ans = max(ans_w + ans_b, ans)
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    
    N,K = map(int,input().split())
    BMAP = [[0]*(2*K) for j in range(2*K)]
    WMAP = [[0]*(2*K) for j in range(2*K)]
    
    for i in range(N):
        x,y,c = input().split()
        x = int(x)%(2*K)
        y = int(y)%(2*K)
        if c == "B":
            BMAP[y][x] += 1
        else:
            WMAP[y][x] += 1
    
    import copy
    Bruiseki =  copy.deepcopy(BMAP)
    Wruiseki =  copy.deepcopy(WMAP)
    
    for i in range(2*K):
        for j in range(1,2*K):
            Bruiseki[i][j] += Bruiseki[i][j-1]
            Wruiseki[i][j] += Wruiseki[i][j-1]
    
    for i in range(2*K):
        for j in range(1,2*K):
            Bruiseki[j][i] += Bruiseki[j-1][i]
            Wruiseki[j][i] += Wruiseki[j-1][i]
    
    ans = 0
    for i in range(K):
        for j in range(K):
            Bone = Bruiseki[i][j]
            Btwo = Bruiseki[i][j+K] - Bone
            Bthree = Bruiseki[i][2*K-1] - Bruiseki[i][j+K]
            Bfour = Bruiseki[i+K][j] - Bone
            Bfive = Bruiseki[i+K][j+K] - Bone - Btwo - Bfour
            Bsix = Bruiseki[i+K][2*K-1] - Bruiseki[i+K][j+K] - Bthree
            Bseven =  Bruiseki[2*K-1][j] - Bruiseki[i+K][j]
            Beight = Bruiseki[2*K-1][j+K] - Bruiseki[i+K][j+K] - Bseven
            Bnine = Bruiseki[2*K-1][2*K-1] - Bruiseki[2*K-1][j+K] - Bthree - Bsix
            
            Wone = Wruiseki[i][j]
            Wtwo = Wruiseki[i][j+K] - Wone
            Wthree = Wruiseki[i][2*K-1] - Wruiseki[i][j+K]
            Wfour = Wruiseki[i+K][j] - Wone
            Wfive = Wruiseki[i+K][j+K] - Wone - Wtwo - Wfour
            Wsix = Wruiseki[i+K][2*K-1] - Wruiseki[i+K][j+K] - Wthree
            Wseven =  Wruiseki[2*K-1][j] - Wruiseki[i+K][j]
            Weight = Wruiseki[2*K-1][j+K] - Wruiseki[i+K][j+K] - Wseven
            Wnine = Wruiseki[2*K-1][2*K-1] - Wruiseki[2*K-1][j+K] - Wthree - Wsix
            
            tmp1 = Wone+Wthree+Wfive+Wseven+Wnine + Btwo+Bfour+Bsix+Beight
            tmp2 = Bone+Bthree+Bfive+Bseven+Bnine + Wtwo+Wfour+Wsix+Weight
            
            if tmp1 > ans:
                ans = tmp1
            if tmp2 > ans:
                ans = tmp2
            
    print(ans)

    
    
main()

Solution (Python):
N, K = map(int, input().split())

dp = [[0] * (3*K+1) for _ in range(2*K+1)]
for _ in range(N) :
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W' :
        x += K
    
    m = min(x//K, y//K)
    x -= m * K
    y -= m * K
    x %= 2 * K
    y %= 2 * K
    
    dp[x][y] += 1
    if x < K and y < K :
        dp[x+K][y+K] += 1
        dp[x][y+2*K] += 1
    elif x < K and y >= K :
        dp[x+K][y-K] += 1
        dp[x+K][y+K] += 1
    elif x >= K and y < K :
        dp[x-K][y+K] += 1
        dp[x][y+2*K] += 1

for i in range(2 * K) :
    for j in range(3 * K) :
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        
ret = 0
for i in range(K-1, 2 * K) :
    for j in range(K-1, 3 * K) :
        ret = max(ret, dp[i][j] - dp[i][j-K] - dp[i-K][j] + dp[i-K][j-K])
print(ret)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, K = map(int, input().split())
black = []
white = []
for i in range(N):
    x, y, c = map(str, input().split())
    temp = 0
    dx, x = divmod(int(x), K)
    temp += dx
    dy, y = divmod(int(y), K)
    temp += dy
    color = 0 if c == 'B' else 1
    color = (color + temp) % 2
    if color == 0:
        white.append((x, y))
    else:
        black.append((x, y))

white_bit_list = [0]
black_bit_list = [0]
for _ in range(K):
    white_bit = Bit(K)
    black_bit = Bit(K)
    white_bit_list.append(white_bit)
    black_bit_list.append(black_bit)
white_y = [0] * K
black_y = [0] * K
for xy in white:
    x, y = xy
    white_y[y] += 1
    x += 1
    y += 1
    white_bit_list[x].add(y, 1)
for xy in black:
    x, y = xy
    black_y[y] += 1
    x += 1
    y += 1
    black_bit_list[x].add(y, 1)
white_y_cum = [0] * (K + 1)
black_y_cum = [0] * (K + 1)
for i in range(K):
    white_y_cum[i + 1] = white_y_cum[i] + white_y[i]
    black_y_cum[i + 1] = black_y_cum[i] + black_y[i]

ans_best = 0
for dy in range(1, K):
    ul_w = 0
    ur_b = black_y_cum[dy]
    ll_b = 0
    lr_w = white_y_cum[-1] - white_y_cum[dy]
    ans = ul_w + ur_b + ll_b + lr_w
    ans_best = max(ans_best, ans, N - ans)
    for dx in range(1, K):
        ul_w += white_bit_list[dx].sum(dy)
        ur_b -= black_bit_list[dx].sum(dy)
        ll_b += black_bit_list[dx].sum(K) - black_bit_list[dx].sum(dy)
        lr_w -= white_bit_list[dx].sum(K) - white_bit_list[dx].sum(dy)
        ans = ul_w + ur_b + ll_b + lr_w
        ans_best = max(ans_best, ans, N - ans)
l_w = 0
r_b = len(black)
ans = l_w + r_b
ans_best = max(ans_best, ans, N - ans)
for dx in range(1, K):
    l_w += white_bit_list[dx].sum(K)
    r_b -= black_bit_list[dx].sum(K)
    ans = l_w + r_b
    ans_best = max(ans_best, ans, N - ans)

print(ans_best)

Solution (Python):
n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
w=[[0]*(k+1) for _ in range(k+1)]
b=[[0]*(k+1) for _ in range(k+1)]
for i in range(n):
    if ((int(l[i][0])//k+int(l[i][1])//k)%2==0)^(l[i][2]=='W'):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        w[int(l[i][0])%k][int(l[i][1])%k]+=1

for i in range(1,k+1):
    b[0][i]+=b[0][i-1]
    b[i][0]+=b[i-1][0]
    w[0][i]+=w[0][i-1]
    w[i][0]+=w[i-1][0]
for i in range(1,k+1):
    for j in range(1,k+1):
        b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
        w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1]

ans=0
for i in range(k+1):
    for j in range(k+1):
        ans=max(ans,b[k][k]-b[i][k]-b[k][j]+2*b[i][j]+w[i][k]+w[k][j]-2*w[i][j])
        ans=max(ans,w[k][k]-w[i][k]-w[k][j]+2*w[i][j]+b[i][k]+b[k][j]-2*b[i][j])
print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(str, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return


def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return


def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            pre = (x, y, t)
            continue
        print("No")
        return
    print("Yes")
    return


def D():
    n, k = LI()
    dp = [[0] * (2 * k + 1) for i in range(2 * k + 1)]
    for _ in range(n):
        x, y, c = LS()
        x, y = int(x), int(y)
        if c == "W":
            dp[y % (2 * k) + 1][(x + k) % (2 * k) + 1] += 1
        else:
            dp[y % (2 * k) + 1][x % (2 * k) + 1] += 1
    for y in range(2 * k + 1):
        for x in range(1, 2 * k + 1):
            dp[y][x] += dp[y][x - 1]
    for y in range(1, 2 * k + 1):
        for x in range(2 * k + 1):
            dp[y][x] += dp[y - 1][x]
    
    def count(l, r, d, u):
        return dp[d][l] - dp[d][r] - dp[u][l] + dp[u][r]
    
    ans = 0
    for i in range(k):
        for j in range(k):
            tmp = count(j, j + k, i, i + k) + count(0, j, 0, i) + count(j + k, 2 * k, 0, i) + \
                 count(0, j, i + k, 2 * k) + count(j + k, 2 * k, i + k, 2 * k)
            ans = max(ans, tmp, n - tmp)
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 

n,k = [int(i) for i in readline().split()]
xyc = []


B = [[0]*(k+1) for i in range(k+1)]
W = [[0]*(k+1) for i in range(k+1)]

for _ in range(n):
    x,y,c = [i for i in readline().split()] 
    x = int(x)
    y = int(y)
    sgn = 0
    sgn += x//k
    x %= k
    sgn += y//k
    y %= k
    if sgn&1:
        if c == "W": B[x+1][y+1] += 1

        else: W[x+1][y+1] += 1

    else:
        if c == "W": W[x+1][y+1] += 1

        else: B[x+1][y+1] += 1



for i in range(k):
    for j in range(k):
        B[i+1][j+1] += B[i+1][j] + B[i][j+1] - B[i][j]
        W[i+1][j+1] += W[i+1][j] + W[i][j+1] - W[i][j]




ans = 0
for i in range(k):
    for j in range(k):
        resb1 = B[i][j] + (B[-1][-1] - B[-1][j] - B[i][-1] + B[i][j])
        resw1 = W[i][j] + (W[-1][-1] - W[-1][j] - W[i][-1] + W[i][j])
        
        resb2 = (B[i][-1] - B[i][j]) + (B[-1][j] - B[i][j])
        resw2 = (W[i][-1] - W[i][j]) + (W[-1][j] - W[i][j])
        

        ans = max(ans,resb1+resw2, resw1+resb2)


print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K = map(int, input().split())
KK = 2*K
m = [[0] * (2*KK+1) for i in range(2*KK+1)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        y += K
    x %= KK
    y %= KK
    m[y+1][x+1] += 1
    m[y+KK+1][x+KK+1] += 1
    m[y+1][x+KK+1] += 1
    m[y+KK+1][x+1] += 1
for i in range(1, 2*KK+1):
    for j in range(2*KK):
        m[i][j+1] += m[i][j]
for j in range(1, 2*KK+1):
    for i in range(2*KK):
        m[i+1][j] += m[i][j]
ans = 0
for i in range(KK):
    for j in range(KK):
        ans = max(ans, 2*m[i+K][j+K]-m[i+K][j]-m[i][j+K]+m[i][j]+m[i+KK][j+KK]-m[i+KK][j+K]-m[i+K][j+KK])
print(ans)

Solution (Python):
N,K = map(int,input().split())
XYC = [[int(x)%(2*K),int(y)%(2*K),int(c=="B")] for x,y,c in [input().split() for _ in [0]*N]]

score = [[[0]*(3*K+1) for _ in [0]*(3*K+1)] for _ in [0]*2]
for x,y,c in XYC:
    x+=1
    y+=1
    score[c][y][x] += 1
    if x<K: score[c][y][x+2*K] += 1
    if y<K: score[c][y+2*K][x] += 1
    if x<K and y<K: score[c][y+2*K][x+2*K] += 1

S = score
for c in range(2):
    for j in range(3*K):
        for i in range(3*K):
            S[c][i+1][j+1] += S[c][i][j+1]
    for i in range(3*K):
        for j in range(3*K):
            S[c][i+1][j+1] += S[c][i+1][j]

def get_sum(c,si,sj,i,j):
    i+=1
    j+=1
    return S[c][i][j] + S[c][si][sj] - S[c][i][sj] - S[c][si][j]

ans = 0
for i in range(K):
    for j in range(2*K):
        tmp = 0
        tmp += get_sum(0,i,j,i+K-1,j+K-1)
        tmp += get_sum(1,i+K,j,i+2*K-1,j+K-1)
        j = (j+K)%(2*K)
        tmp += get_sum(1,i,j,i+K-1,j+K-1)
        tmp += get_sum(0,i+K,j,i+2*K-1,j+K-1)
        ans = max(ans,tmp)
print(ans)

Solution (Python):
N, K = map(int, input().split())
B = [[0] * (2 * K) for _ in range(2 * K)]
for _ in range(N):
    x, y, c = input().split()
    if c == "B":
        B[int(x) % (2 * K)][int(y) % (2 * K)] += 1
    else:
        B[int(x) % (2 * K)][(int(y) + K) % (2 * K)] += 1

SB = [[0] * (4 * K + 1) for _ in range(4 * K + 1)]
for x in range(4 * K):
    for y in range(4 * K):
        SB[x][y] = B[x % (2 * K)][y % (2 * K)]
for x in range(4 * K):
    for y in range(4 * K):
        SB[x + 1][y] += SB[x][y]
for y in range(4 * K):
    for x in range(4 * K):
        SB[x][y + 1] += SB[x][y]

ans = 0
for x in range(2 * K):
    for y in range(2 * K):
        cand = SB[x + K][y + K] - SB[x][y + K] - SB[x + K][y] + SB[x][y]
        cand += SB[x + 2 * K][y + 2 * K] - SB[x + K][y + 2 * K] - \
            SB[x + 2 * K][y + K] + SB[x + K][y + K]
        ans = max(ans, cand)

print(ans)

Solution (Python):
import numpy as np

N, K = map(int, input().split())
B = np.zeros((2 * K, 2 * K), np.int32)

for _ in range(N):
    x, y, c = input().split()
    if c == "B":
        B[int(x) % (2 * K)][int(y) % (2 * K)] += 1
    else:
        B[int(x) % (2 * K)][(int(y) + K) % (2 * K)] += 1

SB = np.zeros((4 * K + 1, 4 * K + 1), np.int32)

SB[0*K+1:2*K+1, 0*K+1:2*K+1] = B
SB[0*K+1:2*K+1, 2*K+1:4*K+1] = B
SB[2*K+1:4*K+1, 0*K+1:2*K+1] = B
SB[2*K+1:4*K+1, 2*K+1:4*K+1] = B

np.cumsum(SB, 0, out=SB)
np.cumsum(SB, 1, out=SB)

ans = 0
cand = SB[1*K:3*K+1, 1*K:3*K+1].copy()
cand -= SB[0*K:2*K+1, 1*K:3*K+1]
cand -= SB[1*K:3*K+1, 0*K:2*K+1]
cand += SB[0*K:2*K+1, 0*K:2*K+1]
cand += SB[2*K:4*K+1, 2*K:4*K+1]
cand -= SB[1*K:3*K+1, 2*K:4*K+1]
cand -= SB[2*K:4*K+1, 1*K:3*K+1]
cand += SB[1*K:3*K+1, 1*K:3*K+1]
ans = np.max(cand)

print(ans)