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

import sys
input = sys.stdin.readline

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        t = self.one
        while l < r:
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            if r & 1:
                r -= 1
                t = self.func(self.b[r - 1], t)
            l >>= 1
            r >>= 1
        return self.func(s, t)


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))
### BUGGY CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    memo[num] += 1
    t *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

### FIXED CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    t *= 10
    t %= 2019
    memo[num] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

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

s=list(input())
l=[0]*2019
t=0
ans=0
for i in range(len(s)):
    t=(t+(10**i)*int(s[-1-i]))%2019
    l[t]+=1
for i in l:
    ans+=(i*(i-1))//2
print(ans+l[0])

### FIXED CODE ###

s=list(input())
l=[0]*2019
t=0
ans=0
for i in range(len(s)):
    t=(t+pow(10,i,2019)*int(s[-1-i]))%2019
    l[t]+=1
for i in l:
    ans+=(i*(i-1))//2
print(ans+l[0])
### BUGGY CODE ###


# -*- coding: utf-8 -*-
import numpy as np
N=int(input())
As=list(map(int, input().split()))

As=np.array(As)
inds=np.argsort(As)[::-1]
As=As[inds]

ds=np.empty((N+1,N+1),dtype=int)

ds[0][0]=0
for i in range(1,N+1):
    ds[i][0]=ds[i-1][0]+As[i-1]*(inds[i-1]-(i-1))
    ds[0][i]=ds[0][i-1]+As[i-1]*(N-i-inds[i-1])

for xy in range(2,N+1):
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1,y]+As[xy-1]*(inds[xy-1]-(x-1))
        c2=ds[x,y-1]+As[xy-1]*(N-y-inds[xy-1])
        ds[x,y]=max(c1,c2)

ans=0
for x in range(0,N+1):
    y=N-x
    c=ds[x,y]
    ans=max(c,ans)
print(ans)
#print(ds)
#print(inds)




### FIXED CODE ###


# -*- coding: utf-8 -*-

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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1]
    a=As[i]
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print(max(ds))
#print(ds)
#print(inds)
### BUGGY CODE ###

h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=[]
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot.append([x,y])
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
u=0
c=0
for i in a:
    for j in b:
        if [i,j] in plot:
            u+=1
        c+=1
ans=x+y
if u==c:
    print(ans-1)
else:
    print(ans)                


### FIXED CODE ###

h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=set()
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot.add((x,y))
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
ans=x+y-1
c=False
for i in a:
    for j in b:
        if (i,j) not in plot:
          c=True
          break
    if c:
      break
if c:
  print(ans+1)
else:
  print(ans)
### BUGGY CODE ###

import sys

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

l = [1]
n = 1
while True:
    n = A[n-1]
    if n in l:
        mod = len(l) - l.index(n)
        init_len = l.index(n)
        break
    else:
        l.append(n)

if K < init_len:
    print(l[K])
else:
    rest = ((K-init_len) % mod)
    print(l[init_len+rest])


### FIXED CODE ###

import sys

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

i = 1
l = [1] * N
s = set([1])
n = 1
while True:
    n = A[n-1]
    if n in s:
        l = l[:i]
        mod = i - l.index(n)
        init_len = l.index(n)
        break
    else:
        l[i] = n
        s.add(n)
        i += 1

if K < init_len:
    print(l[K])
else:
    rest = ((K-init_len) % mod)
    print(l[init_len+rest])
### BUGGY CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
import math
import numpy as np
dp=np.zeros((n+1,s+1),int)
# dp[i][j]:aの中からi個選んでjにできるものの個数。
dp[0][0]=1
for ai in a:
  if ai>s:
    continue
  for j in range(n,0,-1):
    dp[j][ai:]+=dp[j-1][:-ai]
ans=0
for i in range(n+1):
  ans+=dp[i][s]*pow(2,n-i,mod)
  ans%=mod
print(ans)  



### FIXED CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
import numpy as np
dp=np.zeros((n+1,3001),int)
# dp[j]:総和がjになるようにできる空でない部分集合の個数。
dp[0][0]=1 # 遷移用、実際は0

for i in range(n):
  dp[i+1]+=dp[i]*2
  dp[i+1,a[i]:]+=dp[i,:-a[i]]
  dp[i+1]%=mod
print(dp[n][s])

#print(dp)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
S = S.replace('AC', 'ac')

LR = [list(map(int, input().split())) for _ in range(Q)]

for lr in LR:
    l, s = lr[0], lr[1]
    string = S[l - 1:s]
    print(string.count('ac'))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
S = S.replace('AC', 'ac')
ans = [0] * N
LR = [list(map(int, input().split())) for _ in range(Q)]

flag = False
count = 0
for num, s in enumerate(S):
    if flag is False:
        if s == 'a':
            flag = True
            ans[num] = count
            continue
        else:
            ans[num] = count
    else:
        if s == 'c':
            count += 2
            ans[num] = count
            flag = False
            continue
        else:
            ans[num] = count
            flag = False

for lr in LR:
    l, s = lr[0], lr[1]
    print((ans[s - 1] - ans[l - 1]) // 2)
### BUGGY CODE ###

from bisect import bisect_right

n,m = map(int,input().split())
aa = list(map(int,input().split()))
aa = sorted(aa)

for i in range(m):
  tmp = aa[-1]//2
  aa.pop()
  pos = bisect_right(aa,tmp)
  aa.insert(pos,tmp)
  
print(sum(aa))  

### FIXED CODE ###

# dequeにinsert追加されたのは 3.5 から
from heapq import heappop,heappush,heapify
n,m = map(int,input().split())
aa = list(map(int,input().split()))
aa = list(map(lambda x:-x,aa))

heapify(aa)
for i in range(m):
  tmp = heappop(aa)  
  heappush(aa,-(-tmp//2))

print(-sum(aa))
### BUGGY CODE ###

MOD = 998244353

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

dp = [[0] * (S + 1) for i in range(N)]
dp[0][0] = 2
if A[0] < S + 1:
	dp[0][A[0]] = 1

for i in range(1, N):
	for j in range(S + 1):
		dp[i][j] = (2 * dp[i - 1][j]) % MOD
		if 0 <= j - A[i] <= S:
			dp[i][j] = (dp[i][j] + dp[i - 1][j - A[i]]) % MOD
print(dp[-1][-1])


### FIXED CODE ###

MOD = 998244353

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

dp = [[0] * (S + 1) for i in range(N)]
dp[0][0] = 2
if A[0] < S + 1:
	dp[0][A[0]] = 1

for i in range(1, N):
	for j in range(S + 1):
		dp[i][j] = (2 * dp[i - 1][j]) % MOD
		if 0 <= j - A[i] <= S:
			dp[i][j] = (dp[i][j] + dp[i - 1][j - A[i]]) % MOD
print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if abs(i - j) == a[i] + a[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
L_dict, R_dict = {}, {}
i = 0
for ipt in input().split():
    try:
        L_dict[i + int(ipt)] += 1
    except KeyError:
        L_dict[i + int(ipt)] = 1
    try:
        R_dict[i - int(ipt)] += 1
    except KeyError:
        R_dict[i - int(ipt)] = 1
    i += 1
cnt = 0
for Lk, Lv in L_dict.items():
    try:
        cnt += R_dict[Lk] * Lv
    except KeyError:
        pass
print(cnt)
### BUGGY CODE ###

N=int(input())
A =list(map(int,input().split()))
for i in range(N):
  print(A.count(i+1))
  


### FIXED CODE ###

N =int(input())
A =list(map(int,input().split()))
l =[0]*N
for i in A:
  l[i-1]+=1
print(*l,sep="\n")
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    ans += A[i]*A[j]
print(ans % (10**9+7))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
L = [0]*(n+1)
ans = 0
for i in range(n):
  L[i+1] = L[i]+A[i]
for i in range(1,n):
  ans += L[i]*A[i]
print(ans % (10**9+7))
### BUGGY CODE ###

# これは, u749194f さんの改造です。
# オリジナルではございません。
# https://atcoder.jp/contests/abc162/submissions/11825963
n = int(input())
s = input()
flag = True
if len(set(s))<=2:
    print(0)
    flag = False
if flag:
    r = [i+1 for i in range(n) if s[i]=='R']
    b = [i+1 for i in range(n) if s[i]=='B']
    g = [i+1 for i in range(n) if s[i]=='G']
    minus = 0
    def cnt_cmb(a, b, c):
        cnt = 0
        for i in a:
            for j in b:
                if (i+j)/2 in c:
                    cnt += 1
        return cnt
    minus += cnt_cmb(r, b, g)
    minus += cnt_cmb(b, g, r)
    minus += cnt_cmb(g, r, b)
    print(len(r)*len(b)*len(g)-minus)

### FIXED CODE ###

from collections import Counter
# これは, u749194f さんの改造です。
# オリジナルではございません。
# https://atcoder.jp/contests/abc162/submissions/11825963
n = int(input())
s = input()
flag = True
if len(set(s))<=2:
    print(0)
    flag = False
if flag:
    r = [i+1 for i in range(n) if s[i]=='R']
    b = [i+1 for i in range(n) if s[i]=='B']
    g = [i+1 for i in range(n) if s[i]=='G']
    minus = 0
    def cnt_cmb(a, b, c):
        cnt = 0
        set_c = set(c)
        for i in a:
            for j in b:
                if (i+j)/2 in set_c:
                    cnt += 1
        return cnt
    minus += cnt_cmb(r, b, g)
    minus += cnt_cmb(b, g, r)
    minus += cnt_cmb(g, r, b)
    a = Counter(s)
    rslt = 1
    for value in a.values():
        rslt *= value
    print(len(r)*len(b)*len(g)-minus)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
if ans > (10**18):
    ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    b*=a[i]
    if b>10**18:
        print(-1)
        exit()
print(b)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, u = na()
d = []
for i in range(u):
    d.append(na())

c = []
for i in range(n):
    c.append(na())

for i in range(n):
    for j in range(n):
        c[i][j] -= 1

fs = []
for i in range(u):
    f = [0]*3
    for j in range(n):
        for k in range(n):
            f[(j+k)%3] += d[c[j][k]][i]
    fs.append(f)

ans = 99999999999999999
for i in range(u):
    for j in range(u):
        for k in range(u):
            if i == j or j == k or k == i: continue

            ans = min(ans, fs[i][0] + fs[j][1] + fs[k][2])
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, u = na()
d = []
for i in range(u):
    d.append(na())

c = []
for i in range(n):
    c.append(na())

for i in range(n):
    for j in range(n):
        c[i][j] -= 1

fs = []
for i in range(u):
    f = [0]*3
    for j in range(n):
        t = j%3
        for k in range(n):
            f[t] += d[c[j][k]][i]
            t += 1
            if t == 3:
                t = 0
    fs.append(f)

ans = 99999999999999999
for i in range(u):
    for j in range(u):
        for k in range(u):
            if i == j or j == k or k == i: continue

            ans = min(ans, fs[i][0] + fs[j][1] + fs[k][2])
print(ans)
### BUGGY CODE ###

N = int(input())
dic = [[-1]*(N+1) for _ in range(N+1)]
M = [[] for _ in range(N+1)]
used = [-1]*(N+1) 
for i in range(N-1):
    u,v,w = map(int,input().split())
    M[u-1].append([v-1,w])
    M[v-1].append([u-1,w])


# from collections import deque 
q = []
q.append([0,0])
used[0] = 0
# print(M)
while q:
    # print(q)
    e,c = q.pop()
    for i,d in M[e]:
        if used[i]==-1:
            C = (c+d)%2
            used[i] = C
            q.append([i,C])  
for i in used[:-1]:
    print(i)


### FIXED CODE ###

n = int(input())
from collections import deque
#隣接リストedge
edge = [[] for i in range(n)]
d = [-1] * n
#入力
for i in range(n-1):
    x,y,cost = map(int,input().split())
    #edge[x].append([cost,y])
    #edge[y].append([cost,x])
    x -=1
    y -=1
    cost %=2
    edge[x].append((cost,y))
    edge[y].append((cost,x))
q = deque()
q.append(0)
d[0] =0
while q:
    t = q.popleft()
    for s in edge[t]:
        if d[s[1]] == -1:
            d[s[1]] = d[t] + s[0]
            q.append(s[1])
for i in d:
    print(i%2)
### BUGGY CODE ###

n,x,y = map(int,input().split())
ans={i:[] for i in range(1,n)}
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[min(abs(i-j),min(abs(i-x)+1+abs(j-y),abs(i-y)+1+abs(j-x)))].append([i,j])
for i in range(1,n):
    print(len(ans[i]))

### FIXED CODE ###

n,x,y = map(int,input().split())
ans=[0]*n
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(i-x)+1+abs(j-y))]+=1
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    h,w,D = LI()
    a = LIR(h)
    d = defaultdict(int)
    for y in range(h):
        for x in range(w):
            d[a[y][x]] = y*w+x
    n = h*w
    dist = [[0 for i in range(n+1)] for i in range(D)]
    for i in range(1,n-D+1):
        y = d[i]//w
        x = d[i]%w
        y_ = d[i+D]//w
        x_ = d[i+D]%w
        k = i%D
        j = i//D
        dist[k][j+1] = dist[k][j]+abs(y_-y)+abs(x_-x)
    q = I()
    for i in range(q):
        l,r = LI()
        k = l%D
        print(dist[k][r//D]-dist[k][l//D])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    h,w,D = LI()
    a = LIR(h)
    d = defaultdict(int)
    for y in range(h):
        for x in range(w):
            d[a[y][x]] = y*w+x
    n = h*w
    dist = [[0 for i in range(n//D+1)] for i in range(D)]
    for i in range(1,n-D+1):
        y = d[i]//w
        x = d[i]%w
        y_ = d[i+D]//w
        x_ = d[i+D]%w
        k = i%D
        j = i//D
        dist[k][j+1] = dist[k][j]+abs(y_-y)+abs(x_-x)
    q = I()
    for i in range(q):
        l,r = LI()
        k = l%D
        print(dist[k][r//D]-dist[k][l//D])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)

### FIXED CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)
### BUGGY CODE ###

import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            shortest[i][j] = min(j-i, abs(X-i)+1+abs(j-Y))

    coll = [collections.Counter(s) for s in shortest]
    for i in range(1,N):
        count = 0
        for j in range(N):
            count += coll[j].get(i,0)
        print(count)
main()


### FIXED CODE ###

import collections
def main():
    N,X,Y = map(int, input().split())
    # 扱いやすいようにX,Yはインデックス表記にしておく
    X -= 1
    Y -= 1
    # i<jを満たす(i,j)について6通りの場合分けして全最短距離を求められる
    shortest = [[-1]*N for _ in range(N)]
    coll = collections.Counter()
    for i in range(N):
        k1 = abs(X-i)
        for j in range(i+1,N):
            k2 = abs(j-Y)
            shortest[i][j] = min(j-i, k1+1+k2)
        coll += collections.Counter(shortest[i])

    for i in range(1,N):
        print(coll.get(i,0))
        
main()
### BUGGY CODE ###

def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,n//i+1):
        l[i*j] = 0
  return l


while True:
  n = int(input())
  if n == 0:
    break
  l = primes(n)
  count = 0
  for i in range(2,n//2+1):
    if (l[i] and l[n-i]):
      count += 1
  print(count)

### FIXED CODE ###

def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,n//i+1):
        l[i*j] = 0
  return l

l = primes(50000)
while True:
  n = int(input())
  if n == 0:
    break
  count = 0
  if not(n%2):
    for i in range(3,n//2+1,2):
      if (l[i] and l[n-i]):
        count += 1
    if n == 4:
      count = 1
  else:
    if l[n-2]:
      count += 1
  print(count)
### BUGGY CODE ###

s = input()
q = int(input())
ans = s
for i in range(q):
    tmp = input()
    if tmp[0] == "1":
        ans = ans[::-1]
    else:
        _, f, c = map(str, tmp.split())
        ans = (c + ans) if f == "1" else (ans + c)
print(ans)

### FIXED CODE ###

s = input()
q = int(input())
count = 0
top = ""
end = ""
ans = s
for i in range(q):
    tmp = input()
    if tmp[0] == "1":
        count += 1
    else:
        _, f, c = map(str, tmp.split())
        if count % 2 == 0:
            if f == "1":
                top = c + top
            else:
                end = end + c
        else:
            if f == "1":
                end = end + c
            else:
                top = c + top

ans = top + ans + end
ans = ans[::-1] if count % 2 == 1 else ans
print(ans)
### BUGGY CODE ###

def main():
    sc = iter(open(0).read().split())
    ni = lambda: int(next(sc))
    ns = lambda: next(sc)

    N, K = ni(), ni()

    K2 = K * 2
    A = [[0] * K2 for _ in range(K2)]
    for _ in range(N):
        x, y, c = ni(), ni(), ns()
        if c == "W":
            y += K
        A[y % K2][x % K2] += 1

    S = [[0] * (K2 + 1) for _ in range(K2 + 1)]
    for i in range(K2):
        for j in range(K2):
            S[i + 1][j + 1] = (
                A[i][j]
                + S[i + 1][j]
                + S[i][j + 1]
                - S[i][j]
            )

    ans = 0
    for i in range(K, K2 + 1):
        for j in range(K, K2 + 1):
            res = (
                S[i][j] + S[i - K][j - K] - S[i - K][j] - S[i][j - K]
                + S[i - K][j - K]
                + S[K2][j - K] - S[i][j - K]
                + S[i - K][K2] - S[i - K][j]
                + S[K2][K2] + S[i][j] - S[i][K2] - S[K2][j]
            )
            ans = max(ans, res, N - res)

    print(ans)

main()

### FIXED CODE ###

sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, K = ni(), ni()

K2 = K * 2
A = [[0] * K2 for _ in range(K2)]
for _ in range(N):
    x, y, c = ni(), ni(), ns()
    if c == "W":
        y += K
    A[y % K2][x % K2] += 1

S = [[0] * (K2 + 1) for _ in range(K2 + 1)]
for i in range(K2):
    for j in range(K2):
        S[i + 1][j + 1] = (
            A[i][j]
            + S[i + 1][j]
            + S[i][j + 1]
            - S[i][j]
        )

ans = 0
for i in range(K, K2 + 1):
    for j in range(K, K2 + 1):
        res = (
            S[i][j] + S[i - K][j - K] - S[i - K][j] - S[i][j - K]
            + S[i - K][j - K]
            + S[K2][j - K] - S[i][j - K]
            + S[i - K][K2] - S[i - K][j]
            + S[K2][K2] + S[i][j] - S[i][K2] - S[K2][j]
        )
        ans = max(ans, res, N - res)

print(ans)