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):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

n,k = map(int,readline().split())
data = [i.split() for i in readlines()]

cumsum_w = [[0] * (k+1) for _ in range(k+1)]
cumsum_b = [[0] * (k+1) for _ in range(k+1)]
for x,y,c in data:
    x = int(x)
    y = int(y)
    c = 0 if (c=='W') else 1
    c += x//k + y//k
    c %= 2
    x %= k
    y %= k
    if(c==0):
        cumsum_w[x][y] += 1
    else:
        cumsum_b[x][y] += 1

for i in range(k):
    for j in range(1,k):
        cumsum_w[i][j] += cumsum_w[i][j-1]
        cumsum_b[i][j] += cumsum_b[i][j-1]

for i in range(1,k):
    for j in range(k):
        cumsum_w[i][j] += cumsum_w[i-1][j]
        cumsum_b[i][j] += cumsum_b[i-1][j]

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

        tmp = (cumsum_b[k-1][k-1]
                - cumsum_b[x-1][k-1]
                - cumsum_b[k-1][y-1]
                + 2 * cumsum_b[x-1][y-1]
                + cumsum_w[x-1][k-1]
                + cumsum_w[k-1][y-1]
                - 2 * cumsum_w[x-1][y-1])
        ans = max(ans,tmp)

print(ans)

Solution (Python):
from pprint import *
N,K=map(int,input().split())
dpw=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
dpb=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
def getmatnum(x1,y1,x2,y2,mat):
    if (x2==0)or(y2==0):
        return 0
    else:
        if (x1==-1):
            x1=0
        if (y1==-1):
            y1=0
        return mat[y2][x2]-mat[y1][x2]-mat[y2][x1]+mat[y1][x1]








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



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

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

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

for i in range(1,2*K+1):
    for j in range(1,2*K+1):
        dpw[i][j]=dpw[i-1][j]+dpw[i][j]
ans=0
for i in range(K):
    for j in range(K):
        k=i+K
        l=j+K
        b1=getmatnum(-1,-1,i,j,dpb)+getmatnum(k,-1,2*K,j,dpb)+getmatnum(i,j,k,l,dpb)+getmatnum(-1,l,i,2*K,dpb)+getmatnum(k,l,2*K,2*K,dpb)
        w1=getmatnum(i,-1,k,j,dpw)+getmatnum(-1,j,i,l,dpw)+getmatnum(k,j,2*K,l,dpw)+getmatnum(i,l,k,2*K,dpw)
        b2=getmatnum(-1,-1,i,j,dpw)+getmatnum(k,-1,2*K,j,dpw)+getmatnum(i,j,k,l,dpw)+getmatnum(-1,l,i,2*K,dpw)+getmatnum(k,l,2*K,2*K,dpw)
        w2=getmatnum(i,-1,k,j,dpb)+getmatnum(-1,j,i,l,dpb)+getmatnum(k,j,2*K,l,dpb)+getmatnum(i,l,k,2*K,dpb)
        ans=max(ans,b1+w1,b2+w2)

        
print(ans)

Solution (Python):
class cumsum2D:
    def __init__(self, data):
        self.N = len(data)
        self.M= len(data[0])
        self.cum = [[0] * (self.M + 1) for _ in range(self.N + 1)]
        for i in range(self.N):
            for j in range(self.M):
                self.cum[i + 1][j + 1] = self.cum[i][j + 1] + self.cum[i + 1][j] - self.cum[i][j] + data[i][j]

    def get(self,x1,y1,x2,y2):
        """
        長方形の領域 [x1,x2)*[y1,y2) の範囲内にインプットされた数字の和を取る
        """
        return self.cum[x2][y2] - self.cum[x1][y2] - self.cum[x2][y1] + self.cum[x1][y1]


import sys
input = sys.stdin.readline

N, K = map(int, input().split())
B = [[0]*(2*K) for _ in range(2*K)]
W = [[0]*(2*K) for _ in range(2*K)]
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c=="B":
        B[x%(2*K)][y%(2*K)] += 1
    else:
        W[x%(2*K)][y%(2*K)] += 1
cumB, cumW = cumsum2D(B), cumsum2D(W)
res = 0
for i in range(K+1):
    for j in range(K+1):
        res = max(cumW.get(0,0,i,j) + cumW.get(i,j,i+K,j+K) + cumW.get(i+K,j+K,2*K,2*K) + cumW.get(i+K,0,2*K,j) + cumW.get(0,j+K,i,2*K) + cumB.get(i,0,i+K,j) + cumB.get(0,j,i,j+K) + cumB.get(i+K,j,2*K,j+K) + cumB.get(i,j+K,i+K,2*K), cumB.get(0,0,i,j) + cumB.get(i,j,i+K,j+K) + cumB.get(i+K,j+K,2*K,2*K) + cumB.get(i+K,0,2*K,j) + cumB.get(0,j+K,i,2*K) + cumW.get(i,0,i+K,j) + cumW.get(0,j,i,j+K) + cumW.get(i+K,j,2*K,j+K) + cumW.get(i,j+K,i+K,2*K), res)
print(res)

Solution (Python):
from numpy import*;N,K=map(int,input().split());m,L,o=zeros((3*K,3*K)),2*K,0
for _ in[0]*N:x,y,c=input().split();t=c=='W';m[int(x)%L,int(y)%L]+=2*t-1;o+=t
for _ in"00":m[L:]=m[:K];m=cumsum(m,0);m[:L]-=m[K:];m=m.T
m=m[:L,:L];print(o-int((m+roll(roll(m,K,0),K,1)).min()))

Solution (Python):








import sys,collections,math,fractions
sys.setrecursionlimit(1000000)
INF = float("inf")

N,K = map(int,sys.stdin.readline().split())
xyc = tuple(tuple(sys.stdin.readline().rstrip().split()) for _ in range(N)) 
xyc = tuple((int(x)%(2*K),int(y)%(2*K),c=="W")for x,y,c in xyc)
W = K
H = K
grid_w = [[0]*(W) for _ in range(H)]
grid_b = [[0]*(W) for _ in range(H)]

for x,y,c in xyc:
    r = (x//K+y//K)%2 
    c = c ^ r
    if c:
        grid_w[y%K][x%K] += 1
    else:
        grid_b[y%K][x%K] += 1













white =  [[0]*(W+1) for _ in range(H+1)]
black =  [[0]*(W+1) for _ in range(H+1)]
for r in range(H):
    for c in range(W):
        black[r+1][c+1] = black[r+1][c]+grid_b[r][c]
        white[r+1][c+1] = white[r+1][c]+grid_w[r][c]
for r in range(H):
    for c in range(W+1):
        black[r+1][c] += black[r][c]
        white[r+1][c] += white[r][c]


ret = 0
for r in range(K+1):
    for c in range(K+1):
        b = black[H][W]-black[H][c]-black[r][W]+2*black[r][c]
        w = white[H][c]+white[r][W]-2*white[r][c]
        
        ret = max(ret,b+w)
        b = black[H][c]+black[r][W]-2*black[r][c]
        w = white[H][W]-white[H][c]-white[r][W]+2*white[r][c]
        
        ret = max(ret,b+w)

print(ret)

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

Bcnt = [[0 for j in range(K+1)] for i in range(K+1)]
Wcnt = [[0 for j in range(K+1)] for i in range(K+1)]

for i in range(N):
    x,y,c = input().split()
    x,y = int(x),int(y)
    if ((x-x%K)/K + (y-y%K)/K)%2:
        if c == 'W':
            Bcnt[x%K+1][y%K+1] += 1
        else:
            Wcnt[x%K+1][y%K+1] += 1
    else:
        if c == 'W':
            Wcnt[x%K+1][y%K+1] += 1
        else:
            Bcnt[x%K+1][y%K+1] += 1

for i in range(K):
    for j in range(K):
        Bcnt[i+1][j+1] += Bcnt[i+1][j] + Bcnt[i][j+1] - Bcnt[i][j]
        Wcnt[i+1][j+1] += Wcnt[i+1][j] + Wcnt[i][j+1] - Wcnt[i][j]

ans = 0
Bs = Bcnt[K][K]
Ws = Wcnt[K][K]

for i in range(K+1):
    for j in range(K+1):
        B = Bcnt[K][K] - Bcnt[K][j] - Bcnt[i][K] + 2*Bcnt[i][j]
        W = Wcnt[K][K] - Wcnt[K][j] - Wcnt[i][K] + 2*Wcnt[i][j]
        ans = max(ans, B+Ws-W, W+Bs-B)

print(ans)

Solution (Python):
N,K=map(int,input().split())
table=[[0]*K for i in range(K)]
C=0
for i in range(N):
    x,y,z=input().split()
    x = int(x)
    y=int(y)
    if z=='B':
        y +=K
    x %=(2*K)
    y %=(2*K)
    t = (x//K +y//K)%2
    x%= K
    y%=K
    if t:
        table[y][x]-=1
    else:
        table[y][x]+=1
        C+=1
B=N-C

pr=[[0]*(K+1) for i in range(K)]
for i in range(K):
    for j in range(K):
        pr[j][i+1]=pr[j][i]+table[j][i]

pr2=[[0]*(K+1) for i in range(K+1)]
for j in range(K):
    for i in range(K):
        pr2[j+1][i+1]=pr2[j][i+1]+pr[j][i+1]

ans = 0
for i in range(K+1):
    for j in range(K+1):
        
        s =pr2[i][K] +pr2[K][j]-2*pr2[i][j]
        
        
        
        ans = max(ans,C-s,B+s)
print(ans)

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

amat_white,amat_black=[],[]
for i in range(2*K):
  amat_white.append([0]*(2*K))
  amat_black.append([0]*(2*K))

smat_white,smat_black=[],[]
for i in range(2*K+1):  
  smat_white.append([0]*(2*K+1))
  smat_black.append([0]*(2*K+1))

num_white,num_black=0,0
for i in range(N):
  x,y,c=input().split()  
  xx=int(x)%(2*K)
  yy=int(y)%(2*K)
  
  if xx<K and yy<K:
    if c=="W":
      amat_white[xx][yy]+=1
      amat_white[xx+K][yy+K]+=1
      num_white+=1
    else:
      amat_black[xx][yy]+=1
      amat_black[xx+K][yy+K]+=1
      num_black+=1
  elif xx>=K and yy>=K:
    if c=="W":
      amat_white[xx-K][yy-K]+=1
      amat_white[xx][yy]+=1
      num_white+=1
    else:
      amat_black[xx-K][yy-K]+=1
      amat_black[xx][yy]+=1
      num_black+=1
  elif xx<K and yy>=K:
    if c=="W":
      amat_black[xx][yy-K]+=1
      amat_black[xx+K][yy]+=1
      num_black+=1
    else:
      amat_white[xx][yy-K]+=1
      amat_white[xx+K][yy]+=1
      num_white+=1
  elif xx>=K and yy<K:
    if c=="W":
      amat_black[xx-K][yy]+=1
      amat_black[xx][yy+K]+=1
      num_black+=1
    else:
      amat_white[xx-K][yy]+=1
      amat_white[xx][yy+K]+=1
      num_white+=1
  else:
    None



for i in range(1,2*K+1):
  for j in range(1,2*K+1):
    smat_white[i][j]=amat_white[i-1][j-1]+smat_white[i][j-1]+smat_white[i-1][j]-smat_white[i-1][j-1]
    smat_black[i][j]=amat_black[i-1][j-1]+smat_black[i][j-1]+smat_black[i-1][j]-smat_black[i-1][j-1]



max_answer=0

for i in range(K):
  for j in range(K):
    answer_white=smat_white[i+K][j+K]-smat_white[i][j+K]-smat_white[i+K][j]+smat_white[i][j]
    answer_black=num_black-(smat_black[i+K][j+K]-smat_black[i][j+K]-smat_black[i+K][j]+smat_black[i][j])
    max_answer=max(max_answer,(answer_white+answer_black))
    

for i in range(K):
  for j in range(K):
    answer_white=num_white-(smat_white[i+K][j+K]-smat_white[i][j+K]-smat_white[i+K][j]+smat_white[i][j])
    answer_black=smat_black[i+K][j+K]-smat_black[i][j+K]-smat_black[i+K][j]+smat_black[i][j]
    max_answer=max(max_answer,(answer_white+answer_black))
    
    
print(max_answer)

Solution (Python):
import numpy as np
n,k=map(int,input().split())
m=np.zeros((3*k,3*k),dtype=int)
l=2*k
o=0
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%l,int(y)%l
  t=c=='W'
  m[x,y]+=1-2*t
  o+=t
for _ in range(2):
  m[l:]=m[:k]
  m=np.cumsum(m,axis=0)
  m[:l]=m[k:]-m[:l]
  m=m.T
m=m[:l,:l]
print(o+(m+np.roll(np.roll(m,k,axis=0),k,axis=1)).max())

Solution (Python):
N, K = map(int, input().split())
B = [[0]*(2*K+1) for  _ in range(2*K+1)]
B2 = [[0]*(2*K+1) for  _ in range(2*K+1)]
for _ in range(N):
    a, b, c = input().strip().split()
    a, b, c = int(a), int(b), 1 if c == 'B' else 0
    x, y = (a+K*c)%(2*K), b%(2*K)
    if x > K-1 and y > K-1:
        x, y = x-K, y-K
    if x < K and y > K-1:
        x, y = x+K, y-K
    B[x+1][y+1] += 1
    B2[(x+K)%(2*K)+1][y+1] += 1
R = [[0]*(2*K+1) for  _ in range(2*K+1)]
R2 = [[0]*(2*K+1) for  _ in range(2*K+1)]
for i in range(1, 2*K+1):
    for j in range(1, 2*K+1):
        R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + B[i][j]
        R2[i][j] = R2[i-1][j] + R2[i][j-1] - R2[i-1][j-1] + B2[i][j]
r = 0
for i in range(K):
    for j in range(K):
        t1 = R[2*K][j] + R[i+K][K] - R[i][K] - 2*R[i+K][j] + 2*R[i][j]
        r = max(r, t1)
        t1 = R2[2*K][j] + R2[i+K][K] - R2[i][K] - 2*R2[i+K][j] + 2*R2[i][j]
        r = max(r, t1)
print(r)

Solution (Python):
def f(i, j):
    i1, j1 = i, j
    if i1 > 2*K:
        return 0
    if j1 > 2*K:
        return 0
    i2, j2 = min(i+K, 2*K), min(j+K, 2*K)
    if i < 0:
        if j < 0:
            r = R[i2][j2]
        else:
            r = R[i2][j2] - R[i2][j1]
    elif j<0:
        r = R[i2][j2] - R[i1][j2]
    else:

        r = R[i2][j2] - R[i1][j2] - R[i2][j1] + R[i1][j1]
    return r

N, K = map(int, input().split())
B = [[0]*(2*K+1) for  _ in range(2*K+1)]
for _ in range(N):
    a, b, c = input().strip().split()
    a, b, c = int(a), int(b), 1 if c == 'W' else 0
    B[(a+K*c)%(2*K)+1][b%(2*K)+1] += 1
R = [[0]*(2*K+1) for  _ in range(2*K+1)]
for i in range(1, 2*K+1):
    for j in range(1, 2*K+1):
        R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + B[i][j]
r = 0
for i in range(K):
    for j in range(K):
        t = f(i,j)+f(i-K, j-K)+f(i+K, j+K)+f(i-K, j+K)+f(i+K, j-K)


        r = max(r, t)

for i in range(K):
    for j in range(K):
        i += K
        t = f(i,j)+f(i-K, j-K)+f(i-K, j+K)+f(i-2*K, j)
        r = max(r, t)
for i in range(K):
    for j in range(K):
        j += K
        t = f(i,j)+f(i-K, j-K)+f(i+K, j-K)+f(i, j-2*K)
        r = max(r, t)
print(r)

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


def main():
    N, K = map(int, input().split())
    black = defaultdict(int)
    white = defaultdict(int)
    for _ in range(N):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        if c == 'B':
            x_, y_ = x % (2*K), y % (2*K)
            if x_ < K and y_ < K:
                black[x_ * K + y_] += 1
            elif x_ >= K and y_ < K:
                white[(x_ - K) *K +y_] += 1
            elif x_ < K and y_ >= K:
                white[x_ * K + y_ - K] += 1
            else:
                black[(x_ - K)*K + y_ - K] += 1
        else:
            x_, y_ = x % (2 * K), y % (2 * K)
            if x_ < K and y_ < K:
                white[x_*K + y_] += 1
            elif x_ >= K and y_ < K:
                black[(x_ - K)*K + y_] += 1
            elif x_ < K and y_ >= K:
                black[x_*K+ y_ - K] += 1
            else:
                white[(x_ - K)*K + y_ - K] += 1

    cs_b = [[0] * (K+1) for _ in range(K+1)]
    cs_w = [[0] * (K+1) for _ in range(K+1)]
    for i in range(K):
        for j in range(K):
            cs_b[i+1][j+1] = cs_b[i+1][j] + cs_b[i][j+1] - cs_b[i][j] + black[i*K+j]
            cs_w[i + 1][j + 1] = cs_w[i + 1][j] + cs_w[i][j + 1] - cs_w[i][j] + white[i*K+j]

    ans = 0
    for i in range(K):
        for j in range(K):
            ans_b = cs_b[i][j] + cs_b[-1][-1] - cs_b[-1][j] - cs_b[i][-1] + cs_b[i][j]
            ans_w = cs_w[i][-1] - cs_w[i][j] + cs_w[-1][j] - cs_w[i][j]
            ans_w2 = cs_w[i][j] + cs_w[-1][-1] - cs_w[-1][j] - cs_w[i][-1] + cs_w[i][j]
            ans_b2 = cs_b[i][-1] - cs_b[i][j] + cs_b[-1][j] - cs_b[i][j]
            ans = max(ans, ans_b + ans_w, ans_b2 + ans_w2)

    print(ans)
    '''
    print(cs_b)
    print(cs_w)
    print(black)
    print(white)
    '''


if __name__ == '__main__':
    main()

Solution (Python):
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]
b_board_2 = [ [ 0 for i in range(k)] for j in range(k) ]
w_board_2 = [ [ 0 for i in range(k)] for j in range(k) ]
b_board_3 = [ [ 0 for i in range(k+1)] for j in range(k+1) ]
w_board_3 = [ [ 0 for i in range(k+1)] for j in range(k+1) ]

for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[int(w)%k][int(h)%k] += 1
    else:
        w_board[int(w)%k][int(h)%k] += 1
    

for i in range(k):
    b, w = 0, 0
    for j in range(k):
        b += b_board[i][j]
        b_board_2[i][j] = b
        w += w_board[i][j]
        w_board_2[i][j] = w

for i in range(k):
    b, w = 0, 0
    for j in range(k):
        b += b_board_2[j][i]
        b_board_3[j+1][i+1] = b
        w += w_board_2[j][i]
        w_board_3[j+1][i+1] = w

total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k2 = k * 2
    t = [[0] * k2 for _ in range(k2)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        x = (x + k) % k2
        y = (y + k) % k2
        t[x][y] += 1
    
    
    for i in range(k2):
        ti = t[i]
        for j in range(1, k2):
            ti[j] += ti[j - 1]
    for j in range(k2):
        for i in range(1, k2):
            t[i][j] += t[i - 1][j]
    
    ans = 0
    for i in range(k - 1, k2):
        for j in range(k - 1, k2):
            cur = t[i][j]
            if i - k >= 0: cur -= t[i - k][j]
            if j - k >= 0: cur -= t[i][j - k]
            if i >= k and j >= k: cur += t[i - k][j - k]
            ans=max(ans,cur,n-cur)
    print(ans)

main()

Solution (Python):
n,k=map(int,input().split())
xyc=[list(input().split()) for i in range(n)]
data=[[[] for i in range(k)] for j in range(k)]
B=[[0]*k for i in range(k)]
W=[[0]*k for i in range(k)]
for u in xyc:
    x=int(u[0])
    y=int(u[1])
    c=u[2]
    a,b=x%k,y%k
    if (x//k+y//k)%2==0:
        if c=="B":
            B[a][b]+=1
        else:
            W[a][b]+=1
    else:
        if c=="B":
            W[a][b]+=1
        else:
            B[a][b]+=1
lst=[[0]*k for i in range(k)]
li=[[0]*k for i in range(k)]
for i in range(k):
    lst[i][0]=B[i][0]
    li[i][0]=W[i][0]
    for j in range(1,k):
        lst[i][j]=lst[i][j-1]+B[i][j]
        li[i][j]=li[i][j-1]+W[i][j]
for i in range(1,k):
    for j in range(k):
        lst[i][j]+=lst[i-1][j]
        li[i][j]+=li[i-1][j]
det=[[0]*k for i in range(k)]
den=[[0]*k for i in range(k)]
for i in range(k):
    i=k-1-i
    det[i][k-1]=B[i][k-1]
    den[i][k-1]=W[i][k-1]
    for j in range(1,k):
        j=k-j-1
        det[i][j]=det[i][j+1]+B[i][j]
        den[i][j]=den[i][j+1]+W[i][j]
for i in range(1,k):
    i=k-i-1
    for j in range(k):
        j=k-j-1
        det[i][j]+=det[i+1][j]
        den[i][j]+=den[i+1][j]
bcount=lst[k-1][k-1]
wcount=li[k-1][k-1]
ans=max(bcount,wcount)
for i in range(k-1):
    for j in range(k-1):
        o=lst[i][j]+det[i+1][j+1]
        p=li[i][j]+den[i+1][j+1]
        ans=max(ans,o+wcount-p,bcount-o+p)
for i in range(k-1):
    o=lst[k-1][i]
    O=lst[i][k-1]
    p=li[k-1][i]
    P=li[i][k-1]
    ans=max(ans,bcount-o+p,wcount-p+o)
    ans=max(ans,bcount-O+P,wcount-P+O)
print(ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    white = [[0] * K for _ in range(2*K)]
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x) % (2*K), int(y) % (2*K)
        if y >= K:
            y -= K
            x = (x-K) % (2*K)
        if c == "W":
            white[x][y] += 1
        else:
            white[(x+K) % (2*K)][y] += 1
    ysum = [[0] * (2*K) for _ in range(2*K)]
    for i in range(2*K):
        ysum[i][0] = sum(white[i][:K])
        for j in range(1, K):
            ysum[i][j] = ysum[i][j-1] - white[i][j-1]
        for j in range(K+1, 2*K):
            ysum[i][j] = ysum[i][j-1] + white[i][(j+K-1) % (2*K)]
    csum = [[0] * (2*K) for _ in range(2*K)]
    ans = 0
    for i in range(2*K):
        csum[0][i] = sum([ysum[x][i] for x in range(K)]) + \
            sum([ysum[x][(i+K) % (2*K)] for x in range(K, 2*K)])
        for j in range(1, 2*K):
            csum[j][i] = csum[j-1][i] \
                + ysum[(j+K-1) % (2*K)][i] - ysum[(j+K-1) % (2*K)][(i+K) % (2*K)]\
                - ysum[j-1][i] + ysum[j-1][(i+K) % (2*K)]
    for i in range(2*K):
        for j in range(K):
            ans = max(ans, csum[i][j])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
temp=input().split(" ")
n=int(temp[0])
k=int(temp[1])
k2=2*k
tileb=[[0 for i in range(k2*2)] for j in range(k2*2)]
for i in range(n):
    temp=input().split(" ")
    x=int(temp[0])
    y=int(temp[1])
    c=temp[2]
    tempx=x%(k2)
    if c=='B':  
        tempy=y%(k2)
        
    elif c=='W':  
        tempy=(y+k)%(k2)

    tileb[tempy][tempx]+=1
    tileb[tempy+k2][tempx]+=1
    tileb[tempy][tempx+k2]+=1
    tileb[tempy+k2][tempx+k2]+=1
        
ans=0
for y in range(0,k2*2):
    for x in range(1,k2*2):
        tileb[y][x]+=tileb[y][x-1]

for x in range(0,k2*2):
    for y in range(1,k2*2):
        tileb[y][x]+=tileb[y-1][x]

def nijiruisekiwa(x,y,k): 
    global tileb
    if x!=0 and y!=0:
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]-tileb[y-1][x+k-1]+tileb[y-1][x-1]
    
    if x==0 and y==0:     
        return tileb[y+k-1][x+k-1]
    if y==0:     
        return tileb[y+k-1][x+k-1]-tileb[y+k-1][x-1]
    if x==0:     
        return tileb[y+k-1][x+k-1]-tileb[y-1][x+k-1]
    
for x in range(0,k2):
    for y in range(0,k2):
        temp=0
        a=nijiruisekiwa(x,y,k)
        b=nijiruisekiwa(x+k,y+k,k)

        temp=a+b
      

        if temp>ans:
            
            
            
            ans=temp
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        """
        self.mat[row+1][col+1] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]


def solve():
    N, K = map(int, input().split())
    K2 = 2*K

    ACC = ACC_2D(K2, K2)

    
    
    for _ in range(N):
        x, y, s = input().split()
        
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    
    ACC.build()

    ans = 0
    
    
    
    for row in range(K + 1):
        for col in range(K + 1):
            
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(K2, col+K, row+K, col)
            d += ACC.get_val(row+K, K2, row, col+K)
            ans = max(ans, d, N-d)
    print(ans)


solve()

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        mat[row][col]+=val
        """
        self.mat[row+1][col+1] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]

    def __str__(self):
        return "\n".join(map(str, [v for v in self.mat]))


def solve():
    N, K = map(int, input().split())
    K2 = 2*K

    ACC = ACC_2D(K2, K2)

    
    
    for _ in range(N):
        x, y, s = input().split()
        
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    
    ACC.build()

    ans = 0
    for row in range(K + 1):
        for col in range(K + 1):
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(K2, col+K, row+K, col)
            d += ACC.get_val(row+K, K2, row, col+K)
            ans = max(ans, d, N-d)
    print(ans)


solve()

Solution (Python):
import numpy as np

N , K = map(int, input().split())

m = np.zeros((3*K, 3*K), dtype=int)
L = 2 * K
o = 0

for _ in range(N):
	x, y, c = input().split()
	x , y = int(x) % L, int(y) % L
	t = c=='W'
	m[x, y] += 1 - 2 * t
	o += t

for _ in range(2):
	m[L:] = m[:K]
	m = np.cumsum(m,axis=0)
	m[:L] = m[K:] - m[:L]
	m = m.T

m = m[:L,:L]
print(o + (m + np.roll(np.roll(m, K, axis=0), K, axis=1)).max())

Solution (Python):
N, K = map(int, input().split())
T = [[0] * (2 * K + 5) for i in range(2 * K + 5)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    T[x % (2 * K) + 1][y % (2 * K) + 1] += 1

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


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


num = 0
for i in range(K + 1):
    for j in range(K + 1):
        d = T[i][j]
        d += T[i + K][j + K] - T[i][j + K] - T[i + K][j] + T[i][j]
        d += T[2 * K][j] - T[i + K][j]
        d += T[i][2 * K] - T[i][j + K]
        d += T[2 * K][2 * K] - T[2 * K][j + K] - T[i + K][2 * K] + T[i + K][j + K]
        num = max(num, d)
        num = max(num, N - d)

print(num)

Solution (Python):
from numpy import*;N,K=map(int,input().split());m,L,o=zeros((3*K,3*K)),2*K,0
for _ in[0]*N:x,y,c=input().split();t=c=='W';m[int(x)%L,int(y)%L]+=2*t-1;o+=t
for _ in"00":m[L:]=m[:K];m=cumsum(m,0);m[:L]-=m[K:];m=m.T
m=m[:L,:L];print(o-int((m+roll(roll(m,K,0),K,1)).min()))

Solution (Python):
from itertools import accumulate
from operator import add
 
N, K = map(int, input().split())
K2 = 2 * K
 

Gss = [[0] * K2 for i in range(K2)]
 
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
 
    
    if c == 'W':
        x -= K
    x, y = x % K2, y % K2
 
    if y >= K:
        x, y = (x - K) % K2, y - K
 
    
    
    Gss[x][y] += 1
    Gss[x][y - K] += -1
    if x != K:
        Gss[x - K][y - K] += 1
        Gss[x - K][y] += -1
    if x > K:
        Gss[0][y] += 1
        Gss[0][y - K] += -1
 

Gss = [accumulate(Gs) for Gs in Gss]
Gss = [accumulate(Gs) for Gs in zip(*Gss)]
Gss = list(map(list, zip(*Gss))) 
 

Gss = [map(add, Gss[i][:K], Gss[i - K][K:]) for i in range(K2)]
 

print(max(map(max, Gss)))

Solution (Python):
n, k = map(int, input().split())
white = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]

for _ in range(n):
	x, y, c = input().split()
	x, y = (int(x) - 1) % (2*k), (int(y) - 1) % (2*k)
	if (c == "B"):
		x = (x-k) % (2*k)

	if not ((x<k) ^ (y<k)):
		if y >= k:
			x, y = x-k, y-k
		white[0][0] += 1
		white[x][0] += -1
		white[x+k][0] += -1
		white[2*k][0] += 1
		white[0][y] += -1
		white[x][y] += 2
		white[x+k][y] += -2
		white[2*k][y] += 1
		white[0][y+k] += 1
		white[x][y+k] += -2
		white[x+k][y+k] += 2
		white[2*k][y+k] += -1
		white[0][2*k] += -1
		white[x][2*k] += 1
		white[x+k][2*k] += -1
		white[2*k][2*k] += 1

	else:
		if y >= k:
			x, y = x+k, y-k
		white[x-k][0] += 1
		white[x][0] += -1
		white[0][y] += 1
		white[x-k][y] += -2
		white[x][y] += 2
		white[2*k][y] += -1
		white[0][y+k] += -1
		white[x-k][y+k] += 2
		white[x][y+k] += -2
		white[2*k][y+k] += 1
		white[x-k][2*k] += -1
		white[x][2*k] += 1



for i in range(2*k+1):
	for j in range(2*k):
		white[i][j+1] += white[i][j]

for j in range(2*k+1):
	for i in range(2*k):
		white[i+1][j] += white[i][j]



ans = 0
for i in range(2*k):
	for j in range(2*k):
		ans = max(ans, white[i][j])

print(ans)

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

MeetDemand =[[0 for y in range(dK+1)] for x in range(K+1)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = (int(y)+K if c=="W" else int(y)) % dK
    if K <= x:
        if 0 <= y < K:
            x -= K
            y += K
        else:
            x %= K
            y %= K
    if 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    else:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]

Ans = max(MeetDemand[0][:dK])
for i in range(1, K):
    Ans = max(Ans, max(MeetDemand[i][:dK]))
print(Ans)

Solution (Python):
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
for i in range(N):
    a,b,c=map(str,input().split())
    a=int(a)
    b=int(b)
    if c=="W":
        b+=K
    x[i]=a%(2*K)
    y[i]=b%(2*K)
board=[[0 for i in range(2*K+1)] for i in range(2*K+1)]
for i in range(N):
    if x[i]>=K and y[i]>=K:
        x[i]-=K
        y[i]-=K
    if x[i]<K and y[i]>=K:
        x[i]+=K
        y[i]-=K
    if x[i]>=K and y[i]<K:
        board[0][y[i]+1]+=1
        board[0][y[i]+K+1]-=1
        board[x[i]-K+1][y[i]+1]-=2
        board[x[i]-K+1][y[i]+K+1]+=2
        board[x[i]-K+1][0]+=1
        board[x[i]+1][0]-=1
        board[x[i]+1][y[i]+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
    if x[i]<K and y[i]<K:
        board[x[i]+1][y[i]+1]+=2
        board[x[i]+K+1][y[i]+K+1]+=2
        board[x[i]+1][y[i]+K+1]-=2
        board[x[i]+K+1][y[i]+1]-=2
        board[0][0]+=1
        board[x[i]+1][0]-=1
        board[0][y[i]+1]-=1
        board[x[i]+K+1][0]+=1
        board[0][y[i]+K+1]+=1
tmp=[[0 for i in range(2*K)] for i in range(2*K)]
bs=[[0 for i in range(2*K)] for i in range(2*K)]
for i in range(2*K):
    for j in range(2*K):
        if i==0:
            tmp[i][j]=board[i][j]
        else:
            tmp[i][j]=board[i][j]+tmp[i-1][j]
for i in range(2*K):
    for j in range(2*K):
        if j==0:
            bs[i][j]=tmp[i][j]
        else:
            bs[i][j]=tmp[i][j]+bs[i][j-1]
ans=bs[0][0]
for i in range(2*K):
    for j in range(2*K):
        if bs[i][j]>ans:
            ans=bs[i][j]
print(ans)