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):
def main():
    n, k = map(int, input().split())
    xycs = [input().split() for _ in range(n)]
    tbl = [[0 for _ in range(k*2+1)] for _ in range(k+1)]
    
    for sx, sy, c in xycs:
        rx, ry = map(int, (sx, sy))
        mx, my = (rx-1) % (2*k), (ry-1) % (2*k)
        dx, dy = (mx + is_black(c)*k + (my<k)*k) % (2*k), my%k

        if dx < k:
            tbl[0][0] += 1
            tbl[0][dx+1] -= 1
            tbl[dy+1][0] -= 1
            tbl[dy+1][dx+1] += 2

            tbl[0][dx+1+k] += 1
            tbl[dy+1][dx+1+k] -= 2
        else:
            dx = dx % k
            tbl[0][dx+1] += 1
            tbl[dy+1][0] += 1
            tbl[dy+1][dx+1] -= 2

            tbl[0][dx+1+k] -= 1
            tbl[dy+1][dx+1+k] += 2
    for i in range(k):
        for j in range(1, 2*k):
            tbl[i][j] += tbl[i][j-1]
    for i in range(1, k):
        for j in range(0, 2*k):
            tbl[i][j] += tbl[i-1][j]
    print(max(max(t for t in ts) for ts in tbl[:k][:2*k]))

def is_black(c):
    return 1 if c=='B' else 0

main()

Solution (Python):
n,k = map(int,input().split())
dpw = [[0]*(4*k+1) for i in range(4*k+1)]
for i in range(n):
  x,y,c = map(str,input().split())
  x = int(x)
  y = int(y)
  if c == "W":
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
  else:
    y+=k
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
for i in range(1,4*k+1):
  for j in range(1,4*k+1):
    dpw[i][j] += dpw[i-1][j] + dpw[i][j-1]-dpw[i-1][j-1]
ans = 0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    tmp = 0
    tmp += dpw[k+i-1][k+j-1]+dpw[i-1][j-1]-dpw[i-1][j+k-1]-dpw[i+k-1][j-1]
    tmp += dpw[k+i-1+k][k+j-1+k]+dpw[i-1+k][j-1+k]-dpw[i-1+k][j+k-1+k]-dpw[i+k-1+k][j-1+k]
    ans = max(ans,tmp)
print(ans)

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[0,0]: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 numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K))
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o-int((m+roll(roll(m,K,axis=0),K,axis=1)).min()))

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

Solution (Python):
from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

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

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
import numpy as np

N, K = inpl()
H = np.zeros((K,K), dtype = np.int32)
for _ in range(N):
    x, y, c = input().split() 
    x = int(x)
    y = int(y)
    t = c == 'B'
    x %= 2*K
    y %= 2*K
    if x >= K:
        x -= K
        t = not t
    if y >= K:
        y -= K
        t = not t
    if t:
        H[x][y] += 1
        continue
    H[x][y] -= 1

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

checkH = H[K-1][K-1] + 2*H
for i in range(K):
            checkH[i] -= H[i][K-1]
            checkH.T[i] -= H.T[i][K-1]

Hans = (N - checkH[K-1][K-1])//2 + checkH

print(max(np.amax(Hans), N-np.amin(Hans)))

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
import numpy as np
H = np.zeros((K,K), dtype = np.int32)
for _ in range(N):
    x, y, c = input().split() 
    x = int(x)
    y = int(y)
    t = c == 'B'
    x %= 2*K
    y %= 2*K
    if x >= K:
        x -= K
        t = not t
    if y >= K:
        y -= K
        t = not t
    if t:
        H[x][y] += 1
        continue
    H[x][y] -= 1

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

checkH = H[K-1][K-1] + 2*H
for i in range(K):
            checkH[i] -= H[i][K-1]
checkH = checkH.T 
H = H.T
for i in range(K):
            checkH[i] -= H[i][K-1]
Hans = (N - checkH[K-1][K-1])//2 + checkH

print(max(np.amax(Hans), N-np.amin(Hans)))

Solution (Python):
N, K = map(int, input().split())
ss = [[0] * (4*K+2) for i in range(4*K+2)]


def query(x1, x2, y1, y2):
    return ss[x2][y2] - ss[x2][y1] - ss[x1][y2] + ss[x1][y1]


def main():
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'W':
            y += K

        x, y = x % (2*K) + 1, y % (2*K) + 1

        ss[x][y] += 1
        ss[x+2*K][y] += 1
        ss[x][y+2*K] += 1
        ss[x+2*K][y+2*K] += 1

    for i in range(4*K+2):
        for j in range(4*K+1):
            ss[i][j+1] += ss[i][j]

    for i in range(4*K+1):
        for j in range(4*K+2):
            ss[i+1][j] += ss[i][j]

    ans = 0
    for i in range(1, 2*K+1):
        for j in range(1, 2*K+1):
            ans = max(ans, query(i, i+K, j, j+K)+query(i+K, i+2*K, j+K, j+2*K))

    print(ans)


if __name__ == '__main__':
    main()

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

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

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

B = [[0] * (2 * K + 1)] + [[0] + row for row in B]
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        
        tmp = B[i - 1][j - 1]
        
        tmp += B[i - 1][2 * K] - B[i - 1][j + K - 1]
        
        tmp += B[i + K - 1][j + K - 1] - B[i - 1][j + K - 1] \
               - B[i + K - 1][j - 1] + B[i - 1][j - 1]
        
        tmp += B[2 * K][j - 1] - B[i + K - 1][j - 1]
        
        tmp += B[-1][-1] - B[i + K - 1][2 * K] - B[2 * K][j + K - 1] \
               + B[i + K - 1][j + K - 1]
        ans = max(ans, tmp, N - tmp)
print(ans)

Solution (Python):


def main():
    n, k = map(int, input().split())
    xn = []
    yn = []
    for i in range(n):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        assert c in ["W", "B"]
        if c == "W":
            y += k
        xn.append(x % (2 * k))
        yn.append(y % (2 * k))

    kibou = [[0 for x in range(2 * k + 1)] for y in range(2 * k + 1)]
    for i in range(n):
        x = xn[i]
        y = yn[i]
        squares = get_list_squares(x, y, k)
        for x1, y1, x2, y2 in squares:
            kibou[y1][x1] += 1
            kibou[y1][x2] -= 1
            kibou[y2][x1] -= 1
            kibou[y2][x2] += 1

    rui = ruiseki_2d(kibou, k)
    ma = [max(rui[y]) for y in range(2 * k)]
    print(max(ma))

def get_list_squares(x, y, k):
    
    twok = 2 * k
    assert 0 <= x < twok
    assert 0 <= y < twok
    if x >= k:
        x -= k
        y = (y + k) % (twok)
    xp = x + k
    yp = (y + k) % (twok)
    li = []
    if y < yp:
        li.append((x, y, xp, yp))
        li.append((xp, yp, twok, twok))
        if y != 0:
            li.append((xp, 0, twok, y))
        if x != 0:
            li.append((0, yp, x, twok))
        if x != 0 and  y != 0:
            li.append((0, 0, x, y))
    else:
        li.append((x, y, xp, twok))
        li.append((xp, yp, twok, y))
        if x != 0:
            li.append((0, yp, x, y))
        if y != 0:
            li.append((x, 0, xp, yp))
    return li

def ruiseki_2d(kibou, k):
    rui_1d = [[0 for x in range(2 * k)] for y in range(2 * k)]
    for y in range(k * 2):
        rui_1d[y][0] = kibou[y][0]
        for x in range(1, 2 * k):
            rui_1d[y][x] = rui_1d[y][x - 1] + kibou[y][x]

    rui_2d = [[0 for x in range(2 * k)] for y in range(2 * k)]
    for x in range(2 * k):
        rui_2d[0][x] = rui_1d[0][x]
        for y in range(1, 2 * k):
            rui_2d[y][x] = rui_2d[y - 1][x] + rui_1d[y][x]
    return rui_2d

def debug_print(arr, k):
    for y in reversed(range(2 * k)):
        print(arr[y])

main()

Solution (Python):
def cl(i1,j1,i2,j2):
  if i1>i2 or j1>j2 or i1<0 or j1<0 or i2<0 or j2<0:
    return 0
  v=l[i2][j2]
  if i1>0:
    v-=l[i1-1][j2]
  if j1>0:
    v-=l[i2][j1-1]
  if i1>0 and j1>0:
    v+=l[i1-1][j1-1]
  return v

N,K=map(int,input().split())
K2=2*K
l=[[0]*K2 for _ in range(K2)]

for i in range(N):
  xi,yi,ci=input().split()
  xi,yi=int(xi),int(yi)
  if ci=="W":yi+=K
  l[xi%K2][yi%K2]+=1

for y in range(K2):
  for x in range(1,K2):
    l[x][y]+=l[x-1][y]
for y in range(1,K2):
  for x in range(K2):
    l[x][y]+=l[x][y-1]

ans=0
for i in range(K):
  for j in range(K):
    tmp=0
    tmp+=cl(0,0,i-1,j-1)
    tmp+=cl(0,j+K,i-1,K2-1)
    tmp+=cl(i+K,j+K,K2-1,K2-1)
    tmp+=cl(i+K,0,K2-1,j-1)
    tmp+=cl(i,j,i+K-1,j+K-1)
    ans = max(ans,tmp,N-tmp)
print(ans)

Solution (Python):
def get(i1, j1, i2, j2):
  if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
    return 0
  elif i1 > 0 and j1 > 0:
    return l[i2][j2] - l[i1-1][j2] - l[i2][j1-1] + l[i1-1][j1-1]
  elif i1 <= 0 < j1:
    return l[i2][j2] - l[i2][j1-1]
  elif j1 <= 0 < i1:
    return l[i2][j2] - l[i1 - 1][j2]
  else:
    return l[i2][j2]

N, K = map(int, input().split())
K2 = 2*K
R = []
l=[[0] * K2 for _ in range(K2)]

for i in range(N):
  xi, yi, ci = input().split()
  if ci == "W":
    yi = int(yi) + K
  xi, yi = int(xi), int(yi)
  l[xi%K2][yi%K2]+=1

for y in range(K2):
  for x in range(1,K2):
    l[x][y] += l[x-1][y]
for y in range(1,K2):
  for x in range(K2):
    l[x][y] += l[x][y-1]

ans = 0
for i in range(K):
  for j in range(K):
    tmp = 0
    tmp += get(0, 0, i-1, j-1)
    tmp += get(0, j+K, i-1, K2-1)
    tmp += get(i+K, j+K, K2-1, K2-1)
    tmp += get(i+K, 0, K2-1, j-1)
    tmp += get(i, j, i+K-1, j+K-1)

    ans = max(ans, tmp, N-tmp)
print(ans)

Solution (Python):
N, K = map(int, input().split())
K2 = 2*K
R = []



for i in range(N):
    xi, yi, ci = input().split()
    if ci == "W":
        yi = int(yi) + K

    xi, yi = int(xi), int(yi)
    R.append([yi % K2, xi % K2])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  
            if j2 + 1 < self.W:  
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  
            if j2 + 1 < self.W and i2 + 1 < self.H:  
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(K2, K2)
R2D.load(R)

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i-1, j-1)  
        tmp += R2D.get(0, j+K, i-1, K2-1)  
        tmp += R2D.get(i+K, j+K, K2-1, K2-1)  
        tmp += R2D.get(i+K, 0, K2-1, j-1)  
        tmp += R2D.get(i, j, i+K-1, j+K-1)  

        ans = max(ans, tmp, N-tmp)
print(ans)

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())
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)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XYC):
    K2 = 2*K
    ans = [[0] * (K2+K2) for _j in range(K2+K2)]
    XY = list(
        map(lambda x:
            (x[0] % K2, (x[1] if x[2] == 'W' else x[1] + K) % K2), XYC
            )
    )

    for x, y in XY:
        ans[x][y] += 1
        ans[x+K][y] -= 1
        ans[x][y+K] -= 1
        ans[x+K][y+K] += 1

        ans[x+K][y+K] += 1
        ans[x+2*K][y+K] -= 1
        ans[x+K][y+2*K] -= 1
        ans[x+2*K][y+2*K] += 1

    for i in range(K2+K2):
        for j in range(1, K2+K2):
            ans[i][j] += ans[i][j-1]
    for i in range(1, K2+K2):
        for j in range(K2+K2):
            ans[i][j] += ans[i-1][j]

    ans_ = [[0] * K2 for _j in range(K2)]
    for i in range(K2+K2):
        for j in range(K2+K2):
            ans_[i % K2][j % K2] += ans[i][j]

    return max(max(r) for r in ans_)


def main():
    N, K = read_int_n()
    XYC = [read_str_n() for _ in range(N)]
    XYC = list(map(lambda x: (int(x[0]), int(x[1]), x[2]), XYC))
    print(slv(N, K, XYC))


if __name__ == '__main__':
    main()

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)

Solution (Python):
def d_checker(N, K, Q):
    
    
    mat = [[0]*(2*K+2) for _ in range(2*K+2)]
    total = [[0]*(4*K+2) for _ in range(4*K+2)]
    for x, y, c in Q:
        if c == 'W':
            y += K
        mat[(x % (2*K)) + 1][(y % (2*K)) + 1] += 1

    
    for x in range(1, 4*K+1):
        for y in range(1, 4*K+1):
            total[x][y] = total[x][y-1] + \
                mat[((x-1) % (2*K)) + 1][((y-1) % (2*K)) + 1]
    for y in range(1, 4*K+1):
        for x in range(1, 4*K+1):
            total[x][y] += total[x-1][y]

    def get(x, y):
        
        return total[x+K-1][y+K-1] + total[x-1][y-1] - total[x-1][y+K-1] - total[x+K-1][y-1]

    ans = 0
    for x in range(1, 2*K+1):
        for y in range(1, 2*K+1):
            ans = max(ans, get(x, y)+get(x+K, y+K))
    return ans

N, K = [int(i) for i in input().split()]
Q = [(int(x), int(y), c)
    for x, y, c in [input().split() for i in range(N)]]
print(d_checker(N, K, Q))

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


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def cumulative_sum_2d(a):
    h, w = len(a), len(a[0])
    for i in range(1, h):
        for j in range(w):
            a[i][j] += a[i-1][j]
    for i in range(h):
        for j in range(1, w):
            a[i][j] += a[i][j-1]

def solve(f):
    n, k = f.read_int_list()
    b = [[0] * k for _ in xrange(k)]
    w = [[0] * k for _ in xrange(k)]
    for i in xrange(n):
        x, y, c = f.read_str().split()
        x, y = int(x)%(2*k), int(y)%(2*k)
        sgn = 1 if c == 'B' else -1
        if x >= k:
            x -= k
            sgn *= -1
        if y >= k:
            y -= k
            sgn *= -1
        if sgn == 1:
            b[x][y] += 1
        else:
            w[x][y] += 1

    cumulative_sum_2d(b)
    cumulative_sum_2d(w)

    ans = 0
    for xi in xrange(k):
        for yi in xrange(k):
            res = 0
            if xi == yi == 0:
                res += b[k-1][k-1]
            elif xi == 0:
                res += b[k-1][k-1] - b[k-1][yi-1]
                res += w[k-1][yi-1]
            elif yi == 0:
                res += b[k-1][k-1] - b[xi-1][k-1]
                res += w[xi-1][k-1]
            else:
                res += b[k-1][k-1] - b[xi-1][k-1] - b[k-1][yi-1] + b[xi-1][yi-1]
                res += b[xi-1][yi-1]
                res += w[xi-1][k-1] - w[xi-1][yi-1]
                res += w[k-1][yi-1] - w[xi-1][yi-1]
            ans = max(res, ans)

    for xi in xrange(k):
        for yi in xrange(k):
            res = 0
            if xi == yi == 0:
                res += w[k-1][k-1]
            elif xi == 0:
                res += w[k-1][k-1] - w[k-1][yi-1]
                res += b[k-1][yi-1]
            elif yi == 0:
                res += w[k-1][k-1] - w[xi-1][k-1]
                res += b[xi-1][k-1]
            else:
                res += w[k-1][k-1] - w[xi-1][k-1] - w[k-1][yi-1] + w[xi-1][yi-1]
                res += w[xi-1][yi-1]
                res += b[xi-1][k-1] - b[xi-1][yi-1]
                res += b[k-1][yi-1] - b[xi-1][yi-1]
            ans = max(res, ans)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def reads():
  return [int(x) for x in input().split()]

(N, K) = reads()

L = K

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

NW = 0
for _ in range(N):
    (x, y, c) = input().split()
    (x, y) = (int(x), int(y))
    c = (x // K + y // K + int(c == "W")) & 1 
    (x, y) = (x % K, y % K)
    NW += c
    board[y][x] += 1 if c == 1 else -1 
NB = N - NW

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

for i in range(K):
    for j in range(K):
        psumr[i][j+1] = psumr[i][j] + board[i][j]

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

for i in range(K):
    for j in range(K):
        psum[i+1][j+1] = psum[i][j+1] + psumr[i][j+1]

result = 0
for i in range(K+1):
    for j in range(K+1):
        summ = psum[i][K] + psum[K][j] - 2 * psum[i][j]
        result = max(result, NB + summ, NW - summ)
print(result)

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def reads():
  return [int(x) for x in input().split()]

(N, K) = reads()

L = K

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

NW = 0
for _ in range(N):
    (x, y, c) = input().split()
    (x, y) = (int(x), int(y))
    c = (x // K + y // K + int(c == "W")) & 1 
    (x, y) = (x % K, y % K)
    NW += c
    board[y][x] += 1 if c == 1 else -1 
NB = N - NW

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

for i in range(K):
    for j in range(K):
        psumr[i][j+1] = psumr[i][j] + board[i][j]

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

for i in range(K):
    for j in range(K):
        psum[i+1][j+1] = psum[i][j+1] + psumr[i][j+1]

result = 0
for i in range(K+1):
    for j in range(K+1):
        summ = psum[i][K] + psum[K][j] - 2 * psum[i][j]
        result = max(result, NB + summ, NW - summ)
print(result)

Solution (Python):
def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def calcsum(xs):
        r = sum(xs[:K])
        yield r
        for a, b in zip(xs[:K], xs[K:]):
            r += -a + b
            yield r

    pksum = [list(calcsum(xs)) for xs in p]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))

Solution (Python):
def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def isum(xs):
        r = 0
        yield r
        for x in xs:
            r += x
            yield r

    psum = [list(isum(row)) for row in p]
    pksum = [[b - a for a, b in zip(row, row[K:])] for row in psum]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))

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 [0]*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 [0,0]:
	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())

import numpy as np
m = np.zeros((3*K,3*K), dtype=np.int32)

offset = 0

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

K2 = 2*K
m[K2:,:K2] = m[:K,:K2]
np.cumsum(m[:,:K2],axis=0, out=m[:,:K2])
m[:K2,:K2] = m[K:,:K2] - m[:K2,:K2]

m[:K2,K2:] = m[:K2,:K]
np.cumsum(m[:K2,:],axis=1, out=m[:K2,:])
m[:K2,:K2] = m[:K2,K:] - m[:K2,:K2]


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

Solution (Python):
from operator import sub

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

numA = [[0] * K for i in range(K)]
numB = [[0] * K for i in range(K)]

for i in range(N):
    x, y, c = input().split()
    x = int(x) % (2 * K)
    y = int(y) % (2 * K)

    if c == 'B':
        if (x // K == 0 and y // K == 0) or (x // K == 1 and y // K == 1):
            numA[x % K][y % K] += 1
        else:
            numB[x % K][y % K] += 1
    else:
        if (x // K == 1 and y // K == 0) or (x // K == 0 and y // K == 1):
            numA[x % K][y % K] += 1
        else:
            numB[x % K][y % K] += 1


sumXA = list(map(sum, numA))
sumYA = list(map(sum, zip(*numA)))

sumXB = list(map(sum, numB))
sumYB = list(map(sum, zip(*numB)))

sumA = sum(sumXA)
sumB = sum(sumXB)

Arr = [[0] * K for i in range(K)]
numOKA = sumA
numOKB = sumB
for x in range(K):

    tempOKA = numOKA
    tempOKB = numOKB
    for y in range(K):
        Arr[x][y] = max(tempOKA + sumB - tempOKB, sumA - tempOKA + tempOKB)
        tempOKA -= sumYA[y]
        tempOKB -= sumYB[y]

    sumYA = list(map(sub, sumYA, numA[x]))
    sumYA = list(map(sub, sumYA, numA[x]))
    numOKA -= sumXA[x]

    sumYB = list(map(sub, sumYB, numB[x]))
    sumYB = list(map(sub, sumYB, numB[x]))
    numOKB -= sumXB[x]

print(max(map(max, Arr)))