Harryxun/stf_run huggingface dataset:
n,m=map(int,input().split())

g=[[] for i in range(n)]
memo=[-1 for i in range(n)]

for i in range(m):
 x,y=map(int,input().split())
 x-=1
 y-=1
 g[x].append(y)

def rec(x):
 if memo[x]!=-1:
  return memo[x]

 res=0
 for i in g[x]:
  res=max(res,rec(i)+1)

 memo[x]=res
 return res

ans=0
for v in range(n):
 ans=max(ans,rec(v))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

n,m=map(int,input().split())

g=[[] for i in range(n)]
memo=[-1 for i in range(n)]

for i in range(m):
 x,y=map(int,input().split())
 x-=1
 y-=1
 g[x].append(y)

def rec(x):
 if memo[x]!=-1:
  return memo[x]

 res=0
 for i in g[x]:
  res=max(res,rec(i)+1)

 memo[x]=res
 return res

ans=0
for v in range(n):
 ans=max(ans,rec(v))
print(ans)
N,A,B = map(int, [input() for i in range(3)])

def sum(n):
    str_n = str(n)
    ans = 0
    for i in range(len(str_n)):
        ans += int(str_n[i])
    return ans

ans1 = 0
for i in range(N+1):
    if A <= sum(i) <= B:
        ans1 += i
print(ans1)


### FIXED CODE ###

def sum(n):
    str_n = str(n)
    ans = 0
    for i in range(len(str_n)):
        ans += int(str_n[i])
    return ans

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

ans1 = 0
for i in range(N+1):
    if A <= sum(i) <= B:
        ans1 += i
    else:
        continue
print(ans1)
N=int(input())
list=[]
for i in range(N):
  A=int(input())
  list.append(A)
for j in range(N):
  del list[j]
  print(max(list))

### FIXED CODE ###

N=int(input())
list=[]
for i in range(N):
  A=int(input())
  list.append(A)
l=sorted(list,reverse=True)
A_1=l[0]
A_2=l[1]
for j in range(N):
  if list[j]!=A_1:
    print(A_1)
  else:
    print(A_2)
N = int(input())
l = (map(int,input().split()))
num = len(l)
l_first = min(l)
l_min = min(l)
x = l.index(l_min)

for _ in range(N):
    l = l[x:]
    if l_min+1 in l:
        l_min +=1
        x = l.index(l_min)
    else:
        break

if l_first == l_min:
    print(-1)
else:
    print(num-(l_min-l_first+1))

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
a = 1
for i in l:
    if a == i:
        a += 1
if a == 1:
    print(-1)
else:
    print(N-a+1)
a,b=input().split()
A=int(a)
B=float(b)
x=a*b//1
print(x)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
import math
n = int(input())
prev = 0
for i in range(n):
    if(i == 0):
        prev = int(input())
    else:
        t = int(input())
        prev = prev * t // math.gcd(prev, t)
print(prev)


### FIXED CODE ###

def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)
n = int(input())
prev = 1
for i in range(n):
        t = int(input())
        prev = prev * t // gcd(prev, t)
print(prev)
n = str(input())
ans = 0
for i in n: ans = (ans + int(i - '0')) % 9
if ans: print ("No")
else: print("Yes")



### FIXED CODE ###

n = str(input())
ans = 0
for i in range(len(n)):
	ans = (ans + ord(n[i]) - ord('0')) % 9
if ans: print("No")
else: print("Yes")
N = int(input())
A = list(map(int, input().split()))
A.sort()

'''
Anega = [a for a in A if a<0]
Azero = [a for a in A if a==0]
Aposi = [a for a in A if a>0]

if len(A) == len(Anega):
  print(-sum(A[:-1]) + A[-1])
  a = A[-1]
  for i in range(2,N+1):
    print(*(a, A[-i]))
    a = a - A[-i]
    
if len(A) == len(Aposi):
  print(sum(A[1:]) - A[0])
  a = A[0]
  for i in range(1,N-1):
    print(*(a, A[i]))
    a = a-A[i]
  print(*(A[-1],a))
  
if Azero:
  print(sum(Aposi)-sum(Anega))
  for _ in range(len(Azero)-1):
    print(*(0,0))
  a = 0
  for i in range(0,len(Aposi)-1):
    print(*(a, Aposi[i]))
    a = a-Aposi[i]
  print(*(Aposi[-1],a))
  a = Aposi[-1] -a
  
  for b in Anega:
    print(*(a,b))
    a = a-b
'''
        

      
      
Anega = [a for a in A if a<=0]
Aposi = [a for a in A if a>0]

if Anega:
  print(sum(Aposi)-sum(Anega))
  temp = Anega[-1]
  for a in Aposi[:-1]:
    print(*(temp,a))
    temp = temp-a
  print(*(Aposi[-1],temp))
  temp = Aposi[-1]-temp
  for a in Anega[:-1]:
    print(*(temp,a))
    temp = temp-a
    
  
else:
  print(sum(A[1:]) - A[0])
  a = A[0]
  for i in range(1,N-1):
    print(*(a, A[i]))
    a = a-A[i]
  print(*(A[-1],a))

### FIXED CODE ###

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

Anega = [a for a in A if a<=0]
Aposi = [a for a in A if a>0]

if Anega and Aposi:
  print(sum(Aposi)-sum(Anega))
  temp = Anega[-1]
  for a in Aposi[:-1]:
    print(*(temp,a))
    temp = temp-a
  print(*(Aposi[-1],temp))
  temp = Aposi[-1]-temp
  for a in Anega[:-1]:
    print(*(temp,a))
    temp = temp-a

elif Aposi:
  print(sum(A[1:]) - A[0])
  a = A[0]
  for i in range(1,N-1):
    print(*(a, A[i]))
    a = a-A[i]
  print(*(A[-1],a))

else:
  print(A[-1] - sum(A[:-1]))
  temp = A[-1]
  for a in A[:-1]:
    print(*(temp,a))
    temp = temp-a
N,K = map(int,input().split())
S = input()

for i in range(len(S)-1):
    if S[i] == S[i+1]:
        count += 1

print(min(N-1,count+2*K))

### FIXED CODE ###

N,K = map(int,input().split())
S = input()
count = 0

for i in range(len(S)-1):
    if S[i] == S[i+1]:
        count += 1

print(min(N-1,count+2*K))
def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(kouho)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x,-x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()
import sys
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int, input().split())
es = [[] for i in range(N+1)]
edge = [None] * M
h = [0] * (N+1)
for id in range(M):
    a, b = map(int, input().split())
    es[a].append([b, id])
    edge[id] = [a, b]
    h[a] += 1

def rev(v, p, t, visit):
    if v == t:
        return True
    visit[v] = 0
    for i, (u, id) in enumerate(es[v]):
        if u != -1 and visit[u] and rev(u, v, t, visit):
            es[v][i] = [-1, id]
            es[u].append([v, id])
            edge[id] = [u, v]
            h[v] -= 1
            h[u] += 1

ps, pt, s, t = 0, 1, 0, 0
while True:
    for v in range(t+1, N+1):
        if h[v] % 2:
            s = v
            break
    if s == ps:
        break
    for v in range(s+1, N+1):
        if h[v] % 2:
            t = v
            break
    if t == pt:
        print(-1)
        quit()
    rev(s, -1, t, [1] * (N+1))
    ps, pt = s, t
for u, v in edge:
    print(u, v)


### FIXED CODE ###

from heapq import *
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for id in range(M):
    a, b = map(int, input().split())
    es[a].append([b, id])
    es[b].append([a, id])
edge = [None] * M
h = [0] * (N+1)
lev = [None] * (N+1)
visit = [0] * (N+1)
def dfs(v, d):
    if visit[v]: return
    lev[v] = d
    visit[v] = 1
    for u, id in es[v]:
        if edge[id] == None:
            edge[id] = [v, u]
            h[v] ^= 1
            dfs(u, d+1)
dfs(1, 0)
q = [(-lev[v], v) for v in range(1, N+1)]
heapify(q)
while q:
    lv, v = heappop(q)
    lv = -lv
    if h[v] % 2 == 0: continue
    for u, id in es[v]:
        if lev[u] < lv:
            h[v] ^= 1
            h[u] ^= 1
            k, l = edge[id]
            edge[id] = [l, k]
            break
if h[1]:
    print(-1)
else:
    for u, v in edge:
        print(u, v)
n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

distance = [None] + [-1] * n

def bfs(u, d):
    pd = distance[u]
    if pd == -1 or d < pd:
        distance[u] = d
    for v in adj[u]:
        bfs(v, d + 1)


bfs(1, 0)

for i, d in enumerate(distance[1:], start=1):
    print(i, d)

### FIXED CODE ###

n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

isSearched = [None] + [False] * n

distance = [None] + [-1] * n

import collections

def bfs(u):
    isSearched[u] = True
    distance[u] = 0
    edge = collections.deque()
    edge.append(u)
    while edge:
        c_e = edge.popleft()
        for n_e in adj[c_e]:
            if not isSearched[n_e]:
                isSearched[n_e] = True
                distance[n_e] = distance[c_e] + 1
                edge.append(n_e)


bfs(1)

for i, x in enumerate(distance[1:], start=1):
    print(i, x)
N_List = sorted(list(map(int,input().split())))
print(sum(N_List[1:]-N_List[:-1]))

### FIXED CODE ###

import numpy as np
N_List = np.array(list(map(int,input().split())))
N_List_a = np.sort(N_List)
print(sum(N_List_a[1:]-N_List_a[:-1]))
n = int(input())
cnt = 0
for i in range(1,n):
  if len(i) == 1:
    cnt+=1
  elif len(i)>1 and len(i) % 2 != 0:
    cnt+=1
    
print(cnt)

### FIXED CODE ###

n=int(input())

i=1
cnt = 0 
while(i<=n):
	if i < 10 or (i >= 100 and i < 1000) or (i>=10000 and i<100000) :
		cnt+=1
		i+=1
	elif n == 100000:
		cnt  = 90909
		break
	elif len(str(i)) > 1:
		if i < 100:
			i = 100

		elif i >999 and i< 10000:
			i = 10000
	
print(cnt)
List=list(map(int,input().split()))
ans=-1
for x in range(5):
  if(List[x]==0):
    ans=x+1
  	break
print(ans)

### FIXED CODE ###

List=list(map(int,input().split()))
ans=-1
for x in range(5):
  if(List[x]==0):
    ans=x+1
    break
print(ans)
S=input()
s=list(S)

ans=0

for i in range(2**(len(s)-1)):
    judge=str(bin(i))[2:].rjust(len(s)-1,"0")
    sum=0
    plus=s[0]
    #print(judge)
    for j,jud in enumerate(judge):
        if jud=="0":
            plus+=s[j+1]
            #print(plus)
        else:
            sum+=int(plus)
            plus=""
            plus+=s[j+1]
    if len(plus)!=0:
        sum+=int(plus)
        #print(plus)
    #print(sum)
    ans+=sum
print(ans)

### FIXED CODE ###

S=input()
s=list(S)

ans=0

if len(S)!=1:
    for i in range(2**(len(s)-1)):
        judge=str(bin(i))[2:].rjust(len(s)-1,"0")
        sum=0
        plus=s[0]
        #print(judge)
        for j,jud in enumerate(judge):
            if jud=="0":
                plus+=s[j+1]
                #print(plus)
            else:
                sum+=int(plus)
                plus=""
                plus+=s[j+1]
        if len(plus)!=0:
            sum+=int(plus)
            #print(plus)
        #print(sum)
        ans+=sum
else:
    ans=int(S)
print(ans)
# (d1+d2)/2 == n1, (d2+d3)/2 == n2... が矛盾なくなるようにする
# にぶたんを使う
# なんかしらんけど3問駄目だな...

n = int(input())
dum = list(map(int, input().split()))
count = 0
l, r = 0, (10 ** 9 + 1000000) // 2

while True:
    mid = (l + r) // 2
    # print(l, r, mid)
    rain = [0 for _ in range(n)]
    rain[0] += mid * 2
    for i in range(1, n):
        next_amount = (dum[i - 1] - (rain[i - 1] // 2)) * 2
        rain[i] += next_amount
    # print(rain)

    if dum[-1] == (rain[-1] + rain[0]) // 2:
        for i in range(n):
          end = " " if i < n-1 else ""
          print(rain[i], end=end)
        print()
        exit()
    if (rain[0] + rain[-1]) // 2 < dum[-1]:
        # 最初に決めたやつが小さすぎた
        # print("{} は小さすぎた".format(rain[0]))
        l = mid + 1
    else:
        # 最初に決めたやつが大きすぎた
        # print("{} は大きすぎた".format(rain[0]))
        r = mid

    # セーフティネット 必要ないけど
    if count > 50:
        t = 5 / 0
        break
    count += 1

"""
7
110 50 53 50 11 36 88

11
38 7 15 15 9 31 23 1 5 55 81
"""


### FIXED CODE ###

# (d1+d2)/2 == n1, (d2+d3)/2 == n2... が矛盾なくなるようにする
# にぶたんを使う
# なんかしらんけど3問駄目だな...

n = int(input())
dum = list(map(int, input().split()))
count = 0
l, r = 0, (10 ** 10) // 2

while l < r:
    mid = (l + r) // 2
    # print(l, r, mid)
    rain = [0 for _ in range(n)]
    rain[0] += mid * 2
    for i in range(1, n):
        next_amount = (dum[i - 1] - (rain[i - 1] // 2)) * 2
        rain[i] += next_amount
    # print(rain)

    if dum[-1] == (rain[-1] + rain[0]) // 2:
        rain = list(map(str, rain))
        print(" ".join(rain))
        exit()
    if (rain[0] + rain[-1]) // 2 < dum[-1]:
        # 最初に決めたやつが小さすぎた
        # print("{} は小さすぎた".format(rain[0]))
        l = mid + 1
    else:
        # 最初に決めたやつが大きすぎた
        # print("{} は大きすぎた".format(rain[0]))
        r = mid

    # セーフティネット 必要ないけど
    if count > 50:
        t = 5 / 0
        break
    count += 1

"""
7
110 50 53 50 11 36 88

11
38 7 15 15 9 31 23 1 5 55 81
"""
N, R = map(int, input().split())
q = N/K
num = 0
while q >0:
  q = q / (K**num)
  num = num + 1
print(num)

### FIXED CODE ###

N, K = map(int, input().split())
num = 0
q = N
while q > 0:
	num = num + 1
	q = N // (K**num)
print(num)
a = int(input())
s = input()

if 3200 <= a:
    print(input(s))
if a <3200:
    print("red")

### FIXED CODE ###

a = int(input())
s = input()

if 3200 <= a:
    print(s)
if a < 3200:
    print("red")
import math
a,b,x=map(int,input().split())
x=x/a
c=b/2
if x<=a*c:
    d=2*x/b
    print(math.degrees(math.atan(b/d)))
else:
    x=a*b-x
    d=2*x/a
    print(90-math.degrees(math.atan(a/d)))

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
x=x/a
c=b/2
if x<=a*c:
    d=2*x/b
    print(round(math.degrees(math.atan(b/d)),10))
elif x==a*b:
    print(0)
else:
    x=a*b-x
    d=2*x/a
    print(round(90-math.degrees(math.atan(a/d)),10))
N,M = map(int, input().split())
words = [input() for i in range(N)]
words=words.sort()
for word in words:
  print(word,"")
  


### FIXED CODE ###

N, L = map(int, input().split())
S = sorted([input() for i in range(N)])

print(''.join(S))
n = int(input())
a,b = input().split()
for i in range(n):
    str += a[i]+b[i]
print(str)

### FIXED CODE ###

n = int(input())
a,b = input().split()
print(''.join([a[i]+b[i] for i in range(n)]))
S=input()

if S=="SUN":
    x=7
elif S=="MON":
    x=6
elif S=="TUE":
    x=5
elif S=="WED":
    x=4
elif S=="THU":
    x=3
elif S=="FRI":
    x=2
elif S=="STU":
    x=1
    
print(x)

### FIXED CODE ###

S=input()

if S=="SUN":
    x=7
elif S=="MON":
    x=6
elif S=="TUE":
    x=5
elif S=="WED":
    x=4
elif S=="THU":
    x=3
elif S=="FRI":
    x=2
elif S=="SAT":
    x=1
    
print(x)
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, As):
    import math
    x = math.ceil(math.log2(max(As)))
    ans = 0
    for i in range(x):
        count0 = 0
        count1 = 0
        for A in As:
            if (A >> i) % 2 == 0:
                count0 += 1
            else:
                count1 += 1
        # print(i, count0, count1)
        ans += count0 * count1 * (2 ** i)
        ans = ans % (10 ** 9 + 7)
    print(ans)


if __name__ == '__main__':
    N = int(input())
    As = [int(i) for i in input().split()]
    # N = 3 * 10 ** 5
    # import random
    # As = [random.randint(0, 2 ** 60) for _ in range(N)]
    solve(N, As)


### FIXED CODE ###

# 解説を参考に作成
# 提出 #14841909 を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, As):
    import math
    x = 1 if max(As) == 0 else math.ceil(math.log2(max(As)))
    ans = 0
    mod = 10 ** 9 + 7

    for i in range(x):
        cnt = sum((A >> i) % 2 for A in As)
        ans += (cnt * (N - cnt)) * pow(2, i, mod)
        ans = ans % mod
    print(ans)


if __name__ == '__main__':
    N = int(input())
    As = [int(i) for i in input().split()]
    # N = 3 * 10 ** 5
    # import random
    # As = [random.randint(2 ** 59, 2 ** 60) for _ in range(N)]
    solve(N, As)
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
H = [0]*10
dp = [(0,0)]*(N+1)
for a in A:
    if H[C[a]] < a:
        H[C[a]] = a
H = [ str(h) for h in H]
for a in A:
    dp[C[a]] = (1,0)
Z = sorted(list( set( [ C[a] for a in A])))
for i in range(2,N+1):
    for z in Z:
        if i >= z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
ans = ""
b = 1
s = N
while b != 0:
    a, b = dp[s]
    ans = H[s-b] + ans
    s = b
if int( ans[0]) < int( ans[-1]):
    ans = ans[::-1]
print( ans)


### FIXED CODE ###

N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if t-x>=0:
            if dp[t-x]+1 == dp[t]:
                W[V[x]] += 1
                t -= x
                break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)
S = input()
T = input()
count = 0
flg = False
while True:
    flg = False
    for i in range(1,len(T)+1):
        if S[-i-count] != T[-i] and S[-i-count] != '?':
            count += 1
            flg = True
            break
    if count == len(S) - len(T) + 1:
        print('UNRESTORABLE')
        exit()
    if not flg:
        if count == 0:
            ans = S[0:len(S)-len(T)] + T
        elif count == len(S)-len(T):
            ans = T + S[len(T):]
        else:
            ans = S[0:len(S)-len(T)-count] + T + S[-count:]
        print(ans.replace('?','a'))
        exit()

### FIXED CODE ###

S = input()
T = input()
count = 0
flg = False
if len(S) < len(T):
    print('UNRESTORABLE')
    exit()
while True:
    flg = False
    for i in range(1,len(T)+1):
        if S[-i-count] != T[-i] and S[-i-count] != '?':
            count += 1
            flg = True
            break
    if count == len(S) - len(T) + 1:
        print('UNRESTORABLE')
        exit()
    if not flg:
        if count == 0:
            ans = S[0:len(S)-len(T)] + T
        elif count == len(S)-len(T):
            ans = T + S[len(T):]
        else:
            ans = S[0:len(S)-len(T)-count] + T + S[-count:]
        print(ans.replace('?','a'))
        exit()
N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
X=[]
for s,t,x in STX:
    X.append((s-x,1,x))
    X.append((t-x,-1,x))
X.sort(key=lambda x:x[0])
a=0
k=[]
from bisect import bisect_left
for x in X:
    while D[a]<x[0]:
        if len(k)>0:
            print(k[0])
        else:
            print(-1)
        a+=1
    if x[1]==1:
        i=bisect_left(k,x[2])
        k.insert(i,x[2])
    else:
        i=bisect_left(k,x[2])
        del k[i]
while a<Q:
    print(-1)
    a+=1

### FIXED CODE ###

N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
X=[]
for s,t,x in STX:
    X.append((s-x,1,x))
    X.append((t-x,-1,x))
X.sort(key=lambda x:x[0])
a=0
k=[]
from heapq import heappop,heappush
kd={}
for x in X:
    while a<Q and D[a]<x[0]:
        if len(k)>0:
            print(k[0])
        else:
            print(-1)
        a+=1
    if x[1]==1:
        heappush(k,x[2])
        if x[2] in kd:
            kd[x[2]]=0
    else:
        kd[x[2]]=1
        while len(k)>0 and k[0] in kd and kd[k[0]]==1:
            heappop(k)
while a<Q:
    print(-1)
    a+=1
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), (c == 'W')
    p = (x / K + y / K + c) % 2
    DP[y % K + 1][x % K + 1] += -1 ** p
    bias += p

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

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S1 = DP[i][j] * 2 - DP[i][K] - DP[K][j] + DP[K][K]
        S2 = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S1, S2)

print ans + bias

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), (c == 'W')
    if (x / K + y / K + c) % 2 == 0:
        DP[y % K + 1][x % K + 1] += 1
    else:
        DP[y % K + 1][x % K + 1] -= 1
        bias += 1

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

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

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S1 = DP[i][j] * 2 - DP[i][K] - DP[K][j] + DP[K][K]
        S2 = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S1, S2)

print ans + bias
2 3 3
2 2
1 1
1 3


### FIXED CODE ###

from random import randint
import numpy as np
from numba import njit


#@njit
def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            if (ypsi,xpsi) in s:
                a -= 1
                ans = max(ans,a)
            else:
                return a
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)