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 numpy as np



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


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


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


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


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


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



print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
dp=[[0]*k for i in range(k)]
for i in range(n):
    x,y,z=input().split()
    x,y=int(x),int(y)
    if (x//k)%2==(y//k)%2:
        if z=='W':
            x,y=x%k,y%k
            dp[0][0]+=1
            if y<k-1:
                dp[0][y+1]-=1
            if x<k-1:
                dp[x+1][0]-=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]+=2
        else:
            x,y=x%k,y%k
            if y<k-1:
                dp[0][y+1]+=1
            if x<k-1:
                dp[x+1][0]+=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]-=2
    else:
        if z=='W':
            x,y=x%k,y%k
            if y<k-1:
                dp[0][y+1]+=1
            if x<k-1:
                dp[x+1][0]+=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]-=2
        else:
            x,y=x%k,y%k
            dp[0][0]+=1
            if y<k-1:
                dp[0][y+1]-=1
            if x<k-1:
                dp[x+1][0]-=1
            if x<k-1 and y<k-1:
                dp[x+1][y+1]+=2
for i in range(k):
    for j in range(1,k):
        dp[i][j]+=dp[i][j-1]
Max=0
Min=n
for j in range(k):
    for i in range(k):
        if i==0:
            Max=max(Max,dp[i][j])
            Min=min(Min,dp[i][j])
        else:
            dp[i][j]+=dp[i-1][j]
            Max=max(Max,dp[i][j])
            Min=min(Min,dp[i][j])
ans=max(Max,n-Min)
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):
from subprocess import*
call(('julia','-e',"""
const lines=readlines()
input()=shift!(lines)
int(s)=parse(Int32,s)
intLine()=map(int,split(input()))
function nextLine(k)
    x,y,c=split(input())
    int(x)%2k+1,(int(y)+(c=="W")k)%2k+1
end
function solve(k,g)
    m=0
    for i=1:2k,j=1:2k
        a=0
        for x=-1:2,y=-1:2
            (x+y)%2!=0&&continue
            v,w=i+x*k,j+y*k
            v>0<w&&(a+=g[min(2k,v)][min(2k,w)])
            v>k&&w>0&&(a-=g[min(2k,v-k)][min(2k,w)])
            w>k&&v>0&&(a-=g[min(2k,v)][min(2k,w-k)])
            v>k<w&&(a+=g[min(2k,v-k)][min(2k,w-k)])
        end
        m=max(m,a)
    end
    m
end
function main()
    n,k=intLine()
    g=Array{Int32,1}[[0for j=1:2k]for i=1:2k]
    for i=1:n
        x,y=nextLine(k)
        g[x][y]+=1
    end
    println(solve(k,cumsum(map(cumsum,g))))
end
main()
"""))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


'''
data = input("")
data = data.split(" ")
a = int(data[0])
b = int(data[1])

if (a*b)%2 == 1: print("Odd")
else: print("Even")
'''


'''
data = input()
data = int(data.replace(" ",""))
if data%(data**(1/2)) == 0: print("Yes")
else: print("No")
'''


'''
n = int(input(""))
data = [0]*n
t = [0]*n
x = [0]*n
y = [0]*n
flag = 0

for i in range(n):
    data[i] = input("")
    t[i] = int(data[i].split(" ")[0])
    x[i] = int(data[i].split(" ")[1])
    y[i] = int(data[i].split(" ")[2])

for i in range(n):
    if i == 0:
        if x[i]+y[i] > t[i] or (x[i]+y[i]-t[i])%2 != 0:
            print("No")
            flag = 1
            break
    else:
        if abs(x[i]-x[i-1])+abs(y[i]-y[i-1]) > t[i] or (x[i]+y[i]-t[i])%2 != 0:
            print("No")
            flag = 1
            break
if flag == 0:print("Yes")
'''


def check(y,x,k):
    l = max(0,min(m,x))
    r = max(0,min(m,x+k))
    d = max(0,min(m,y))
    u = max(0,min(m,y+k))
    f[d][l] += 1
    f[d][r] -= 1
    f[u][l] -= 1
    f[u][r] += 1
n,k = LI()
m = k*2
f = [[0]*(m+1) for i in range(m+1)]
for i in range(n):
    x,y,c = input().split()
    x = int(x)%m
    y = int(y)%m
    if c == "W":
        y += k
        y %= m
    check(y-m+1,x-m+1,k)
    check(y+1,x-m+1,k)
    check(y-k+1,x-k+1,k)
    check(y+k+1,x-k+1,k)
    check(y-m+1,x+1,k)
    check(y+1,x+1,k)
    check(y-k+1,x+k+1,k)
    check(y+k+1,x+k+1,k)

for y in range(m+1):
    for x in range(m):
        f[y][x+1] += f[y][x]

for y in range(m):
    for x in range(m+1):
        f[y+1][x] += f[y][x]

ans = 0
for i in f:
    ans = max(ans,max(i))
print(ans)

Solution (Python):
import sys
from itertools import accumulate
input = sys.stdin.readline
def main():
    N, K = map( int ,input().split())
    TK = K*2
    B = [[0]*(K*2) for _ in range(TK)]
    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            B[x%TK][y%TK] += 1
        else:
            B[x%TK][(y+K)%TK] += 1
    C = [[0]*(TK+1)] + [[0] + list( accumulate(B[i])) for i in range(TK)]
    for i in range(TK):
        for j in range(TK+1):
            C[i+1][j] += C[i][j]
    def get(i1, j1, i2, j2):
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if ans < get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK):
                ans = get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK)
            if ans < get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK):
                ans = get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):



import numpy as np
N,K = map(int,input().split())
KK = 2*K
hope = np.zeros((KK,KK),dtype=np.int32)

for _ in range(N):
  x,y,c  = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x -= K
  hope[x%KK,y%KK] += 1


A = np.zeros((KK+K,KK+K),dtype=np.int32)
A[:-K,:-K] = hope[:]
A[K:,:-K] += -hope[:]
A[:-K,K:] += -hope[:]
A[K:,K:] += hope[:]
A = A.cumsum(axis = 0).cumsum(axis = 1)


B = A[:,:KK]
B[:,:K] += A[:,KK:] 
A = B[:KK,:]
A[:K,:] += B[KK:,:] 
B = A[:K,:] 
B[:,:K] += A[K:,K:]
B[:,K:] += A[K:,:K]

answer = B.max()
print(answer)

Solution (Python):
N,K=map(int,input().split())
B=[[0]*(2*K) for i in range(2*K)]
W=[[0]*(2*K) for i in range(2*K)]
w=0
for i in range(N):
    x,y,c=map(str,input().split())
    x=int(x)
    y=int(y)
    if c=="B":
        B[y%(2*K)][x%(2*K)]+=1
    else:
        w+=1
        W[y%(2*K)][x%(2*K)]+=1
sumb=[[0]*(2*K+1) for i in range(2*K+1)]
sumw=[[0]*(2*K+1) for i in range(2*K+1)]
for i in range(2*K):
    for j in range(2*K):
        sumb[i+1][j+1]=sumb[i][j+1]+sumb[i+1][j]-sumb[i][j]+B[i][j]
        sumw[i+1][j+1]=sumw[i][j+1]+sumw[i+1][j]-sumw[i][j]+W[i][j]


ans=0
for i in range(K):
    for j in range(K):
        for _ in range(2):
            s=0
            s+=sumb[i][j]-sumb[i][0]-sumb[0][j]+sumb[0][0]
            s+=sumb[i+K][j+K]-sumb[i][j+K]-sumb[i+K][j]+sumb[i][j]
            s+=sumb[i][2*K]-sumb[0][2*K]-sumb[i][j+K]+sumb[0][j+K]
            s+=sumb[2*K][j]-sumb[i+K][j]-sumb[2*K][0]+sumb[i+K][0]
            s+=sumb[2*K][2*K]-sumb[i+K][2*K]-sumb[2*K][j+K]+sumb[i+K][j+K]

            s+=sumw[i][j+K]-sumw[0][j+K]-sumw[i][j]+sumw[0][j]
            s+=sumw[i+K][j]-sumw[i][j]-sumw[i+K][0]+sumw[i][0]
            s+=sumw[2*K][j+K]-sumw[i+K][j+K]-sumw[2*K][j]+sumw[i+K][j]
            s+=sumw[i+K][2*K]-sumw[i+K][j+K]-sumw[i][2*K]+sumw[i][j+K]

            ans=max(ans,s)
            sumb,sumw=sumw,sumb

print(ans)

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

ans=0
for i in range(K):
    for j in range(K):
        for _ in range(2):
            s=0
            s+=sumb[i][j]-sumb[i][0]-sumb[0][j]+sumb[0][0]
            s+=sumb[i+K][j+K]-sumb[i][j+K]-sumb[i+K][j]+sumb[i][j]
            s+=sumb[i][2*K]-sumb[0][2*K]-sumb[i][j+K]+sumb[0][j+K]
            s+=sumb[2*K][j]-sumb[i+K][j]-sumb[2*K][0]+sumb[i+K][0]
            s+=sumb[2*K][2*K]-sumb[i+K][2*K]-sumb[2*K][j+K]+sumb[i+K][j+K]

            s+=sumw[i][j+K]-sumw[0][j+K]-sumw[i][j]+sumw[0][j]
            s+=sumw[i+K][j]-sumw[i][j]-sumw[i+K][0]+sumw[i][0]
            s+=sumw[2*K][j+K]-sumw[i+K][j+K]-sumw[2*K][j]+sumw[i+K][j]
            s+=sumw[i+K][2*K]-sumw[i+K][j+K]-sumw[i][2*K]+sumw[i][j+K]

            ans=max(ans,s)
            sumb,sumw=sumw,sumb

print(ans)

Solution (Python):
N,K = [ int(it) for it in input().split() ]
K2 = 2*K
li = [ (lambda x,y,z:[int(x)%K2,int(y)%K2,0 if z=="W" else 1] )(*(input().split())) for i in range(N)]

bm = [[0]*(K2+1) for i in range(K2+1)]
wm = [[0]*(K2+1) for i in range(K2+1)]
for x,y,z in li:
  if (z==0):
    wm[x+1][y+1] += 1
  else:
    bm[x+1][y+1] += 1

for i in range(1,2*K+1):
  for j in range(1,2*K+1):
    bm[i][j]=bm[i-1][j]+bm[i][j-1]-bm[i-1][j-1]+bm[i][j]
    wm[i][j]=wm[i-1][j]+wm[i][j-1]-wm[i-1][j-1]+wm[i][j]
sumb=bm
sumw=wm

ans=0
for i in range(K):
    for j in range(K):
        for _ in range(2):
            s=0
            s+=sumb[i][j]-sumb[i][0]-sumb[0][j]+sumb[0][0]
            s+=sumb[i+K][j+K]-sumb[i][j+K]-sumb[i+K][j]+sumb[i][j]
            s+=sumb[i][2*K]-sumb[0][2*K]-sumb[i][j+K]+sumb[0][j+K]
            s+=sumb[2*K][j]-sumb[i+K][j]-sumb[2*K][0]+sumb[i+K][0]
            s+=sumb[2*K][2*K]-sumb[i+K][2*K]-sumb[2*K][j+K]+sumb[i+K][j+K]

            s+=sumw[i][j+K]-sumw[0][j+K]-sumw[i][j]+sumw[0][j]
            s+=sumw[i+K][j]-sumw[i][j]-sumw[i+K][0]+sumw[i][0]
            s+=sumw[2*K][j+K]-sumw[i+K][j+K]-sumw[2*K][j]+sumw[i+K][j]
            s+=sumw[i+K][2*K]-sumw[i+K][j+K]-sumw[i][2*K]+sumw[i][j+K]

            ans=max(ans,s)
            sumb,sumw=sumw,sumb

print(ans)

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


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

    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

    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(2 * K, 2 * K)
R2D.load(Demand)
R2D.calc()


ans = 0
for x in range(K):
    for y in range(K):
        cnt = 0
        cnt += R2D.get(x, y, x + K - 1, y + K - 1)  
        cnt += R2D.get(0, 0, x - 1, y - 1)  
        cnt += R2D.get(x + K, 0, 2 * K - 1, y - 1)  
        cnt += R2D.get(0, y + K, x - 1, 2 * K - 1)  
        cnt += R2D.get(x + K, y + K, 2 * K - 1, 2 * K - 1)  
        ans = max(ans, cnt, N - cnt)

print(ans)

Solution (Python):



import numpy as np
N,K = map(int,input().split())
KK = 2*K
hope = np.zeros((KK,KK),dtype=np.int32)

XYC = [input().split() for _ in range(N)]

for x,y,c in XYC:
  x = int(x)
  y = int(y)
  if c == 'B':
    x -= K
  x %= KK
  y %= KK
  hope[x,y] += 1


A = np.zeros((KK+K,KK+K),dtype=np.int32)
A[:-K,:-K] = hope[:]
A[K:,:-K] += -hope[:]
A[:-K,K:] += -hope[:]
A[K:,K:] += hope[:]
A = A.cumsum(axis = 0).cumsum(axis = 1)


B = A[:,:KK]
B[:,:K] += A[:,KK:] 
A = B[:KK,:]
A[:K,:] += B[KK:,:] 
B = A[:K,:] 
B[:,:K] += A[K:,K:]
B[:,K:] += A[K:,:K]

answer = B.max()
print(answer)

Solution (Python):
N,K = [ int(it) for it in input().split() ]
K2 = 2*K
li = [ (lambda x,y,z:[int(x)%K2,int(y)%K2,0 if z=="W" else 1] )(*(input().split())) for i in range(N)]

bm = [[0]*(K2+1) for i in range(K2+1)]
wm = [[0]*(K2+1) for i in range(K2+1)]
for x,y,z in li:
  if (z==0):
    wm[x+1][y+1] += 1
  else:
    bm[x+1][y+1] += 1

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

ma = 0
for i in range(K):
  for j in range(K):
    for _ in range(2):
      s = 0
      s += bm[i][j]-bm[i][0]-bm[0][j]+bm[0][0]
      s += wm[K+i][j]-wm[K+i][0]-wm[i][j]+wm[i][0]
      s += wm[i][K+j]-wm[i][j]-wm[0][K+j]+wm[0][j]
      s += bm[i+K][j+K]-bm[i+K][j]-bm[i][j+K]+bm[i][j]
      s += bm[i][2*K]-bm[0][2*K]-bm[i][j+K]+bm[0][j+K]
      s += bm[2*K][j]-bm[2*K][0]-bm[i+K][j]+bm[i+K][0]
      s += wm[2*K][j+K]-wm[2*K][j]-wm[K+i][j+K]+wm[K+i][j]
      s += wm[i+K][2*K]-wm[i][2*K]-wm[K+i][j+K]+wm[i][j+K]
      s += bm[2*K][2*K]-bm[2*K][j+K]-bm[i+K][2*K]+bm[i+K][j+K]
      ma = max(ma,s)
      bm,wm=wm,bm
print (ma)

Solution (Python):
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = map(int, next(sys.stdin).split())

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


def draw(sx, sy, ex, ey):
    sx %= MOD
    sy %= MOD
    ex = (ex - 1) % MOD + 1
    ey = (ey - 1) % MOD + 1

    if sx < ex and sy < ey:
        grid[sx][sy] += 1
        if ex < MOD:
            grid[ex][sy] -= 1
        if ey < MOD:
            grid[sx][ey] -= 1
        if ex < MOD and ey < MOD:
            grid[ex][ey] += 1

    elif ex <= sx:
        if ey <= sy:
            draw(0, 0, ex, ey)
            draw(0, sy, ex, MOD)
            draw(sx, 0, MOD, ey)
            draw(sx, sy, MOD, MOD)
        else:
            draw(0, sy, ex, ey)
            draw(sx, sy, MOD, ey)
    else:
        draw(sx, 0, ex, ey)
        draw(sx, sy, ex, MOD)


for _ in range(N):
    x, y, c = next(sys.stdin).split()
    x = int(x)
    y = int(y)
    if c == 'W':
        x += K

    
    
    draw(x, y, x + K, y + K)
    draw(x + K, y + K, x + K * 2, y + K * 2)

for i in range(MOD - 1):
    for j in range(MOD):
        grid[i + 1][j] += grid[i][j]
for i in range(MOD - 1):
    for j in range(MOD):
        grid[j][i + 1] += grid[j][i]
ans = 0
for i in range(MOD):
    ans = max(ans, *grid[i])
print(ans)

Solution (Python):
N,K=map(int, input().split())
K2 = 2*K
inmap = [[0]*(K) for _ in range(K2)]
accmap = [[0]*(K+1) for _ in range(K2+1)]
inmapdeb = {}
for i in range(N):
    line = input().split()
    x, y, wb = int(line[0]), int(line[1]), line[2]
    if wb == 'W':
        x += K
    y %= K2
    if y >= K:
        y = y%K
        x = (x+K) %K2
    else:
        x = x % K2
    inmap[x][y] += 1






def calc(x, y):
    return accmap[x][y] \
        + (accmap[x+K][K] - accmap[x][K] - accmap[x+K][y] + accmap[x][y]) \
        + (accmap[K2][y] - accmap[x+K][y])

for i in range(K2):
    for j in range(K):
        accmap[i+1][j+1] = inmap[i][j] + accmap[i+1][j] + accmap[i][j+1] - accmap[i][j]

res = 0
for i in range(K):
    for j in range(K):
        
        cand = calc(i, j)
        
        res = max(res, cand, N-cand)

print(res)

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


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

    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

    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(2 * K, 2 * K)
R2D.load(Demand)
R2D.calc()

ans = 0
for x in range(K):
    for y in range(K):
        fulfill = 0
        fulfill += R2D.get(0, 0, x - 1, y - 1)  
        fulfill += R2D.get(x + K, 0, 2 * K - 1, y - 1)  
        fulfill += R2D.get(x, y, x + K - 1, y + K - 1)  
        fulfill += R2D.get(0, y + K, x - 1, 2 * K - 1)  
        fulfill += R2D.get(x + K, y + K, 2 * K - 1, 2 * K - 1)  

        ans = max(ans, fulfill, N - fulfill)

print(ans)

Solution (Python):
n, k = [int(i) for i in input().split(" ")]
dm = [[0 for j in range(0, 2 * k)] for i in range(0, 2 * k)]
s = [[0 for j in range(0, 2 * k + 1)] for  i in range(0, 2 * k + 1)]

for i in range(0, n):
    x, y, c = input().split(" ")
    x = int(x) % (2 * k)
    if c == "W":
        y = int(y) % (2 * k)
    else:
        y = (int(y) + k) % (2 * k)
    dm[x][y] += 1

for i in range(1, 2 * k + 1):
    for j in range(1, 2 * k + 1):
        s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + dm[i - 1][j - 1]

def srect(i, j, r, l):
    global s
    return s[r][l] - s[r][j] - s[i][l] + s[i][j]

m = 0
for i in range(0, k):
    for j in range(0, k):
        aw = srect(0, j, i, j + k) + srect(i, 0, i + k, j) + srect(i, j + k, i + k, 2 * k) + srect(i + k, j, 2 * k, j + k)
        raw = n - aw
        if m < max(aw, raw):
            m = max(aw, raw)
print(m)

Solution (Python):
import numpy as np


def solve(string):
    n, k, *xyc = string.split()
    k = int(k)
    l = 2 * int(k)
    xy = [(int(x) % l, int(y) % l) if c == "W" else (int(x) % l, (int(y) + k) % l)
          for x, y, c in zip(xyc[::3], xyc[1::3], xyc[2::3])]
    ans = [[0 for j in range(l + 0)] for i in range(l + 0)]
    for _x, _y in xy:
        if (_x - k + 0.5) * (_y - k + 0.5) > 0:
            lt = 2
            lte = 1
            ans[0][0] += 1
        else:
            lt = -2
            lte = -1
        _x %= k
        _y %= k
        ans[_x][_y] += lt
        ans[_x + k][_y] -= lt
        ans[_x][_y + k] -= lt
        ans[_x + k][_y + k] += lt
        ans[_x + k][0] += lte
        ans[0][_y + k] += lte
        ans[_x][0] -= lte
        ans[0][_y] -= lte
    return str(np.asarray(ans).cumsum(axis=1).cumsum(axis=0).max())


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Solution (Python):
import numpy as np


def solve(string):
    n, k, *xyc = string.split()
    k = int(k)
    l = 2 * int(k)
    xy = [(int(x) % l, int(y) % l) if c == "W" else (int(x) % l, (int(y) + k) % l)
          for x, y, c in zip(xyc[::3], xyc[1::3], xyc[2::3])]
    ans = [[0 for j in range(l + 0)] for i in range(l + 0)]
    for _x, _y in xy:
        if (_x - k + 0.5) * (_y - k + 0.5) > 0:
            _x %= k
            _y %= k
            ans[_x][_y] += 2
            ans[_x + k][_y] -= 2
            ans[_x][_y + k] -= 2
            ans[_x + k][_y + k] += 2
            ans[_x + k][0] += 1
            ans[0][_y + k] += 1
            ans[0][0] += 1
            ans[_x][0] -= 1
            ans[0][_y] -= 1
        else:
            _x %= k
            _y %= k
            ans[_x][_y] -= 2
            ans[_x + k][_y] += 2
            ans[_x][_y + k] += 2
            ans[_x + k][_y + k] -= 2
            ans[_x + k][0] -= 1
            ans[0][_y + k] -= 1
            ans[_x][0] += 1
            ans[0][_y] += 1
    return str(np.asarray(ans).cumsum(axis=1).cumsum(axis=0).max())


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Solution (Python):
import numpy as np
import sys

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

def imos(i1, j1, i2, j2):
    Mij[i1][j1] += 1
    Mij[i1][j2] -= 1
    Mij[i2][j1] -= 1
    Mij[i2][j2] += 1

for _ in range(N):
    i, j, s = sys.stdin.readline().split()
    i = int(i) % K2
    j = int(j) % K2
    if s == "B":
        i = (i + K) % K2
    i1 = i % K
    j1 = j % K
    if (i < K and j < K) or (K <= i and K <= j):
        imos(0, 0, i1, j1)
        imos(0, j1 + K, i1, K2)
        imos(i1 + K, 0, K2, j1)
        imos(i1 + K, j1 + K, K2, K2)
        imos(i1, j1, i1 + K, j1 + K)
    else:
        imos(0, j1, i1, j1 + K)
        imos(i1 + K, j1, K2, j1 + K)
        imos(i1, 0, i1 + K, j1)
        imos(i1, j1 + K, i1 + K, K2)


Mij = np.array(Mij)
for x in range(K2):
    Mij[:, x + 1] += Mij[:, x]
for y in range(K2):
    Mij[y + 1, :] += Mij[y, :]
print(Mij.max())

Solution (Python):
import numpy as np

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


def imos(x1, y1, x2, y2):
    Mij[y1][x1] += 1
    Mij[y2][x2] += 1
    Mij[y2][x1] -= 1
    Mij[y1][x2] -= 1

for _ in range(N):
    ls = input().split()
    x = int(ls[0]) % K2
    y = int(ls[1]) % K2
    if ls[2] == "B":
        y = (y + K) % K2
    x_ = x % K
    y_ = y % K

    if (x < K and y < K) or (K <= x and K <= y):
        imos(0, 0, x_ + 1, y_ + 1)
        imos(x_ + K + 1, 0, K2, y_ + 1)
        imos(0, y_ + K + 1, x_ + 1, K2)
        imos(x_ + K + 1, y_ + K + 1, K2, K2)
        imos(x_ + 1, y_ + 1, x_ + K + 1, y_ + K + 1)
    else:
        imos(x_ + 1, 0, x_ + K + 1, y_ + 1)
        imos(x_ + 1, y_ + K + 1, x_ + K + 1, K2)
        imos(0, y_ + 1, x_ + 1, y_ + K + 1)
        imos(x_ + K + 1, y_ + 1, K2, y_ + K + 1)

Mij = np.array(Mij)
for x in range(K2):
    Mij[:, x + 1] += Mij[:, x]
for y in range(K2):
    Mij[y + 1, :] += Mij[y, :]

print(Mij.max())

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18
 
N,K=rl()
 
W = [[0 for _ in range(K+3)] for _ in range(K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1
 
for x in range(0,K+2):
    for y in range(0,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(0,K+2):
        W[x][y] += W[x-1][y]
 
ans = 0
for x in range(K+1):
    for y in range(K+1):
        res = W[x][y]
        ans = max(ans,res,N-res)
 
print(ans)

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18
 
N,K=rl()
 
W = [[0 for _ in range(K+3)] for _ in range(K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1
 
for x in range(0,K+2):
    for y in range(0,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(0,K+2):
        W[x][y] += W[x-1][y]
 
ans = 0
for x in range(K+1):
    for y in range(K+1):
        res = W[x][y]
        ans = max(ans,res,N-res)
 
print(ans)

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[0][y+K+1] -= 1
        W[x+1][0] += 1
        W[x+1][y+1] -= 2
        W[x+1][y+K+1] += 2
        W[x+1][2*K] -= 1
        W[x+K+1][0] -= 1
        W[x+K+1][y+1] += 2
        W[x+K+1][y+K+1] -= 2
        W[x+K+1][2*K] += 1
        W[2*K][y+1] -= 1
        W[2*K][y+K+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[x+K+1][y+1] -= 2
        W[x+1][y+K+1] -= 2
        W[x+K+1][y+K+1] += 1
        W[x+K+1][0] += 1
        W[2*K][0] -= 1
        W[2*K][y+1] += 1
        W[0][y+K+1] += 1
        W[0][2*K] -= 1
        W[x+1][2*K] += 1

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

print(ans)

Solution (Python):
n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score = cum[i][k] + cum[k][j] - 2*cum[i][j]
        maxscore = max(maxscore, max(cum[k][k] - score, score))
print(maxscore + initscore)