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

import heapq
K=int(input())
G=[[(1,(i+1)%K)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((0,a))
stack=list(G[1])
heapq.heapify(stack)
reached=[0]*K
reached[1]=1
while(stack):
    c,g=heapq.heappop(stack)
    if g==0:
        print(c+1)
        quit()
    reached[g]=1
    for i in G[g]:
        if reached[i[1]]:
            continue
        heapq.heappush(stack,(c+i[0],i[1]))


### FIXED CODE ###

import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)
### BUGGY CODE ###

from math import sqrt, ceil
import fractions
A, B = map(int, input().split())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


ans = 1
for i in range(2, fractions.gcd(A, B)+1):
    if i > 2 and i % 2 == 0:
        continue
    if A % i == 0 and B % i == 0:
        prime = is_prime(i)
        if prime:
            ans += 1

print(ans)


### FIXED CODE ###

from math import sqrt, ceil
import fractions
A, B = map(int, input().split())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors


ans = 1

tmp = make_divisors(fractions.gcd(A, B))

for x in tmp:
    if is_prime(x):
        ans += 1

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

import itertools
import collections


def a_prime_factor_table(n):
    table = [0] * (n + 1)

    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i

    return table


def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()

    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1

    return prime_count

def num_divisors(prime_count):
    num = 1

    for prime, count in prime_count.items():
        num *= (count + 1)

    return num

N = int(input())
ans = 0
table = a_prime_factor_table(N)
for num in range(1,N+1):
    if num == 1:
        ans += 1
        continue
    a = prime_factor(num,table)

    ans += num*num_divisors(a)
print(ans)

### FIXED CODE ###

def num_divisors_table(n):
    table = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1

    return table
N = int(input())
table = num_divisors_table(N)
ans = 0
for i in range(1,N+1):
    ans += i*table[i]
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
pre_max = max(a)

for i in range(n):
  if pre_max != a[i]:
    print(pre_max)
  else:
    copy_a = copy.copy(a)
    copy_a.pop(i)
    print(max(copy_a))
  

### FIXED CODE ###

import copy
n = int(input())
a = [int(input()) for i in range(n)]
sorted_a = sorted(a, reverse=True)
n1 = sorted_a[0]
n2 = sorted_a[1]
if(n1 == n2):
  for i in range(n):
    print(n1)
else:
  for i in range(n):
    if a[i] == n1:
      print(n2)
    else:
      print(n1)
### BUGGY CODE ###

S = input()

Sr = S.split('L')
R_max = len(max(Sr,key=len))
Sl = S.split('R')
L_max = len(max(Sl,key=len))

Sc = [1] * len(S)
Sc_ = [0] * len(S)

S_try = max(L_max,R_max)
if S_try % 2 == 1:
    S_try += 1

for n in range(S_try):
    for i in range(len(S)):
        if S[i] == 'L':
            Sc_[i - 1] += Sc[i]
        elif S[i] == 'R':
            Sc_[i + 1] += Sc[i]
    Sc = Sc_[:]
    Sc_ = [0] * len(S)

print(" ".join(map(str,Sc)))



### FIXED CODE ###

import copy
S = input()
Slen = len(S)

Sc=[0]*Slen
for i in range(Slen):
    if S[i:i+2] == 'RL':
        for j in range(i,-1,-1):
            if S[j]=='R':
                Sc[(i-j)%2 + i] += 1
            else:
                break
        for j in range(i+1,Slen):
            if S[j] == 'L':
                Sc[(j-i)%2 +i] += 1
            else:
                break    

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

n = int(input())
x = [int(x) for x in input().split()]
inf = 10**9+7
a = 1
for i in range(n-1, 0, -1):
    a *= i
b = a
key = 0
ans = 0
for i in range(n-1):
    key += a//(i+1)
    key %= inf
    ans += key*(x[i+1]-x[i])
    ans %= inf
    

print(ans)

### FIXED CODE ###

n = int(input())
x = [int(x) for x in input().split()]
inf = 10**9+7
a = 1
for i in range(n-1, 0, -1):
    a *= i
    a %= inf
b = a
key = 0
ans = 0
for i in range(n-1):
    key += a*pow((i+1), inf-2, inf)
    key %= inf
    ans += key*(x[i+1]-x[i])
    ans %= inf
    

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

n,m=map(int,input().split())
# a=sorted(a)
c=abs(n-m)
if m==1:
   c=0
else:
    while True:
        n=abs(n-m)
        if n<=c:
            c=n
        else:
            break
print(c)

### FIXED CODE ###

n,m=map(int,input().split())
# a=sorted(a)
l=[]
c=abs(n-m)
if n%m==0:
    c=0
    print(c)
else:
    c=n%m
    d=abs(m-c)
    l.append(c)
    l.append(d)
    l=sorted(l)
    print(l[0])
### BUGGY CODE ###

s = input()
t = int(input())
r = set()

# i: 文字数
for i in range(1,len(s)+1):
    # j: 始点
    for j in range(len(s)-i+1):
        sub = s[j:j+i]
        r.add(sub)

print(sorted(r)[t-1])

### FIXED CODE ###

s = input()
k = int(input())
alphabets = sorted(set(list(s)))

# 答えとなるsubstringは必ずK文字以下
res = set()
# 頭文字(alphabetsの添字)
prefix = 0
while len(res)<k:
    # 頭文字のみの場合
    res.add(alphabets[prefix])
    for i in range(len(s)):
        #print(i,res)
        if s[i]==alphabets[prefix]:
            # 2文字以上の部分文字列をresに追加
            length = 2
            while length<=k:
                if i+length>len(s):
                    break
                res.add(s[i:i+length])
                length += 1
    prefix += 1

print(sorted(res)[k-1])
### BUGGY CODE ###

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

L = len(A)
total = 0
mod = 10**9+7

for x in range(L):
    for y in range(x+1, L):
        total += A[x]*A[y]
print(total % mod)


### FIXED CODE ###

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

L = len(A)
total = 0
tmp = 0
mod = 10**9+7
for y in range(L):
    tmp += A[y]

for x in range(L):
    tmp -= A[x] 
    total += tmp*A[x]
print(total % mod)
### BUGGY CODE ###

n = int(input())
nums = []
for i in range(n):
  num = int(input())
  nums.append(num)
count = 0
setnums = set(nums)
for j in setnums:
  test = nums.count(j)
  if test % 2 == 1:
    count += 1
print(count)

### FIXED CODE ###

from collections import defaultdict

cnt = defaultdict(int)

n = int(input())
for i in range(n):
    value = int(input())
    cnt[value] += 1

ret = 0
for c in cnt.values():
    if c % 2 == 1:
        ret += 1
print(ret)
### BUGGY CODE ###

#/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def readInput():
	return [int(i) for i in input().split(" ")]

(R, C) = readInput()
N = int(input())
rowIdx = set()
grid = defaultdict(int)
coverGrid = defaultdict(set)
rowGrid = defaultdict(set)
colGrid = defaultdict(set)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].add(c)
	colGrid[c].add(r)
	grid[(r, c)] = a 
	rowIdx.add(r)

for rowNum in rowIdx:
	row = rowGrid[rowNum]
	if (len(row) == 1):
		continue
	coverRow = coverGrid[rowNum]
	if (row.issubset(coverRow)):
		continue
	elif (len(coverRow) == 0):
		tempRow = row
	else:
		intersect = coverRow.intersection(row)
		dif = coverRow.difference(row)
		dif.add(intersect.pop()) 
		tempRow = dif
	tempRowIdx = rowIdx.copy()	
	tempRowIdx.remove(rowNum)
	for pairRowIdx in tempRowIdx:
		pairRow = rowGrid[pairRowIdx] 
		intersect = tempRow.intersection(pairRow)
		dif = tempRow.difference(pairRow)
		if (len(intersect) == 0):
			continue
		listTempRow = list(tempRow)
		listPairRow = list(pairRow)
		i = list(intersect)[0] 
		q = grid[(rowNum,i)] - grid[(pairRowIdx,i)]
		for pointer in intersect:
			tempQ = grid[(rowNum,pointer)] - grid[(pairRowIdx,pointer)]
			if (q != tempQ):
				print("No")
				exit()
		for pointer in dif:
			if (grid[(rowNum,pointer)]- q < 0): 
				print("No")
				exit()
	coverGrid[rowNum] |= tempRow
print("Yes")

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

n = int(input())

ans = 10**12

i = 2
while i <= n//2 + 1:
    if n % i == 0:
        ans = min(ans, (n//i) + i - 2)
    i += 1

print(ans)



### FIXED CODE ###

import math
n = int(input())

ans = 10**12

i = 1
while i <= int(math.sqrt(n)):
    if n % i == 0:
        ans = min(ans, (n//i) + i - 2)
    i += 1

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

N, K = map(int,input().split())
A = list(map(int,input().split()))
li = []
for i in range(N+1):
    cnt = A.count(i+1)
    if cnt>0:
        li.append(cnt)
li.sort(reverse=True)
print(sum(li[K:]))

### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
li = {}
for i in A:
    c = li.setdefault(i,0)
    li[i] = c + 1
    # print(c)
w = len(li.keys()) - K
# print(w)
# print(len(li.keys()))
ans = sorted(li.values())
# print(ans)
if w > 0:
    print(sum(ans[:w]))
else:
    print(0)
### BUGGY CODE ###

# need to solve this by C++ to avoid TLE

import sys
si = sys.stdin.readline
so = sys.stdout.write


def main():
    n = int(si())
    l = [int(e) for e in si().split()]
    i = 1
    if i not in l:
        print(-1)
        return
    count = 0
    while i in l:
        idx_i = l.index(i)
        count += idx_i
        l = l[idx_i+1:]
        i += 1

    print(count+len(l))


main()


### FIXED CODE ###

import sys
si = sys.stdin.readline
so = sys.stdout.write


def main():
    n = int(si())
    l = [int(e) for e in si().split()]

    bn = 1
    count = 0
    for i in range(n):
        if l[i] == bn:
            bn += 1
        else:
            count += 1

    print(count if count != n else -1)


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

N = int(input())

count = []

for _ in range(N):
    temp = input()
    if temp in count:
        pass
    else:
        count.append(temp)
        
print(len(count))

### FIXED CODE ###

N = int(input())

count = []

for _ in range(N):
    temp = input()
    count.append(temp)
    
count = set(count)

print(len(count))
### BUGGY CODE ###

import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
NoNeed = 0
count = 0
while Possible and count < N * (N-1) // 2:
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] < A[c[0]][i] + A[c[1]][i]:
                    continue
                elif A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    NoNeed += A[c[0]][c[1]]
                    break
                else:
                    Possible = False

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)

else:
    print(-1)


### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

a = input()
n = int(input())
for i in range(n):
    q = input().split()
    if len(q) == 3:
        if q[1] == '1':
            a = q[2] + a
        elif q[1] == '2':
            a = a + q[2]
    else:
        a = a[::-1]

print(a)

### FIXED CODE ###

from collections import deque
a = input()
a = deque(a)
n = int(input())
tmp = 0
for i in range(n):
    q = input().split()
    if len(q) == 1:
        tmp += 1
    elif len(q) == 3:
        if q[1] == '1':
            if tmp % 2 == 0:
                a.appendleft(q[2])
            else:
                a.append(q[2])
        elif q[1] == '2':
            if tmp % 2 == 0:
                a.append(q[2])
            else:
                a.appendleft(q[2])

print(''.join(a) if tmp % 2 == 0 else ''.join(a)[::-1])
### BUGGY CODE ###

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 2 ** 61 - 1
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

### FIXED CODE ###

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 1007
q2 = 2009

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q2) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q2 + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	rolling_Hash1 = [None] * (N - M + 1)
	rolling_Hash1[0] = val1
	rolling_Hash2 = [None] * (N - M + 1)
	rolling_Hash2[0] = val2

	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q2 - A[i] * mul2 + A[i + M]) % p2
		rolling_Hash1[i + 1] = val1
		rolling_Hash2[i + 1] = val2

		if Droll1[val1] == -1:
			Droll1[val1] = i + 1
		else:
			if rolling_Hash1[i + 1] == rolling_Hash1[Droll1[val1]] and rolling_Hash2[i + 1] == rolling_Hash2[Droll1[val1]] and i + 1 - Droll1[val1] >= M:
				return M

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



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

import collections

def other(a, b):
    if(a!="R" and b!="R"):
        return "R"
    if(a!="G" and b!="G"):
        return "G"
    if(a!="B" and b!="B"):
        return "B"


N = int(input())
S = str(input())
counterList = []

for i in range(N):
    counterList.append(collections.Counter(S[i:]))

result = 0
for j in range(1, N-1):
    for i in range(j):
        if(S[i] != S[j]):
            key = other(S[i], S[j])
            result += counterList[j][key]
            if(2*j-i < N):
                if(S[2*j-i] == key):
                    result -= 1
print(result) 

### FIXED CODE ###

import collections

def other(a, b):
    if(a!="R" and b!="R"):
        return "R"
    if(a!="G" and b!="G"):
        return "G"
    if(a!="B" and b!="B"):
        return "B"


N = int(input())
S = str(input())
counterList = []

for i in range(N):
    counterList.append(collections.Counter(S[i:]))

result = 0
for j in range(1, N-1):
    for i in range(j):
        if(S[i] != S[j]):
            key = other(S[i], S[j])
            result += counterList[j][key]
            if(2*j-i < N):
                if(S[2*j-i] == key):
                    result -= 1
print(result)
### BUGGY CODE ###

def check():
  n=int(input())
  A=list(map(int,input().split()))
  if 0 in A:
    print(0)
    return
  a=1
  for i in A:
      a=a*i
  if a>1000000000000000000:
    print(-1)
    return
  print(a)
  return


check()


### FIXED CODE ###

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

ans=1

if 0 in A:
    print(0)
    exit()

for i in A:
   ans=ans*i
   if ans>10**18:
    print(-1)
    exit()


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

from functools import lru_cache
import sys
sys.setrecursionlimit(100000000)
N = int(input())
def main():
    a = list(map(int, input().split()))
    d = {0:0, 1:0, 2:0, 3:0}
    for i in a:
        d[i] += 1
    print(dfs(d[1],d[2],d[3]))
@lru_cache(maxsize=None)
def dfs(a, b, c):
    if a + b + c == 0:
        return 0
    t1 = t2 = t3 = 0
    total = a + b + c
    if a > 0:
        t1 = (a/total) * dfs(a-1, b, c)
    if b > 0:
        t2 = (b/total) * dfs(a+1, b-1, c)
    if c > 0:
        t3 = (c/total) * dfs(a, b+1, c-1)
    return N/total + t1 + t2 + t3
main()



### FIXED CODE ###

N = int(input())
def main():
    a = list(map(int, input().split()))
    d = {0:0, 1:0, 2:0, 3:0}
    for i in a:
        d[i] += 1
    d1 = d[1]
    d123 = d[1] + d[2] + d[3]
    d23 = d[2] + d[3]
    d3 = d[3]
    d2 = d[2]
    l = [[[0] * (d123 + 1) for _ in range(d23 + 1)] for _ in range(d3 + 1)]
    for i in range(d3 + 1):
        for j in range(d23 + 1):
            for k in range(d123 + 1):
                if i + j + k == 0:
                    continue
                if i + j + k > d123:
                    continue
                if i + j > d23:
                    continue
                total = i + j + k
                a = b = c = 0
                if k > 0:
                    a = k * l[i][j][k-1]
                if j > 0:
                    b = j * l[i][j-1][k + 1]
                if i > 0:
                    c = i * l[i-1][j + 1][k]
                l[i][j][k] = (a + b + c + N)/total
    print(l[d3][d2][d1])
main()
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))

cost = np.zeros(n)


for i in range(1,n):
    left = max(0,i-k)
    cost[i] = min(cost[left:i]+abs(h[i]-h[left:i]))
     

print(int(cost[-1]))


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))

cost = np.zeros(n)


for i in range(1,n):
    left = max(0,i-k)
    cost[i] = (cost[left:i]+abs(h[i]-h[left:i])).min()
     

print(int(cost[-1]))
### BUGGY CODE ###

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

new_a = sorted(a)
for i in range(n):
  ans.append(a.index(new_a[i])+1)

print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0] * n

for i in range(n):
  b[a[i]-1] = i+1
print(*b)
### BUGGY CODE ###

def appen(li,yousa):
    li.append(yousa)
    return li
    
def main():
    
    n,m=map(int,input().split())
    h=list(map(int,input().split()))
    a=[]
    b=[]
    for i in range(m):
        al,bl=map(int,input().split())
        a=appen(a,al)
        b=appen(b,bl)
    res=0
    for i in range(1,n+1):
        xx=[]
        for j in range(m):
            if i==a[j]:
                xx=appen(xx,h[b[j]-1])
            if i==b[j]:
                xx=appen(xx,h[a[j]-1])
        if len(xx)==0:
            res+=1
        elif max(xx)<h[i-1]:
            res+=1
        else:
            continue
    print(res)
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

def ma(li):
    # ループごとにifで大小比較
    max_num = 0
    for i in li:
        if max_num < i:
            max_num = i
    return max_num

def appen(li,yousa):
    li.append(yousa)
    return li
    
def main():
    res=0
    n,m=map(int,input().split())
    h=list(map(int,input().split()))
    
    a=[list(map(int,input().split())) for i in range(m)]
    f=[]
    for i in range(n):
        f.append([0])
    for i in a:
        f[i[0]-1].append(h[i[1]-1])
        f[i[1]-1].append(h[i[0]-1])
    p=-1
    for i in f:
        p+=1
        if len(i)==1:
            res+=1
        elif ma(i)<h[p]:
            res+=1
        else:
            continue

    print(res)

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

n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))
    
s = [[0 for _ in range(6*k+1)] for _ in range(6*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]

            res = 0
for i in range(k):
    for j in range(k):
        res = max(res, s2[i][j])
        res = max(res, s3[i][j])
print(res)


### FIXED CODE ###

n, k = map(int, input().split())
v = []
for i in range(n):
    abc = [x for x in input().split()]
    a = int(abc[0])
    b = int(abc[1])
    c = abc[2]
    if c == 'W':
        b += k
    v.append((a % (2*k), b % (2*k)))

s = [[0 for _ in range(3*k+1)] for _ in range(3*k+1)]
s2 = [[0 for _ in range(k+1)] for _ in range(k+1)]
s3 = [[0 for _ in range(k+1)] for _ in range(k+1)]

for i in range(n):
    s[v[i][1]][v[i][0]] += 1
    s[v[i][1]+k][v[i][0]+k] += 1
    s[v[i][1]+k][v[i][0]] -= 1
    s[v[i][1]][v[i][0]+k] -= 1

for i in range(3*k):
    for j in range(3*k):
        s[i+1][j] += s[i][j]
for i in range(3*k):
    for j in range(3*k):
        s[i][j+1] += s[i][j]

for i in range(3*k):
    for j in range(3*k):
        c = (i//k+j//k) % 2
        if c == 0:
            s2[i % k][j % k] += s[i][j]
        else:
            s3[i % k][j % k] += s[i][j]
res = 0

for i in range(k):
    for j in range(k):
        res = max(res, s2[i][j])
        res = max(res, s3[i][j])

print(res)