Harryxun/stf_run huggingface dataset:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
      	que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])

### FIXED CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    l = len(que)
    while (que):
        if l > 0:
            que_warp.append(que[0])
            l -= 1
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])
input()
nums = map(int, input().split())
count = 0
while True:
  for i, n in enumerate(nums):
    if n % 2 == 1:
      break
    else:
      nums[i] = n / 2
      count += 1
print(count)
      

### FIXED CODE ###

kazu = int(input())
nums = list(map(int, input().split()))
count = 0
flg = True
while flg:
  for i in range(kazu):
    if nums[i] % 2 == 1:
      flg = False
      break
    else:
      nums[i] /= 2
  count += 1
count -= 1
print(count)
n, w = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(n)]
dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(w + 1):
        if j < A[i][0]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - A[i][0]] + A[i][1])
            
print(dp[n][w])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 8)

N, W = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(N)]
memo = {i : {} for i in range(N)}

def dfs(i, j):
    if i == N:
        return 0
    elif j in memo[i]:
        return memo[i][j]
    elif A[i][0] > j:
        ans = dfs(i + 1, j)
    else:
        ans  = max(dfs(i + 1, j), A[i][1] + dfs(i + 1, j - A[i][0]))
    memo[i][j] = ans
    return ans
        
print(dfs(0, W))
X,Y=map(int,input().split())
if X<Y:
    X,Y=Y,X
mod=10**9+7

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

x,y=0,0
while X>=3 and Y>=3:
    x+=1
    y+=1
    X-=3
    Y-=3
if X==0 and Y==0:
    pass
elif X//Y == 2 and X%Y==0:
    x+=Y
else:
    print(0)
    exit()

print(Comb(x+y,y))

### FIXED CODE ###

X,Y=map(int,input().split())
if X<Y:
    X,Y=Y,X
mod=10**9+7

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

d=X-Y
if (Y-d)%3!=0 or Y-d<0:
    print(0)
    exit()
x,y=d+(Y-d)//3,(Y-d)//3

print(Comb(x+y,y))
import itertools
from collections import defaultdict as dict
d = dict(int)

N = int(input())
S = [int(_) for _ in input()]
s = list(itertools.combinations(S, 3))

for j in range(len(s)):

    # カウントアップ
    d[s[j]] += 1

print(len(d))

### FIXED CODE ###

X = int(input())
if X < 100:
    print(0)
    exit()

w = X // 100
ans = w * 105
if X <= ans:
    print(1)
else:
    print(0)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N=one_int()

dicts={}
for i in range(2,N+1):
    lists = factorization(i)
    for item in lists:
        if item[0] != 1:
            if item[0] in dicts:
                dicts[item[0]] += item[1]
            else:
                dicts[item[0]] = item[1]

div=10**9 + 7
ans=1

for k,v in dicts.items():
    ans *= (v+1)%div

print(ans%div)

### FIXED CODE ###

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
# import sys
# input = sys.stdin.readline

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N=one_int()

dicts={}
for i in range(2,N+1):
    lists = factorization(i)
    for item in lists:
        if item[0] != 1:
            if item[0] in dicts:
                dicts[item[0]] += item[1]
            else:
                dicts[item[0]] = item[1]

div=10**9 + 7
ans=1

for k,v in dicts.items():
    ans *= (v+1)%div

print(ans%div)
n=input()


n=str(n)
Sum=0
for i in range(len(n)):
    Sum=Sum+n[i]-"0"

if Sum%9==0:
    print("yes")
else:
    print("no")
    

        

### FIXED CODE ###

n=input()


n=str(n)
Sum=0
for i in range(len(n)):
    Sum=Sum+int(n[i])

if Sum%9==0:
    print("Yes")
else:
    print("No")
import sys

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.par[x]
        y = self.par[y]
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
p = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
sys.setrecursionlimit(max(1000, N+1))
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

for i in range(1, N+1):
    if uf.find(i) == uf.find(p[i]):
        ans += 1

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
p = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

for i in range(1, N+1):
    if uf.find(i) == uf.find(p[i]):
        ans += 1

print(ans)
(A, B, T) = (int, input().split())

biscuit = 0

for i in range(0, A*10, T*10 + 5):
    biscuit += B

print(B)
    


### FIXED CODE ###


(A, B, T) = map(int, input().split(" "))

biscuit = 0

for i in range(A * 10, T*10 + 5, A * 10):
    biscuit += B

print(biscuit)
N = int(input())
A = list(map(int,input().split()))

ans = []
i = 0
while A[i] > 0:
    i += 1
n = i
for i in range(n-1,0,-1):
    if A[i] < A[i-1]:
        A[i-1] += A[i]
        ans.appned(i+1,i)


for i in range(n,N-1):
    if A[i] <= A[i+1]:
        continue
    else:
        if A[i+1] >= 0:
            A[i+1] += A[i]
            ans.append([i+1,i+2])
        else:
            A[i+1] += 2 * A[i]
            ans.append([i+1,i+2])
            ans.append([i+1,i+2])

# print(A)
print(len(ans))
for a in ans:
    print(*a)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))

MIN,MAX = 10**7,-10**7
ans = []
for i in range(N):
    if MIN > A[i]:
        MIN =A[i]
        min_i = i
    if MAX < A[i]:
        MAX = A[i]
        max_i = i

if abs(MIN) <= abs(MAX):
    for i in range(N):
        if A[i] < 0:
            A[i] += MAX
            ans.append([max_i+1,i+1])
    # print(A)

    for i in range(N-1):
        if A[i] > A[i+1]:
            A[i+1] += A[i]
            ans.append([i+1,i+2])

else:
    for i in range(N):
        if A[i] > 0:
            A[i] += MIN
            ans.append([min_i+1,i+1])
    # print(A)

    for i in range(N-1,0,-1):
        if A[i] < A[i-1]:
            A[i-1] += A[i]
            ans.append([i+1,i])
print(len(ans))
for a in ans:
    print(*a)
N,A,B = map(int,input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())

# x回で全モンスター倒せるかどうかをにぶちゃん(にぱー)

import math

def check(x):
    count = 0
    for i in range(N):
        count += math.ceil(max(h[i] - B * x, 0) / (A - B))
           
    if count <= x:
        return True
    else:
        return False
    
def solve():
    
    while abs(right-left) > 1:
    
        left = -1
        right = 10**9+1
    
        center = (right+left)//2
    
        if check(center) == True:
            right = center
        elif check(center) == False:
            left = center
        
    return right
    
print(solve())

### FIXED CODE ###

N,A,B = map(int,input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())

# x回で全モンスター倒せるかどうかをにぶちゃん(にぱー)

import math

def check(x):
    count = 0
    for i in range(N):
        count += math.ceil(max(h[i] - B * x, 0) / (A - B))
           
    if count <= x:
        return True
    else:
        return False
    
def solve():
    
    left = -1
    right = 10**9+1
    
    while abs(right-left) > 1:
    
        center = (right+left)//2
    
        if check(center) == True:
            right = center
        elif check(center) == False:
            left = center
        
    return right
    
print(solve())
s = input()
N = s.count('N')
S = s.count('S')
E = s.count('E')
W = s.count('W')
if (N >= 1 and S >= 1) or (E >= 1 and W >= 1) or s ='':
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S =input()
if (('N' in S) == ('S' in S)) and (('W' in S) == ('E' in S)):
    print('Yes')
else:
    print('No')
N = int(input())

E = [[] for _ in range(N + 1)]
for a, b, c in [[int(i) for i in input().split()] for _ in range(N - 1)]:
    E[a].append((b, c))
    E[b].append((a, c))


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

for x, y in [[int(i) for i in input().split()] for _ in range(Q)]:
    print(dist[x] + dist[y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())

E = [[] for _ in range(N + 1)]
for a, b, c in [[int(i) for i in input().split()] for _ in range(N - 1)]:
    E[a].append((b, c))
    E[b].append((a, c))


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

for x, y in [[int(i) for i in input().split()] for _ in range(Q)]:
    print(dist[x] + dist[y])
n = int(input())

a = []
a = list(map(int, input().split()))

counter = 0
check = 0

for i in range(n):
    if a[i] % 2 = 0:
        check += 1



while check == n:
    for i in range(n):
        a[i] = a[i]/2
    for i in range(n):
        product = 1
        product *= a[i]
    counter += 1
print(counter)




### FIXED CODE ###

s = input()
count = 0

if s[0] == '1':
  count += 1
if s[1] == '1':
  count += 1
if s[2] == '1':
  count += 1

print(count)
n, m =map(int,input().split())
flg=0
for i in range(n+1):
    for j in range(n-i+1):
        if 10000*i+5000*j+1000*(n-i-j)==m:
            flg = 1
            x = i
            y = j
            z = k
            break
        else:
            continue
        break
            
if flg==0:
    print(-1,-1,-1)
else:
    print(x,y,z)

### FIXED CODE ###

n, y = map(int, input().split())
flg = 0
for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i+5000*j+1000*(n-i-j) == y:
            a = i
            b = j
            c = n-i-j
            flg = 1
            break
        else: 
            pass
if flg == 1:
    print(a,b,c)
else:
    print(-1,-1,-1)
a,b,c=map(int(input()))
print("YES" if any((a*i)%b==c for i in range(a,b+1)) else "NO")

### FIXED CODE ###

a,b,c=map(int,input().split())
print("YES" if any((a*i)%b==c for i in range(1,b+1)) else "NO")
n = int(input())
m = int(input())
if n == m:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n, m = map(int, input().split())
if n == m:
  print("Yes")
else:
  print("No")
n = int(input())
a = [False] * 100000

cnt = 0
for i in range(n):
    ai = int(input()) - 1
    a[ai] = not a[ai]

    if a[ai]:
        cnt += 1
    else:
        cnt -= 1

print(cnt)

### FIXED CODE ###

n = int(input())
a = {}

cnt = 0
for i in range(n):
    ai = int(input()) - 1

    if ai in a:
        cnt -= 1
        del a[ai]
    else:
        cnt += 1
        a[ai] = 1

print(cnt)
import sys
sys.stdin = open('input.txt', 'r') 
sys.stdout = open('output.txt', 'w')

n, k = map(int, input().split())
if(n >= 10):
	print(k)
else:
	print(k + 100 * (10 - n))	

### FIXED CODE ###


n, k = map(int, input().split())
if(n >= 10):
	print(k)
else:
	print(k + 100 * (10 - n))
n,k=map(int,input().split())
iran=[]
l=list(map(int,input().split()))
#n,k=6,727202214173249351
#l=[6,5,2,5,3,2]
for i in range(N):
  if l.count(i+1)==0:
    iran.append(i+1)
kiseki=[]
#町1からスタート
u=1
kiseki.append(1)
for i in l:
  u=l[u-1]
  if kiseki.count(u)==0:
    kiseki.append(u)
  else:
    kiseki.append(u)
    break
kuri=kiseki[kiseki.index(u):len(kiseki)-1]
if k<=len(kiseki)-(len(kuri)+1):
  print(kiseki[k])
else:
  K=k-(len(kiseki)-(len(kuri)+1))
  amari=K%len(kuri)
  print(kuri[amari])

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
kiseki=[-1]*n
i=0
v=1
while kiseki[v-1]==-1:
  kiseki[v-1]=i
  v=l[v-1]
  i+=1
saisyo=kiseki[v-1]
kuri=i-saisyo

if saisyo>k:
  print(kiseki.index(k)+1)
else:
  amari=(k-saisyo)%kuri
  print(kiseki.index(amari+saisyo)+1)
s = input()
if(s[2:3]==s[3:4] and s[4:5]==s[5:6]){print("Yes")}
else{print("No")}

### FIXED CODE ###

s = input()
if(s[2:3]==s[3:4] and s[4:5]==s[5:6]):
  print("Yes")
else:
  print("No")
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p =sorted(p)[::-1][:x][::-1]
q =sorted(q)[::-1][:y][::-1]
r =sorted(r)[::-1][:x+y]


pp = 0
qq = 0
for rr in r:
    if p[pp]<rr or q[qq]<rr:
        if p[pp]<q[qq]:
            p[pp] = rr
            pp += 1
        else:
            q[qq] = rr
            qq +=1

print(sum(p)+sum(q))

### FIXED CODE ###

x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p =sorted(p)[::-1][:x][::-1]
q =sorted(q)[::-1][:y][::-1]
r =sorted(r)[::-1][:x+y]

pp = 0
qq = 0
pf = True
qf = True
for rr in r:
    lll = False
    if pf == True and qf == True:
        if p[pp]<rr and q[qq]<rr:
            lll = True
            if p[pp]<q[qq] and pf == True:
                p[pp] = rr
                pp += 1
                if pp == x:
                    pf = False
            elif qf == True:
                q[qq] = rr
                qq +=1
                if qq == y:
                    qf = False
    if pf == True and lll == False:
        if p[pp]<rr:
            lll = True
            if pf == True:
               p[pp] = rr
               pp += 1
               if pp == x:
                  pf = False
    if qf == True and lll == False:
        if q[qq]<rr:
            lll = True
            if qf == True:
                q[qq] = rr
                qq +=1
                if qq == y:
                    qf = False

print(sum(p)+sum(q))
N,Q=map(int,input().split())
S=input()
out=''
for i in range(Q):
    l,r=map(int,input().split())
    out+=str(S[l-1:r].count('AC'))+'\n'
print(out[:-1])

### FIXED CODE ###

base = ['A', 'T', 'A', 'C', 'G', 'C']
str = input()
print(base[base.index(str) + 1])
l=[]
for i in range(5):
    l.append(int(input()))
indexn=10
indx=0
for v in range(5):
    if l[v]%10==0:
        pass
    else:
        if l[v]%10<indexn:
            indexn=l[v]%10
            indx=v
for k in range(5):
    if k!=indx:
        l[v]=((l[v]-1)//10+1)*10
    else:
        
print(sum(l))

### FIXED CODE ###

l=[]
for i in range(5):
    l.append(int(input()))
indexn=10
indx=0
for v in range(5):
    if l[v]%10==0:
        pass
    else:
        if l[v]%10<indexn:
            indexn=l[v]%10
            indx=v
for k in range(5):
    l[k]=((l[k]-1)//10+1)*10
        
print(sum(l)-10+indexn)
h1=input('>>')
m1=input('>>')
h2=input('>>')
m2=input('>>')
k=input('>>')
print('60*(h2-h1)+(m2-m1)-k')









### FIXED CODE ###

h1,m1,h2,m2,k=map(int,input().split())
s=60*(h2-h1)+(m2-m1)-k
print(s)
n,m = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7

import sys
sys.setrecursionlimit(100000)

dp = [-1]*(n+1)
dp[0] = 1
for i in para :
    dp[i] = 0

def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if dp[cnt] != 0 :  
                dp[cnt] = (dp[cnt-1] + dp[cnt-2]) % mod
                cnt += 1
            else :
                cnt += 1
        return dps(cnt,cantvisit)
dps(1,para)
print("{}".format(dp[-1]))

### FIXED CODE ###

n,m = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7
dp = [-1]*(n+1)
for i in para:
    dp[i] = 0
for i in range(n+1):
    if  dp[i] != 0 :
        if i == 1 or i==0:
            dp[i] = 1
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod



print("{}".format(dp[-1]))
l=map(int,input().split())
N=min(l)
M=max(l)
if N==1 and M==1:
  print(1)
elif N==1:
  print(M-2)
else:
  print((M-2)*(N-2))

### FIXED CODE ###

l=list(map(int,input().split()))
N=min(l)
M=max(l)
if N==1 and M==1:
  print(1)
elif N==1:
  print(M-2)
else:
  print((M-2)*(N-2))
N = input()
n=1
p=-1
for i in range(4):
    t= N % 10
    if p == t:
        n = n + 1
    p=t
    N = int(N / 10)
ans = "YES" if n >= 3 else "NO"
print(ans)

### FIXED CODE ###

N = int(input())
n=1
p=-1
for i in range(4):
    t= N % 10
    if p == t:
        n = n + 1
        if n == 3: break
    else:
        n = 1
    p=t
    N = int(N / 10)
ans = "Yes" if n == 3 else "No"
print(ans)
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
lsw=[0]*(k*2)
for i in range(n):
  a,b,c=input().split()
  a,b=int(a)%(k*2),int(b)%(k*2)
  if c=="B":
    b=(b+k)%(k*2)
  if a>=k:
    b=(b+k)%(k*2)
  lsw[b]+=1
ans=[sum(lsw[:k])]
for i in range(1,k+1):
  ans.append(ans[-1]+lsw[k+i]-lsw[i])
print(max(ans))

### FIXED CODE ###

n,k = map(int,input().split())
xyc = [list(input().split()) for i in range(n)]
for i in range(n):
  x,y,c = xyc[i]
  x = int(x)
  y = int(y)
  xq = x//k
  yq = y//k
  if (xq+yq)%2:
    if c == "B":
      c = "W"
    else:
      c = "B"
  x %= k
  y %= k
  xyc[i] = x,y,c
gridw = [[0 for i in range(k+1)] for j in range(k+1)]
gridb = [[0 for i in range(k+1)] for j in range(k+1)]
for x,y,c in xyc:
  x += 1
  y += 1
  if c == "B":
    gridb[x][y] += 1
  else:
    gridw[x][y] += 1
for grid in gridb,gridw:
  for i in range(1,k+1):
    for j in range(k+1):
      grid[i][j] += grid[i-1][j]
for grid in gridb,gridw:
  for i in range(k+1):
    for j in range(1,k+1):
      grid[i][j] += grid[i][j-1]
nw = gridw[-1][-1]
nb = gridb[-1][-1]
ans = 0
def sm(grid,i,j):
  return grid[i][j]+grid[-1][-1]-grid[-1][j]-grid[i][-1]+grid[i][j]
for i in range(k+1):
  for j in range(k+1):
    x = sm(gridb,i,j)+nw-sm(gridw,i,j)
    ans = max(ans,x,n-x)
print(ans)
k = int(input())
# s = input()
# s = len(s)
s = int(input())

mod = 10 ** 9 + 7
n = k + s


def _fac_inv(_n, _mod):
    _fac = [1] * (_n + 1)
    _inv = [1] * (_n + 1)
    for i in range(_n):
        _fac[i + 1] = _fac[i] * (i + 1) % _mod
    _inv[_n] = pow(_fac[_n], _mod - 2, _mod)
    for i in range(_n, 0, -1):
        _inv[i - 1] = _inv[i] * i % _mod

    return _fac, _inv


fac, inv = _fac_inv(n, mod)

n25 = [1]
n26 = [1]
for _ in range(n-s):
    n25.append((n25[-1] * 25) % mod)
    n26.append((n26[-1] * 26) % mod)

ans = 0

for i in range(s, n + 1):
    ans = (ans + fac[i-1] * inv[s-1] * inv[i-s] * n25[i-s] * n26[n-i]) % mod

print(ans)


### FIXED CODE ###

k = int(input())
s = input()
s = len(s)

mod = 10 ** 9 + 7
n = k + s


def _fac_inv(_n, _mod):
    _fac = [1] * (_n + 1)
    _inv = [1] * (_n + 1)
    for i in range(_n):
        _fac[i + 1] = _fac[i] * (i + 1) % _mod
    _inv[_n] = pow(_fac[_n], _mod - 2, _mod)
    for i in range(_n, 0, -1):
        _inv[i - 1] = _inv[i] * i % _mod

    return _fac, _inv


fac, inv = _fac_inv(n, mod)

n25 = [1]
n26 = [1]
for _ in range(n-s):
    n25.append((n25[-1] * 25) % mod)
    n26.append((n26[-1] * 26) % mod)

ans = 0

for i in range(s, n + 1):
    ans = (ans + fac[i-1] * inv[s-1] * inv[i-s] * n25[i-s] * n26[n-i]) % mod

print(ans)