Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math
 
K = int(input())
 
lis = [i for i in range(1,K+1)]
a = []
 
for i in lis:
    for j in lis:
        for k in lis:
            a.append([i,j,k])
gcd_list = []
for i in a:
    e,f,g = map(int,i)
    e_f = math.gcd(e,f)
    e_g = math.gcd(e,g)
    e_f_g = math.gcd(e_f,e_g)
    gcd_list.append(e_f_g)
print(sum(gcd_list))

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            ans += gcd(gcd(i, j), l)
print(ans)
### BUGGY CODE ###

N = int(input())
A =[int(input()) for i in range(N)]

for i in range(N):
    if i == 0:
        print(max(A[1:N]))
    elif i == N-1:
        print(max(A[0:N-1]))
    else:
        print(max([ max(A[0:i]) , max(A[i+1:N]) ] ))


### FIXED CODE ###

N = int(input())
A =[int(input()) for i in range(N)]

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

m = max(A)
maxindexlist = my_index_multi(A,m)

if len(maxindexlist) == 1:
    for i in range(N):
        if i != (maxindexlist[0]):
            print(m)
        else:
            A.pop(maxindexlist[0])
            print(max(A))
else:
    for i in range(N):
        print(m)
### BUGGY CODE ###

N=int(input())
S=input()
L=len(S)

ans=[]
for i in range(1000):
    key=str(i).zfill(3)
    if key[0] in S:
        idx1=S.index(key[0])
    else:
        continue
    for j in range(idx1+1,L-1):
        if S[j]==key[1]:
            idx2=j
            for k in range(idx2+1,L):
                if S[k]==key[2]:
                    ans.append(key)
                    break
               

print(len(set(ans)))


### FIXED CODE ###

N=int(input())
S=input()

L0=[]
L1=[]
ans=[]

for i in range(N-2):
    if S[i] in L0:
        continue
    else:
        L0.append(S[i])
    for j in range(i+1,N-1):
        temp=S[i]+S[j]
        if temp in L1:
            continue
        else:
            L1.append(temp)
        for k in range(j+1,N):
            ans.append(temp+S[k])


print(len(set(ans)))
### BUGGY CODE ###

S = input()
ans=0
for i in range(len(S)-3):
    j=4
    while i+j <= len(S):
        q = int(S[i:i+j])%2019
        if q==0:
            ans+=1
            j+=4
        elif len(str(q))==4:
            j+=1
        else :
            j += 4-len(str(q))
print(ans)

### FIXED CODE ###

S = input()
T = [0]*2019
T[0]=1
t = 0
ans = 0
dig = 1
for i in range(len(S)):
    t = (t + (int(S[-i-1]))*dig)%2019
    dig = (dig*10)%2019
    T[t] += 1
for j in T:
    ans +=int(j*(j-1)/2)
print(ans)
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
n = 1
m = 1
aa = a/2

if a%2 == 1:
    aa = (aa*2+1)//2

for i in range(int(aa)):
  n = n * b[i]
  if n == 0:
      print(0)
      exit()
  
for i in range(int(aa),a):
    m *= b[i]
    if m == 0:
      print(0)
      exit()

if n * m <= 10**18:
    print(n*m)
    exit()
  
print('-1')

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
n = 1

c = 0
d = 0

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()

for i in b:
  n *= i
  if n > 10**18:
    print(-1)
    exit()
print(n)
### BUGGY CODE ###

n=int(input())
S=input()

def e():
    for l in range(n//2, 0, -1):
        for i in range(n-l+1):
            s=S[i:i+l]
            if len(S.split(s))>=3:
                return l
    return 0

print(e())

### FIXED CODE ###

N = int(input())
S = input()

dp = [[0] * N for _ in range(N)]

ans = 0

for j in range(N - 1, 0, -1):
    sj = S[j]
    for i in range(j-1, -1, -1):
        si = S[i]
        if j == N - 1:
            if si == sj:
                dp[j][i] = 1
                ans = 1
        else:
            if si == sj:
                dp[j][i] = min(j - i, dp[j + 1][i + 1] + 1)
                ans = max(ans, dp[j][i])

print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
X = [0]*(N+1)
S = sum(A)

even_list = deque([A[i] for i in range(1, N) if (i+1) % 2 == 0])
odd_list = deque([A[i] for i in range(1, N) if (i+1) % 2 != 0])

X[1] = S - 2 * sum(even_list)
X[2] = S - 2 * sum(odd_list)
even_idx = N-1
odd_idx = N
for i in range(3, N+1):
  if i%2:
    even_idx += 2 
    even_idx %= N
    even_list.popleft()
    even_list.append(A[even_idx-1])
    X[i] = S - 2 * sum(even_list)
  else:
    odd_idx += 2
    odd_idx %= N
    odd_list.popleft()
    odd_list.append(A[odd_idx-1])
    X[i] = S - 2 * sum(odd_list)

for i in range(1, N+1):
  print(X[i], end=" ")
    


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sum(A)
even_s, even_t = 2, N-1
even = 0
for i in range(N):
  if (i+1) % 2 == 0:
    even += A[i]
odd_s, odd_t = 3, N
odd = 0
for i in range(2, N):
  if (i+1) % 2 == 1:
    odd += A[i]
odd_s, odd_t = 3, N
X = [0]*N
X[0] = S - even * 2
X[1] = S - odd * 2
for i in range(3, N+1):
  if i % 2:
    even -= A[even_s-1] 
    even += A[(even_t+2)%N-1]
    even_s += 2
    even_t = (even_t+2)%N
    X[i-1] = S - even * 2
  else:
    odd -= A[odd_s-1]
    odd += A[(odd_t+2)%N-1]
    odd_s += 2
    odd_t = (odd_t+2)%N
    X[i-1] = S - odd * 2

X = list(map(str, X))
print(" ".join(X))
### BUGGY CODE ###

def main():
    import numpy as np
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        
        num = np.zeros(len(lis))
        ans = 0
        for i in range(w):
            num2 = np.zeros(len(lis))
            for j in range(h):
                if l[j][i] == "1":
                    num2[d[j]] += 1
            
            if np.max(num2) > k:
                return float("INF")
            else:
                num += num2
            if np.max(num) > k:
                ans += 1
                num = num2
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        d = []
        for j in range(h):
            d.append(count)
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        lis1.append(count+1)
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    num2[d[j]] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        d = []
        for j in range(h):
            d.append(count)
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        lis1.append(count+1)
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np


def main():
	h,n=map(int,input().split())
	AB=[list(map(int,input().split())) for _ in range(n)]
	
	li=[10**10]*(10**5)
	li[0]=0
	
	for i in range(h):
		if li[i]==10**10:
			continue
		else:
			for a,b in AB:
				li[i+a]=min(li[i+a],li[i]+b)
	
	print(min(li[h:]))
	
	
	
	
	
	

if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np


def main():
	h,n=map(int,input().split())
	AB=[list(map(int,input().split())) for _ in range(n)]
	
	li=[10**10]*(10**5)
	li[0]=0
	
	for i in range(h):
		if li[i]==10**10:
			continue
		else:
			for a,b in AB:
				li[i+a]=min(li[i+a],li[i]+b)
	
	print(min(li[h:]))
	
	
	
	
	
	

if __name__ == "__main__":
	main()
### BUGGY CODE ###

d=set()
for i in[0]*input():d^={input()}
print len(d)

### FIXED CODE ###

d={}
for _ in[0]*int(input()):
 i=input()
 d[i]=d.get(i,0)^1
print(sum(d.values()))
### BUGGY CODE ###

N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    tmp=4*n*h-N*h-N*n
    if tmp>0:
      if N*h*n%tmp==0:
        print(h,n,N*h*n//tmp)
        exit()

### FIXED CODE ###

N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    tmp=4*n*h-N*h-N*n
    if tmp>0:
      if N*h*n%tmp==0:
        print(h,n,N*h*n//tmp)
        exit()
### BUGGY CODE ###

l, r = map(int, input().split())
rest = l*(l+1) % 2019
ans = rest
 
if r - l > 1:
  for i in range(l, r):
    for j in range(i+1, r+1):
      rest_next = i*j % 2019
      if rest_next < ans:
        ans = rest_next
      if ans == 0:
        break
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
rest = l*(l+1) % 2019
ans = rest
 
if r - l > 1:
  for i in range(l, r):
    if ans == 0:
      break
    for j in range(i+1, r+1):
      rest_next = i*j % 2019
      if rest_next < ans:
        ans = rest_next
      if ans == 0:
        break
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def dijkstra(s,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def dijkstra1(s,ss,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if (edge[0], v) == (s,ss) or (edge[0], v) == (ss,s):
                continue
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    for i in range(n-1):
        d = dijkstra(i,n,g)
        if d != a[i]:
            print(-1)
            return
        for j in range(i+1,n):
            d = dijkstra1(i,j,n,g)
            if d[j] == a[i][j]:
                ans -= a[i][j]
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,M=map(int,input().split())
a=[]
b=[]
for i in range(M):
    c,d=map(int,input().split())
    a.append(c)
    b.append(d)

s=[]
g=[]
#O(M)
for i in range(M):
    if a[i]==1:
        s.append(b[i])
    if b[i]==N:
        g.append(a[i])
flag = False
for idx in s:
    if idx in g:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
G = [list() for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
#O(M)
flag = False
for i in G[1]:
    if N in G[i]:
        flag = True
        break

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys
N = int(input())
A = list(map(int, input().split()))
a = list(reversed(sorted(list(set(A)))))
width = -1
height = -1
candinate = []
for tmp in a:
    b = A.count(tmp)
    if b >= 4:
        if width == -1:
            width = tmp
        if height == -1:
            height = tmp
    elif b >= 2:
        if width == -1:
            width = tmp
            b = 0
        if height == -1 and b != 0:
            height = tmp
    else:
        pass
    if width != -1 and height != -1:
        print(width*height)
        sys.exit()
print(0)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
a = Counter(A)
width = -1
height = -1
candinate = []
for tmp in reversed(sorted(list(set(A)))):
    b = a[tmp]
    if b >= 4:
        if width == -1:
            width = tmp
        if height == -1:
            height = tmp
    elif b >= 2:
        if width == -1:
            width = tmp
            b = 0
        if height == -1 and b != 0:
            height = tmp
    else:
        pass
    if width != -1 and height != -1:
        print(width*height)
        sys.exit()
print(0)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(N)]

A.sort()

for i in range(N):
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
cnt = 0
for i in range(N):
    if dp[i] == 1:
        cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# dp = [0 for _ in range(N)]

# A.sort()

# for i in range(N):
#     if dp[i] < 2:
#         p = A[i]
#         for j in range(N):
#             if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
#                 dp[j] += 1
# cnt = 0
# for i in range(N):
#     if dp[i] == 1:
#         cnt += 1
M = 10**6  + 5
cnt = [0 for _ in range(M)]
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    i = x
    while i < M:
        cnt[i] += 1
        i += x
ans = 0
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
L = [input() for i in range(N)]
ans = {}
for i in range(len(L)):
    a = L[i]
    ans[a] = ans.get(a,0) + 1

ans2 = [k for k, v in ans.items() if v == max(ans.values())]
ans2.sort()
[print(i) for i in ans2]


### FIXED CODE ###

N = int(input())
ans = {}
for i in range(N):
    a = input()
    ans[a] = ans.get(a,0) + 1

t = max(ans.values())
ans2 = [k for k, v in ans.items() if v ==t ]
ans2.sort()
[print(i) for i in ans2]
### BUGGY CODE ###

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

for i in range(n):
    p[i] = (p[i]+1)/2

ans = [0]*(n-k+1)
for i in range(n-k+1):
    ans[i] = sum(p[i:i+k])

print(max(ans))

### FIXED CODE ###

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

for i in range(n):
    p[i] = (p[i]+1)/2

ans = [0]*(n)
tem = 0
for i in range(n):
    tem = tem
    if i < k:
        tem = tem + p[i]
    else:
        tem = tem + p[i] - p[i-k]
    ans[i] = tem

print(max(ans))
### BUGGY CODE ###

S = input()
Q = int(input())
TFC = [input().split() for _ in range(Q)]
is_reversed = False
for tfc in TFC:
    if tfc[0] == '1':
        is_reversed = not is_reversed
    else:
        if tfc[1] == '1':
            if is_reversed:
                S += tfc[2]
            else:
                S = tfc[2] + S 
        else:
            if is_reversed:
                S = tfc[2] + S
            else:
                S += tfc[2]
if is_reversed:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S = input()
Q = int(input())
TFC = [input().split() for _ in range(Q)]
is_reversed = False
head = ''
tail = ''
for tfc in TFC:
    if tfc[0] == '1':
        is_reversed = not is_reversed
    else:
        if tfc[1] == '1':
            if is_reversed:
                tail += tfc[2]
            else:
                head += tfc[2]
        else:
            if is_reversed:
                head += tfc[2]
            else:
                tail += tfc[2]
if is_reversed:
    print(tail[::-1]+S[::-1]+head)
else:
    print(head[::-1]+S+tail)
### BUGGY CODE ###

import copy
import statistics
n = int(input())
x = list(map(int,input().split()))
l = ((len(x))//2)
for i in range(n):
	l2 = copy.copy(x)
	l2.pop(i)
	l2.sort()
	print(l2[l-1])

### FIXED CODE ###

import copy
n = int(input())
x = list(map(int,input().split()))
x2 = copy.copy(x)
x2.sort()
num1,num2 = (len(x)//2)-1,(len(x)//2)
med1,med2 = x2[num1],x2[num2]
for i in range(n):
	if x[i] <= med1:
		print(med2)
	else:
		print(med1)
### BUGGY CODE ###

import sys

stdin = sys.stdin

sys.setrecursionlimit(10 ** 5)


def li(): return map(int, stdin.readline().split())


def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())


def lf(): return map(float, stdin.readline().split())


def ls(): return stdin.readline().split()


def ns(): return stdin.readline().rstrip()


def lc(): return list(ns())


def ni(): return int(stdin.readline())


def nf(): return float(stdin.readline())


l, n = li()
x = [ni() for _ in range(n)]

#dp = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
dp0 = [[0]*(n+1) for _ in range(n + 1)]
dp1 = [[0]*(n+1) for _ in range(n + 1)]
left = [0] + x
right = [l] + x[::-1]

for total in range(1, n + 1):
    for ccw in range(total + 1):
        cw = total - ccw
        if ccw == 0:
            dp1[ccw][cw] = dp1[ccw][cw - 1] + (right[cw - 1] - right[cw])

        elif cw == 0:
            dp0[ccw][cw] = dp0[ccw - 1][cw] + (left[ccw] - left[ccw - 1])

        else:
            dp0[ccw][cw] = max(dp1[ccw - 1][cw] + (left[ccw] + l - right[cw]),
                                 dp0[ccw - 1][cw] + (left[ccw] - left[ccw - 1]))

            dp1[ccw][cw] = max(dp1[ccw][cw - 1] + (right[cw - 1] - right[cw]),
                                 dp0[ccw][cw - 1] + (left[ccw] + l - right[cw]))
ans = 0
for ccw in range(n + 1):
    cw = n - ccw
    ans = max(ans, dp0[ccw][cw], dp1[ccw][cw])

print(ans)


### FIXED CODE ###

L, N = map(int, input().split())
X = [int(input()) for i in range(N)]
Y = [L - X[-i] for i in range(1, N + 1)]


def check(T, N):
    X = [0] + T
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = P[i - 1] + X[i]
    for i in range(N, 0, -1):
        Q[i - 1] = Q[i] + L - X[i]
    ans = -1
    for i in range(1, N + 1):
        k = N - i
        if k % 2 == 0:
            a = k // 2
            t = 2 * (P[i + a - 1] - P[i - 1]) + 2 * (Q[i + a]) + X[i + a]
        else:
            a = k // 2
            t = 2 * (P[i + a] - P[i - 1]) + 2 * (Q[i + a + 1]) + L - X[i + a + 1]
        ans = max(ans, t)
        # print(t)
    return ans


print(max(check(X, N), check(Y, N)))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np

n,k = list(map(int, input().split()))
v0 = np.zeros((4*k, 4*k), dtype=int)
v1 = np.zeros((4*k, 4*k), dtype=int)

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    v = np.cumsum(v, axis=0)
    v = np.cumsum(v, axis=1)
    c = np.zeros((v.shape[0]+1, v.shape[1]+1), dtype=int)
    c[1:, 1:] = v
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
for i in range(2*k):
    for j in range(2*k):
        val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
        val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
        ans = max(ans, val0+val1)
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    if c=="B":
        x += k
    x %= 2*k
    y %= 2*k
    v[x][y] += 1
#     v[x][y+2*k] += 1
#     v[x+2*k][y] += 1
#     v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(v)

def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<=k and j<=k:
        l = [[i,i+k,j,j+k]]
    elif i>k and j<=k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<=k and j>k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
ans = -1
for i in range(2*k):
    for j in range(2*k-i):
        val0 = sub(v, i,j) + sub(v, i+k, j+k)
#         val0 = v[i+k][j+k]-v[i+k][j]-v[i][j+k]+v[i][j] + v[i+2*k][j+2*k]-v[i+2*k][j+k]-v[i+k][j+2*k]+v[i+k][j+k]
#         val1 = v[i+2*k][j+k]-v[i+2*k][j]-v[i+k][j+k]+v[i+k][j] + v[i+k][j+2*k]-v[i+k][j+k]-v[i][j+2*k]+v[i][j+k]
        ans = max(ans, val0)
print(ans)
### BUGGY CODE ###

while 1:
    try:
        n = input()
        c = 0
        ps = [False for i in range(n)]
        for i in range(2, n):
            ps[i] = True
        for i in range(2, int(n**0.5+1)):
            if ps[i]:
                for j in range(i**2, n, i):
                    ps[j] = False
            
        for i in range(n):
            if ps[i] is True:
                c += 1
        print c
    except EOFError:
        break

### FIXED CODE ###

n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break