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):
n,k=map(int,input().split())
ans=[[0]*(3*k+10) for i in range(4*k+10)]
for i in range(n):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    a=x//k%2
    b=x%k
    d=y//k%2
    e=y%k
    x=b+a*k
    y=e+d*k
    if (a+d)%2==0:
        if c=="B":

            x=k-b
            y=k-e

        else:
            x=2*k-b
            y=k-e
    else:
        if c == "W":
            x = k - b
            y = k - e

        else:
            x = 2 * k - b
            y = k - e

    ans[x][y]+=1
    ans[x][y+k]-=1
    ans[x+k][y]-=1
    ans[x+k][y+k]+=1


for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i][j+1]=ans[i][j]+ans[i][j+1]
for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i+1][j]=ans[i][j]+ans[i+1][j]
anser=0

for x in range(k,2*k):
    for y in range(k,2*k):
        p=ans[x][y]+ans[x-k][y-k]+ans[x-k][y+k]+ans[x+k][y+k]+ans[x+k][y-k]
        anser=max(anser,p)
for x in range(2*k,3*k):
    for y in range(k,2*k):
        p = ans[x][y] + ans[x - k][y - k] + ans[x - k][y + k] + ans[x + k][y + k] + ans[x + k][y - k]+ans[x-2*k][y]
        anser = max(anser, p)
print(anser)

Solution (Python):
n,k=map(int,input().split())
ans=[[0]*(3*k+10) for i in range(4*k+10)]
for i in range(n):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    a=x//k%2
    b=x%k
    d=y//k%2
    e=y%k
    x=b+a*k
    y=e+d*k
    if (a+d)%2==0:
        if c=="B":

            x=k-b
            y=k-e

        else:
            x=2*k-b
            y=k-e
    else:
        if c == "W":
            x = k - b
            y = k - e

        else:
            x = 2 * k - b
            y = k - e

    ans[x][y]+=1
    ans[x][y+k]-=1
    ans[x+k][y]-=1
    ans[x+k][y+k]+=1


for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i][j+1]=ans[i][j]+ans[i][j+1]
for i in range(4*k+9):
    for j in range(3*k+9):
        ans[i+1][j]=ans[i][j]+ans[i+1][j]
anser=0

for x in range(k,2*k):
    for y in range(k,2*k):
        p=ans[x][y]+ans[x-k][y-k]+ans[x-k][y+k]+ans[x+k][y+k]+ans[x+k][y-k]+ans[x+2*k][y]
        anser=max(anser,p)
for x in range(2*k,3*k):
    for y in range(k,2*k):
        p = ans[x][y] + ans[x - k][y - k] + ans[x - k][y + k] + ans[x + k][y + k] + ans[x + k][y - k]+ans[x-2*k][y]
        anser = max(anser, p)
print(anser)

Solution (Python):
n,k = map(int, input().split())

ok = [ [0]*k for _ in range(k) ]
ng = [ [0]*k for _ in range(k) ]

ok_cnt = 0
ng_cnt = 0
for _ in range(n):
    x,y,c = map(str, input().split())
    x = int(x)%(k*2)
    y = int(y)%(k*2)
    if (x < k and y < k and c=='W') or (x >= k and y >= k and c=='W') or (x < k and y>= k and c =='B') or (x >= k and y < k and c =='B'):
        ok[x%k][y%k] += 1
        ok_cnt += 1
    else:
        ng[x%k][y%k] += 1
        ng_cnt += 1

ok_csums = [ [0]*(k+1) for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        ok_csums[i+1][j+1] = ok_csums[i+1][j] + ok_csums[i][j+1] - ok_csums[i][j] + ok[i][j]

ng_csums = [ [0]*(k+1) for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        ng_csums[i+1][j+1] = ng_csums[i+1][j] + ng_csums[i][j+1] - ng_csums[i][j] + ng[i][j]

    
ans = max(ok_cnt, ng_cnt)


for i in range(0,k+1):
    for j in range(0,k+1):
        ok_sum = ok_csums[i][j]
        ok_sum += (ok_csums[k][k] - ok_csums[i][k]- ok_csums[k][j] + ok_csums[i][j])
        ng_sum = ng_csums[i][k] - ng_csums[i][j]
        ng_sum += (ng_csums[k][j] - ng_csums[i][j])

        
        ans = max(ok_sum+ng_sum, ans)

for i in range(0,k+1):
    for j in range(0,k+1):
        ok_sum = ok_csums[i][k] - ok_csums[i][j]
        ok_sum += (ok_csums[k][j] - ok_csums[i][j])
        ng_sum = ng_csums[i][j]
        ng_sum += (ng_csums[k][k] - ng_csums[i][k]- ng_csums[k][j] + ng_csums[i][j])
        
        
        ans = max(ok_sum+ng_sum, ans)
































print(ans)

Solution (Python):








import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]

white_all = 0
black_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
    black_all += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]

cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
  
for i in range(1, K + 1):
  for j in range(1, K + 1):
    
    
    
    
    
    
    
    
    
    
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
        
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)
      if x1 > x2 or y1 > y2:
        continue
        
      
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      
    
    point = max(black_cnt + (white_all - white_cnt),white_cnt + (black_all - black_cnt))
    if ans < point:
      ans = point
    
print(ans)

Solution (Python):








import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]

white_all = 0
black_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
    black_all += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]

cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0
  
for i in range(1, K + 1):
  for j in range(1, K + 1):
    
    
    
    
    
    
    
    
    
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1
        
      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)
      if x1 > x2 or y1 > y2:
        continue
        
      
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      
    
    point = max(black_cnt + (white_all - white_cnt),white_cnt + (black_all - black_cnt))
    if ans < point:
      ans = point
    
print(ans)

Solution (Python):






import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
white = [[0] * (2 * K + 1) for i in range(2 * K + 1)]
black = [[0] * (2 * K + 1) for i in range(2 * K + 1)]

white_all = 0
black_all = 0
for i in range(N):
  x,y,c = readline().split()
  x,y = int(x) % (2 * K),int(y) % (2 * K)
  if c == "W":
    white[x + 1][y + 1] += 1
    white_all += 1
  else:
    black[x + 1][y + 1] += 1
    black_all += 1
  
for i in range(1, len(white)):
  for j in range(1, len(white[i])):
    white[i][j] += white[i][j - 1]
    
for j in range(1, len(white)):
  for i in range(1, len(white[j])):
    white[i][j] += white[i - 1][j]

for i in range(1, len(black)):
  for j in range(1, len(black[i])):
    black[i][j] += black[i][j - 1]
    
for j in range(1, len(black)):
  for i in range(1, len(black[j])):
    black[i][j] += black[i - 1][j]



cases = ((0,0),(K,K),(-K,-K),(K,-K),(-K,K))
ans = 0





  
for i in range(1, K + 1):
  for j in range(1, K + 1):



    
    
    
    
    
    
    
    
    
    black_cnt = 0
    white_cnt = 0
    for c in cases:
      x1 = i + c[0]
      y1 = j + c[1]
      x2 = x1 + K - 1
      y2 = y1 + K - 1


        




      x1 = max(1, x1)
      y1 = max(1, y1)
      x2 = min(2 * K, x2)
      y2 = min(2 * K, y2)


      if x1 > x2 or y1 > y2:
        continue
        
      
      black_cnt += black[x2][y2] - black[x2][y1 - 1] - black[x1 - 1][y2] + black[x1 - 1][y1 - 1]
      white_cnt += white[x2][y2] - white[x2][y1 - 1] - white[x1 - 1][y2] + white[x1 - 1][y1 - 1]
      

      
    point = max(black_cnt + (white_all - white_cnt),white_cnt + (black_all - black_cnt))
    if ans < point:
      ans = point
    




print(ans)

Solution (Python):
import numpy as np

N, K = map(int, input().split())
_3K = 3 * K
_2K = 2 * K
G = np.zeros((_2K, _3K), dtype='int64') 
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    
    if c == 'B':
        x = x % _2K
        y = y % _2K
    else:
        x = (x + K) % _2K
        y = y % _2K
    
    if (y >= K) and (x >= K):
        x -= K
        y -= K
    if (y >= K) and (x < K):
        x += K
        y -= K
    
    
    
    
    
    
    
    
    G[y, x] += 1
    G[y+K, x+K] += 1
    G[y+K, x] -= 1
    G[y, x+K] -= 1


G = G.cumsum(axis=1).cumsum(axis=0)

G = G[:K, :_2K] + G[K:_2K, K:_3K] + np.concatenate((G[:K, _2K:_3K], G[K:_2K, :K]), axis=1)
ans = G.max()
print(ans)

Solution (Python):
import sys
from pprint import *
N,K=map(int,input().split())
input=sys.stdin.readline
dpb=[[0 for _ in range(2*K+1)] for _ in range(2*K+1)]
def getmatnum(x1,y1,x2,y2,mat):
    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":
        dpb[(y%(2*K))+1][((x+K)%(2*K))+1]=dpb[(y%(2*K))+1][((x+K)%(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]

ans=0
for i in range(K):
    for j in range(K):
        k=i+K
        l=j+K
        b1=getmatnum(0,0,i,j,dpb)+getmatnum(k,0,2*K,j,dpb)+getmatnum(i,j,k,l,dpb)+getmatnum(0,l,i,2*K,dpb)+getmatnum(k,l,2*K,2*K,dpb)
        b2=getmatnum(i,0,k,j,dpb)+getmatnum(0,j,i,l,dpb)+getmatnum(k,j,2*K,l,dpb)+getmatnum(i,l,k,2*K,dpb)
        ans=max(ans,b1,b2)

        
print(ans)

Solution (Python):
import sys
from pprint import *
N,K=map(int,input().split())
input=sys.stdin.readline
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":
        dpb[(y%(2*K))+1][((x+K)%(2*K))+1]=dpb[(y%(2*K))+1][((x+K)%(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]

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)
        b2=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,b2)

        
print(ans)

Solution (Python):
import sys
from pprint import *
N,K=map(int,input().split())
input=sys.stdin.readline
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):
n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)

Solution (Python):
n, k = map(int, input().split())
X, Y, C = [], [], []
for _ in range(n):
  x, y, c = input().split()
  X.append(int(x)%(2*k))
  Y.append(int(y)%(2*k))
  C.append(c=="B")
G = [[0]*k for _ in range(k)]
cnt = 0
for x, y, c in zip(X, Y, C):
  if (x >= k and y < k) or (x < k and y >= k):
    x += k
    c ^= 1
  x %= k
  y %= k
  G[x][y] += (-1)**c
  cnt += c
for i in range(k):
  for j in range(k-1):
    G[i][j+1] += G[i][j]
for j in range(k):
  for i in range(k-1):
    G[i+1][j] += G[i][j]
ans = 0
for i in range(k):
  for j in range(k):
    temp = G[k-1][k-1] - G[i][k-1] - G[k-1][j] + G[i][j]*2 + cnt
    ans = max(ans, temp, n-temp)
print(ans)

Solution (Python):
def calc(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum[ry*2*k+rx]
  if lx!=0:
    ret-=acum[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum[(ly-1)*2*k+lx-1]
  return ret

n,k=map(int,input().split())
board=[0]*(4*k*k)
acum=[0]*(4*k*k)
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%(2*k),int(y)%(2*k)
  if c=='B':
    board[y*2*k+x]+=1
  if c=='W':
    y+=k
    y%=2*k
    board[y*2*k+x]+=1
for i in range(2*k):
  for j in range(2*k):
    acum[i*2*k+j]=board[i*2*k+j]
    if i!=0:
      acum[i*2*k+j]+=acum[(i-1)*2*k+j]
    if j!=0:
      acum[i*2*k+j]+=acum[i*2*k+j-1]
    if i!=0 and j!=0:
      acum[i*2*k+j]-=acum[(i-1)*2*k+j-1]
ans=0
for i in range(k):
  for j in range(k):
    tmp1=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    
    tmp1+=calc(lx,ly,rx,ry)
    
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp1+=calc(tlx,tly,trx,ttry)
    
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp1+=calc(tlx,tly,trx,ttry)
    
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp1+=calc(tlx,tly,trx,ttry)
    
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp1+=calc(tlx,tly,trx,ttry)
    tmp2=0
    
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp2+=calc(tlx,tly,trx,ttry)
    
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp2+=calc(tlx,tly,trx,ttry)
    
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp2+=calc(tlx,tly,trx,ttry)
    
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp2+=calc(tlx,tly,trx,ttry)
    ans=max(ans,tmp1,tmp2)
print(ans)

Solution (Python):
def calcb(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum1[ry*2*k+rx]
  if lx!=0:
    ret-=acum1[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum1[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum1[(ly-1)*2*k+lx-1]
  return ret

def calcw(lx,ly,rx,ry):
  if rx<0 or ry<0 or lx>rx or ly>ry:
    return 0
  ret=acum2[ry*2*k+rx]
  if lx!=0:
    ret-=acum2[ry*2*k+lx-1]
  if ly!=0:
    ret-=acum2[(ly-1)*2*k+rx]
  if lx!=0 and ly!=0:
    ret+=acum2[(ly-1)*2*k+lx-1]
  return ret

n,k=map(int,input().split())
board1=[0]*(4*k*k)
board2=[0]*(4*k*k)
acum1=[0]*(4*k*k)
acum2=[0]*(4*k*k)
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%(2*k),int(y)%(2*k)
  if c=='B':
    board1[y*2*k+x]+=1
  if c=='W':
    board2[y*2*k+x]+=1
for i in range(2*k):
  for j in range(2*k):
    acum1[i*2*k+j]=board1[i*2*k+j]
    acum2[i*2*k+j]=board2[i*2*k+j]
    if i!=0:
      acum1[i*2*k+j]+=acum1[(i-1)*2*k+j]
      acum2[i*2*k+j]+=acum2[(i-1)*2*k+j]
    if j!=0:
      acum1[i*2*k+j]+=acum1[i*2*k+j-1]
      acum2[i*2*k+j]+=acum2[i*2*k+j-1]
    if i!=0 and j!=0:
      acum1[i*2*k+j]-=acum1[(i-1)*2*k+j-1]
      acum2[i*2*k+j]-=acum2[(i-1)*2*k+j-1]
ans=0
for i in range(k):
  for j in range(k):
    tmp1=0
    tmp2=0
    lx,ly=i,j
    rx,ry=lx+k-1,ly+k-1
    
    tmp1+=calcb(lx,ly,rx,ry)
    tmp2+=calcw(lx,ly,rx,ry)
    
    tlx,tly=0,0
    trx,ttry=lx-1,ly-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    
    tlx,tly=rx+1,0
    trx,ttry=2*k-1,ly-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    
    tlx,tly=0,ry+1
    trx,ttry=lx-1,2*k-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    
    tlx,tly=rx+1,ry+1
    trx,ttry=2*k-1,2*k-1
    tmp1+=calcb(tlx,tly,trx,ttry)
    tmp2+=calcw(tlx,tly,trx,ttry)
    
    tlx,tly=lx,0
    trx,ttry=rx,ly-1
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    
    tlx,tly=0,ly
    trx,ttry=lx-1,ry
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    
    tlx,tly=rx+1,ly
    trx,ttry=2*k-1,ry
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    
    tlx,tly=lx,ry+1
    trx,ttry=rx,2*k-1
    tmp1+=calcw(tlx,tly,trx,ttry)
    tmp2+=calcb(tlx,tly,trx,ttry)
    ans=max(ans,tmp1,tmp2)
print(ans)

Solution (Python):
def main():

    n, k = map(int, input().split())

    C = [[0]*(2*k) for _ in range(2*k)]

    for i in range(n):
        x, y, c = map(str, input().split())
        x, y = int(x), int(y)
        if c == 'W':
            y += k
        C[y%(2*k)][x%(2*k)] += 1

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

    

    def count(x1, x2, y1, y2):
        return s[y2][x2]-s[y1][x2]-s[y2][x1]+s[y1][x1]

    ans = 0
    for i in range(k):
        for j in range(k):
            temp = 0
            temp += count(0, j, 0, i)
            temp += count(j, j+k, i, i+k)
            temp += count(0, j, i+k, 2*k)
            temp += count(j+k, 2*k, 0, i)
            temp += count(j+k, 2*k, i+k, 2*k)
            ans = max(ans, max(temp, n-temp))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int, input().split())

C = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x, y, c = map(str, input().split())
    x, y = int(x), int(y)
    if c == 'W':
        y += k
    C[y%(2*k)][x%(2*k)] += 1


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



def count(x1, x2, y1, y2):
    return s[y2][x2]-s[y1][x2]-s[y2][x1]+s[y1][x1]

ans = 0
for i in range(k):
    for j in range(k):
        temp = 0
        temp += count(0, j, 0, i)
        temp += count(j, j+k, i, i+k)
        temp += count(0, j, i+k, 2*k)
        temp += count(j+k, 2*k, 0, i)
        temp += count(j+k, 2*k, i+k, 2*k)
        ans = max(ans, max(temp, n-temp))
print(ans)

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

N,K = list(map(int,input().split()))
data = [list(map(str, input().split())) for _ in range(N)]
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Solution (Python):
N,K = list(map(int,input().split()))
data = [list(map(str, input().split())) for _ in range(N)]
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]





N,K = IL()
data = SLL(N)
base = 10**6

BW_data = [[0 for i in range(2*K)] for i in range(2*K)]

for x,y,c in data:
  x,y = int(x)%(2*K),int(y)%(2*K)
  if c == "B":
    BW_data[y][x] += 1
  else:
    BW_data[y][x] += base

def ACC2(l):
  H = len(l)
  W = len(l[0])
  ret = [[0]*(W+1) for i in range(H+1)]
  for i in range(H):
    for j in range(W):
      ret[i+1][j+1] = ret[i+1][j] + ret[i][j+1] - ret[i][j] + l[i][j]
  return ret

def RANGE_SUM_in_ACC(l,h1,h2,w1,w2):
  return l[h2][w2]-l[h2][w1]-l[h1][w2]+l[h1][w1]

BW_ACC = ACC2(BW_data)

BW_res = [[0 for i in range(2*K)] for i in range(K)]

for j in range(K):
  for i in range(2*K):
    if i<K:
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,j,j+K,i,i+K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,0,max(0,j),min(2*K,i+K),2*K)
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,0,max(0,i))
      BW_res[j][i] += RANGE_SUM_in_ACC(BW_ACC,min(2*K,j+K),2*K,min(2*K,i+K),2*K)
    else:
      BW_res[j][i] = BW_ACC[-1][-1]-BW_res[j][i-K]
      
ans = 0
for j in range(K):
  for i in range(2*K):
    ans = max(ans,BW_res[j][i]%base+BW_res[j][(i+K)%(2*K)]//base)
print(ans)

Solution (Python):
from numpy import *
N,K = map(int,input().split())
M = zeros((3*K,3*K),int)
L = 2*K
O = 0

for n in range(N):
  x,y,c = input().split()
  x = int(x)%L
  y = int(y)%L
  t = c=="W"
  M[x,y]+=1-2*t
  O+=t

for n in range(2):
  M[L:] = M[:K]
  M = cumsum(M,axis=0)
  M[:L] = M[K:]-M[:L]
  M = M.T
  
M = M[:L,:L]
print(O+(M+roll(roll(M,K,axis=0),K,axis=1)).max())

Solution (Python):
N, K = map(int, input().split())
import numpy as np

_2K, _4K = 2*K, 4*K
shape = (_2K,_4K) 
Grd = np.zeros(shape, dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    
    if x >= K and y >= K: x -= K; y -= K
    if x < K and y >= K: x += K; y -= K
    
    
    
    
    
    
    
    
    
    
    
    
    Grd[y, x] += 1
    Grd[y+K, x+K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
del x, y, c


Grd = Grd.cumsum(axis=1).cumsum(axis=0)

Grd = Grd[:,:_2K] +Grd[:,_2K:_4K]
Grd = Grd[:K,:] +np.concatenate((Grd[K:_2K,K:_2K],Grd[K:_2K,:K]),axis=1) 

ans = Grd.max()
print(ans)

Solution (Python):
N, K = map(int, input().split())
import numpy as np

_2K, _4K = 2*K, 4*K
shape = (_2K+1,_4K+1) 
Grd = np.zeros(shape,dtype='int64')
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'B':
        x, y = x%_2K, y%_2K
    else: 
        x, y = (x+K)%_2K, y%_2K
    
    if x >= K and y >= K: x -= K; y -= K
    if x < K and y >= K: x += K; y -= K
    
    
    
    
    
    
    
    
    
    
    
    
    Grd[y, x] += 1
    Grd[y+K, x+K] += 1
    Grd[y+K, x] += -1
    Grd[y, x+K] += -1
del x, y, c


Grd = Grd.cumsum(axis=1).cumsum(axis=0)

Grd = Grd[:,:_2K] +Grd[:,_2K:_4K]
Grd = Grd[:K,:] +np.concatenate((Grd[K:_2K,K:_2K],Grd[K:_2K,:K]),axis=1) 

ans = Grd.max()
print(ans)

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


want_white = [[0] * (K+1) for _ in range(K+1)]
want_black = [[0] * (K+1) for _ in range(K+1)]

for _ in range(N):
    x_str, y_str, c_str = input().split()
    x = int(x_str)
    y = int(y_str)
    c = 1 if c_str == 'B' else 0

    x %= 2 * K
    y %= 2 * K
    if x >= K:
        x -= K
        c ^= 1
    if y >= K:
        y -= K
        c ^= 1

    if c:
        want_black[x+1][y+1] += 1
    else:
        want_white[x+1][y+1] += 1


for i in range(K+1):
    for j in range(K):
        want_black[i][j+1] += want_black[i][j]
        want_white[i][j+1] += want_white[i][j]

for i in range(K):
    for j in range(K+1):
        want_black[i+1][j] += want_black[i][j]
        want_white[i+1][j] += want_white[i][j]


ans = 0
for h in range(K+1):
    for w in range(K+1):
        count = want_black[-1][-1] - want_black[h][-1] - want_black[-1][w] + 2 * want_black[h][w]
        count += want_white[h][-1] + want_white[-1][w] - 2 * want_white[h][w]
        ans = max(ans, count, N - count)

print(ans)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def main():
    N, K = map(int, sys.stdin.buffer.readline().split())
    XYC = sys.stdin.buffer.read().split()
    X, Y, C = np.array(XYC[::3], dtype=np.int64), np.array(XYC[1::3], dtype=np.int64), np.array(XYC[2::3])==b"B"
    solve(N, K, X, Y, C)

def solve(N, K, X, Y, C):
    M = np.zeros((K*2+1, K*4), dtype=np.int64)
    for x, y, c in zip(X, Y, C):
        if c:
            x += K
        x %= 2*K
        y %= 2*K
        if x >= K and y >= K:
            x -= K
            y -= K
        elif y >= K:
            y -= K
            x += K
        M[y, x] += 1
        M[y, (x+2*K)%(4*K)] += 1
        M[y+K, x+K] += 1
        M[y+K, (x+3*K)%(4*K)] += 1
        if y == 0:
            M[2*K, x] += 1
            M[2*K, (x+2*K)%(4*K)] += 1
    for y in range(2*K):
        for x in range(4*K):
            M[y+1, x] += M[y, x]
    for y in range(2*K+1):
        for x in range(4*K-1):
            M[y, x+1] += M[y, x]
    ans = max([M[y+K, x+K]+M[y, x]-M[y+K, x]-M[y, x+K] for y in range(K+1) for x in range(2*K+1)])
    print(ans)

numba_compile([
    [solve, "void(i8,i8,i8[:],i8[:],b1[:])"],
])

main()