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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	def power(x, y):
		if y == 0:
			return 1
		elif y == 1:
			return x
		elif y % 2 == 0:
			return power(x, int(y/2)) ** 2 % P
		else:
			return power(x, int((y-1)/2)) ** 2 * x % P

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		for i, s in enumerate(S[::-1]):
			tmp += power(10, i) * s
			mod_cnt[tmp%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()



### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	if P == 2 or P == 5:
		ans = 0

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		z = 1
		for i, n in enumerate(S[::-1]):
			tmp += n*z
			z = z * 10 % P
			mod_cnt[int(tmp)%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


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

import sys
from collections import deque
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

A.sort(reverse=True)
B.sort(reverse=True)

if len(set(A))!=len(A) or len(set(B))!=len(B):
    print(0)
    sys.exit()

x = N*M
def hantei(x, A, B):
    countB=0
    for i in B:
        if i>=x:
            countB+=1
    countA=0
    for i in A:
        if i>=x:
            countA+=1
    if x in A and x in B:
        return 1
    elif x in A and not x in B:
        return countB
    elif x in B and not x in A:
        return countA
    elif not(x in A or x in B):
        return countA*countB-(N*M-x)

ans = 1
for i in range(N*M,1,-1):
    ans *= hantei(i,A,B)

print(ans%(10**9+7))    


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

from collections import Counter

n = int(input())
aa = tuple(sorted(map(int, input().split())))
cnt = Counter(aa)

ans = 0
for i in range(n - 1, -1, -1):
    if cnt[aa[i]] > 1:
        continue

    f = True
    for j in range(i):
        if aa[i] < aa[j] * 2:
            break
        if aa[i] % aa[j] == 0:
            f = False
            break
    if f:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
aa = tuple(sorted(map(int, input().split())))
cnt = Counter(aa)
amax = max(aa)
af = [False] * (amax + 1)

ans = 0
for i in range(n):
    x = aa[i]
    if af[x]:
        continue
    while x <= amax:
        af[x] = True
        x += aa[i]
    if cnt[aa[i]] == 1:
        ans += 1

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

if mn*pn<k:
    l,r=0,max(a[0]*a[1],a[-1]*a[-2])
else:
    l,r=a[0]*a[-1],0
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(r if func(r) else l)


### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
a.sort()
p=a[a>0]
z=np.count_nonzero(a==0)
m=a[a<0]
r=10**19
l=-r
while r-l>1:
    # 区間[l,r]を半分に分けて探索。最終的にrが求める値になるようにする。
    # b以下のものがk個以上あるような、最小のbを求める。bを大きくする→b以下のものも増える。b以下のものがめちゃくちゃある→bを減らす。
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    # 配列aに対し、配列b//pの要素たちをそれぞれsearchsortedする。結果の配列はb//pと同じ形になる。
    c+=a.searchsorted(b//p,side='right').sum()
    # 配列aに対し、配列b//mの要素たちをそれぞれsearchsortedする。結果の配列はb//mと同じ形になる。
    c+=n*len(m)-a.searchsorted(-(-b//m),side='left').sum()
    c-=np.count_nonzero(a*a<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)
### BUGGY CODE ###

S = int(input())
x1, y1 = 0, 0
y2 = 0
x3 = 0
x2, y3 = 0, 0

for i in range(int(S ** 0.5), S + 1):
  x2 = i
  y3 = S // i
  if S % x2 == 0 and y3 <= 1000000000:
    break
print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))

### FIXED CODE ###

S = int(input())
MOD = 10 ** 9
x1, y1, x2, y2 = 0, 0, MOD, 1
y3 = S // MOD
if S % MOD != 0:
  y3 += 1
x3 = x2 * y3 - S

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
### BUGGY CODE ###

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

list_val = list(set(L))
list_size = [0]*N
for i,v in enumerate(list_val):
    list_size[i] = L.count(v)

max_size = max(list_size)
sorted_index = sorted(range(len(list_size)), key=lambda k: list_size[k], reverse=True)

ans = []
for s in sorted_index:
    if list_size[s] == max_size:
      ans.append(list_val[s])
    else:
      break
print("\n".join(sorted(ans)))


### FIXED CODE ###

import collections

N = int(input())

s = [input() for i in range(N)]

c = collections.Counter(s)
max_n = max(c.values())

ans = []
for key, val in c.items():
  if val == max_n:
    ans.append(key)
print("\n".join(sorted(list(set(ans)))))
### BUGGY CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N=int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for _ in [0]*N]

Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
Eb = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    for a0,a1 in zip(B[:-1],B[1:]):
        k0 = tuple(sorted((i,a0)))
        k1 = tuple(sorted((i,a1)))
        Ef[k0].append(k1)
        Eb[k1].append(k0)
Ef = {k:set(v) for k,v in Ef.items()}
Eb = {k:set(v) for k,v in Eb.items()}

q = [k for k in Eb if Eb[k] == set()]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            Eb[k2].remove(k)
            rmv += 1
            if not Eb[k2] : qq.append(k2)
        Ef[k] = set()
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()
### BUGGY CODE ###

import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
S = input()
T = input()

def lcs(s, t):
    dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])
        
lcs(S, T)

### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
S = input()
T = input()

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j+1])

    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])

        
lcs(S, T)
### BUGGY CODE ###

n=int(input())
l=sorted([int(i)for i in input().split()])
sum=0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i]+l[j]>l[k]:
                sum+=1
            else:
                break
print(sum)

### FIXED CODE ###

import bisect

n = int(input())
l = [int(i) for i in input().split()]
l.sort()

cnt = 0
for a in range(n):
    for b in range(a+1, n):
        c = bisect.bisect_left(l, l[a] + l[b])
        if c > b:
            cnt += c - b - 1
print(cnt)
### BUGGY CODE ###

import math

N = int(input())

if math.floor(math.log(N, 2)) == math.log(N, 2):
    print("No")
    exit()
else:
    print("Yes")

i = 1
print(N+1, N+2)
while i < N:
    if i+2 <= N:
        print(1, i+1)
        print(i+1, i+2)
        print(1, i+2+N)
        print(i+2+N, i+1+N)
        i += 2
    else:
        print(i-1, i+1)
        print(N+3, i+1+N)


### FIXED CODE ###

import math
 
N = int(input())
 
if math.floor(math.log(N, 2)) == math.log(N, 2):
    print("No")
    exit()
else:
    print("Yes")
 
i = 1
print(N+1, N+2)
for i in range(1, N, 2):
    if i+2 <= N:
        print(1, i+1)
        print(i+1, i+2)
        print(1, i+2+N)
        print(i+2+N, i+1+N)
    else:
        print(i-1, i+1)
        tmp = (i+1) ^ (i-1) 
        print(N+tmp+1, i+1+N)
### BUGGY CODE ###

import sys
N,K = map(int,sys.stdin.readline().split())
h = list(map(int,input().split()))
dp = [0]

for i in range(1,N):
  dp.append(min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)))
print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

import fractions
def lcm(a,b):
    return a*b//fractions.gcd(a,b)

def power(a,p):
    T=[a]
    while 2**(len(T))<p:
        T.append(T[-1]**2%p)
    b=bin(p-2)
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%p
    return ans   

l=A[0]
for i in range(n-1):
    l=lcm(l,A[i+1])
s=0
for i in range(n):
    s+=l*power(A[i],mod)%mod
    s%=mod
print(s)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

import fractions
def lcm(a,b):
    return a*b//fractions.gcd(a,b)

def power(a):
    T=[a]
    while 2**(len(T))<mod:
        T.append(T[-1]**2%mod)
    b=bin(mod-2)
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans   

l=A[0]
for i in range(n-1):
    l=lcm(l,A[i+1])
l%=mod
s=0
for i in range(n):
    s+=l*power(A[i])%mod
    s%=mod
print(s)
### BUGGY CODE ###

def main():
    X, K, D = list(map(int, input().split()))
    for i in range(K):
        if abs(X - D) > abs(X + D):
            X = X + D
        else:
            X = X - D
            if X <= 0:
                if (i % 2 == 1 and K % 2 == 0) or (i % 2 == 0 and K % 2 == 1):
                    print(abs(X))
                    return
                else:
                    if abs(X - D) < X:
                        print(abs(X - D))
                        return
                    elif abs(X + D) < X:
                        print(abs(X + D))
                        return
    print(abs(X))
main()


### FIXED CODE ###

def main():
    X, K, D = list(map(int, input().split()))
    
    def sgn(X):
        if X > 0:return 1
        if X < 0:return -1
        return 0
    
    if X > 0:
        x_greedy = X - K * D
    else:
        x_greedy = X + K * D
    
    if sgn(X) == sgn(x_greedy):
        print(abs(x_greedy))
        return
    
    x_r = X % D
    x_l = x_r - D

    r_parity = (abs(X - x_r) // D) % 2
    
    if K%2 == r_parity:
        print(abs(x_r))
    else:
        print(abs(x_l))
main()
### BUGGY CODE ###

import heapq
n,m=map(int,input().split())
c=[]
for i in range(n):
    a,b=map(int,input().split())
    c.append([a,-b])
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(n):
        if c[j][0]==i:
            heapq.heappush(d,c[j][1])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)  

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
c=[[] for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(len(c[i])):
        heapq.heappush(d,c[i][j])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)
### BUGGY CODE ###

import numpy as np


len_arr = int(input())
arr = np.array(list(map(int, input().split())))

ans = 0
for i in arr:
    mods = np.mod(i, arr)
    num_zeros = np.count_nonzero(mods == 0)
    ans += (num_zeros == 1)

print(ans)


### FIXED CODE ###

import numpy as np
from collections import Counter


len_arr = int(input())
arr = list(map(int, input().split(' ')))
counter = Counter(arr)
x_max = max(counter.keys())

dp = np.empty(x_max+1, dtype=np.bool_)
dp[:] = True

ans = 0

for x, count in sorted(counter.items()):
    multi = [x*y for y in range(1, x_max//x+1)]
    if count == 1 and dp[x]:
        ans += 1
    dp[multi] = False

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():

    N = int(input())

    a_l = [0] * N

    nums = list(map(int, input().split()))

    for i in nums:
        a_l[i-1] += 1

    for i in nums:
        a_l[i-1] -= 1
        total = 0
        for j in a_l:
            if j > 1:
                total += cmb(j,2)
        print(total)
        a_l[i-1] += 1




if __name__ == '__main__':
    main()

### FIXED CODE ###

def cmb(n):
    return int(n * (n-1) / 2)

def main():

    N = int(input())

    a_l = [0] * N

    nums = list(map(int, input().split()))
    for i in nums:
        a_l[i-1] += 1

    total = 0
    for j in a_l:
        if j > 1:
            total += cmb(j)

    for k in nums:
        if a_l[k-1] > 1:
            print(total - cmb(a_l[k-1]) + cmb(a_l[k-1] - 1))
        else:
            print(total)


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

# https://atcoder.jp/contests/abc113/tasks/abc113_c

N, M = map(int, input().split())
c_l = [list(map(int, input().split())) for _ in range(M)]

dict = {}

for c in c_l:
    if c[0] in dict:
        dict[c[0]].append(c[1])
    else:
        dict[c[0]] = [c[1]]


for k, v in dict.items():
    v.sort()

# print(dict)

for c in c_l:
    idx = dict[c[0]].index(c[1]) + 1
    print("{:06}{:06}".format(c[0], idx))






### FIXED CODE ###

# https://atcoder.jp/contests/abc113/tasks/abc113_c

N, M = map(int, input().split())
c_l = [[int(i) for i in input().split()] + [j] for j in range(M)]

# print(c_l)
c_l.sort(key=lambda x: x[1])

counter = [0] * (N+1)
for c in c_l:
    p = c[0]
    counter[p] += 1
    c.append("{:06}{:06}".format(c[0], counter[p]))

c_l.sort(key=lambda x: x[2])

for c in c_l:
    print(c[3])
### BUGGY CODE ###

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

for i in range(n):
    if p[i] <= min(p[:i+1]):
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
min = p[0]

for i in range(n):
    if p[i] <= min:
        ans += 1
        min = p[i]

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

from bisect import bisect, bisect_left
N = int(input())
A = list(map(int, input().split()))
A_ = sorted(list(set(A)))
A = sorted(A)
ans = 0
i = 0
while i < len(A_):
  a = A_[i]
  j = bisect_left(A_, a*2)
  while j < len(A_):
    if A_[j] % a == 0:
      A_.pop(j)
    else:
      j += 1
  if bisect(A, a)-bisect_left(A, a) > 1:
    ans -= 1
  i += 1
print(ans+len(A_))



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = max(A)
memo = [0]*(M+1)
i = 0
while i < N:
  a = A[i]
  memo[a] += 1
  x = a+a
  while x <= M:
    memo[x] += 2
    x += a
  i += 1
print(sum([1 if m == 1 else 0 for m in memo]))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2 * 10**6)


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


def dfs(v=0, c=0):
    if visited[v] is True:
        return
    visited[v] = True
    c += counter[v]
    ans[v] = c
    for nv in edge[v]:
        dfs(nv, c)
    return


N, Q = inpl()
AB = [inpl() for i in range(N - 1)]
PQ = [inpl() for i in range(Q)]

edge = [[] for i in range(N)]
for a, b in AB:
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
counter = {k: 0 for k in range(N)}
for p, q in PQ:
    counter[p - 1] += q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

dfs()

print(" ".join(list(map(str, ans))))


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


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


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

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

import sys
input = sys.stdin.readline

INF = float("inf")


class Acc2D:
    def __init__(self, grid):
        self.h, self.w = len(grid), len(grid[0])
        self.acc2D = self._build(self.h, self.w, grid)

    def _build(self, h, w, grid):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + grid[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        if r1 < 0:
            r1 = 0
        if r2 >= self.h:
            r2 = self.h
        if c1 < 0:
            c1 = 0
        if c2 >= self.w:
            c2 = self.w
        cnt = self.acc2D
        return cnt[r2][c2] - cnt[r1][c2] - cnt[r2][c1] + cnt[r1][c1]


def main():
    n, k = map(int, input().split())
    g = [[0] * (2 * k) for _ in range(2 * k)]
    for _ in range(n):
        x, y, c = input().split()
        x = int(x) % (2 * k)
        y = int(y) % (2 * k)
        if c == 'B':
            y = (y + k) % (2 * k)
        g[y][x] += 1
    acc2d = Acc2D(g)
    ans = 0
    for r in range(k):
        for c in range(k):
            tmp = acc2d.get(0, r, 0, c)
            tmp += acc2d.get(0, r, c + k, c + k * 2)
            tmp += acc2d.get(r, r + k, c, c + k)
            tmp += acc2d.get(r + k, r + k * 2, 0, c)
            tmp += acc2d.get(r + k, r + k * 2, c + k, c + k * 2)
            ans = max(ans, tmp, n - tmp)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float("inf")


class Acc2D:
    def __init__(self, grid):
        self.h, self.w = len(grid), len(grid[0])
        self.acc2D = self._build(self.h, self.w, grid)

    def _build(self, h, w, grid):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + grid[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        if r1 < 0:
            r1 = 0
        if r2 >= self.h:
            r2 = self.h
        if c1 < 0:
            c1 = 0
        if c2 >= self.w:
            c2 = self.w
        cnt = self.acc2D
        return cnt[r2][c2] - cnt[r1][c2] - cnt[r2][c1] + cnt[r1][c1]


def main():
    n, k = map(int, input().split())
    g = [[0] * (2 * k) for _ in range(2 * k)]
    for _ in range(n):
        x, y, c = input().split()
        x = int(x) % (2 * k)
        y = int(y) % (2 * k)
        if c == 'B':
            y = (y + k) % (2 * k)
        g[y][x] += 1
    acc2d = Acc2D(g)
    ans = 0
    for r in range(k):
        for c in range(k):
            tmp = acc2d.get(0, r, 0, c)
            tmp += acc2d.get(0, r, c + k, c + k * 2)
            tmp += acc2d.get(r, r + k, c, c + k)
            tmp += acc2d.get(r + k, r + k * 2, 0, c)
            tmp += acc2d.get(r + k, r + k * 2, c + k, c + k * 2)
            ans = max(ans, tmp, n - tmp)
    print(ans)


if __name__ == '__main__':
    main()