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

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[n])
### BUGGY CODE ###

isPrime = []
prime = []

import math

def init():
    for i in range(50000 + 1):
        isPrime.append(True)

def eratos():
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(math.sqrt(50000)) + 1):
        if (isPrime[i]):
            for j in range(i * 2, 50000 + 1, i):
                isPrime[j] = False
    
    for i in range(2, 50001):
        if isPrime[i]:
            prime.append(i)

init()
eratos()

while True:
    n = int(input())
    if n == 0:
        break

    count = 0
    if n % 2:
        if isPrime[n - 2]:
            count += 1
    else:
        if n == 4:
            count += 1
        else:
            for i in prime:
                if i > (n // 2):
                    break
                if (n - i) in prime:
                    count += 1
    
    print(count)

### FIXED CODE ###

isPrime = []
prime = []
count = []

def init():
    for i in range(50000 + 1):
        isPrime.append(True)
        count.append(0)

def eratos():
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int((50000 ** (1 / 2))) + 1):
        if (isPrime[i]):
            for j in range(i * 2, 50000 + 1, i):
                isPrime[j] = False
    
    for i in range(2, 50001):
        if isPrime[i]:
            prime.append(i)


def table():
    for i in prime:
        for j in prime:
            if i < j:
                continue
            if i + j > 50000:
                continue
            count[i + j] += 1

init()
eratos()
table()

while True:
    n = int(input())
    if n == 0:
        break
    print(count[n])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    r = 0
    for i1 in range(n-1):
        tall = a[i1]
        for i2 in range(i1 + tall+1, n):
            r += (i2 - i1) == tall + a[i2]

    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0
    l1 = []
    for ea in a:
        l1.append(cnt - ea)
        cnt += 1
    l1c = Counter(l1)
    r = 0
    for i2 in range(n):
        r += l1c[i2 + a[i2]]
    print(int(r))

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

from collections import Counter as C
s=list(input())
l=[]
ans=0
for i in range(len(s)):
  if s[i] == "W":
    l.append(i)
for i in l:
  #print(s[:i], C(s[:i])["B"])
  s[i]="_"
  ans+=C(s[:i])["B"]
print(ans)

### FIXED CODE ###

s=list(input())
l=[]
ans=0
b=0
for i in range(len(s)):
  if s[i] == "W":
    ans+=b
  else:
    b+=1
print(ans)
### BUGGY CODE ###

import numpy as np


def count_multi(s, d):
  a = np.array([c for c in s]).astype(np.int)
  m = a % d
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (10*m[:-1] + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input().strip(), 2019))


### FIXED CODE ###

def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())
### BUGGY CODE ###

n, a, b = map(int, input().split())

al = a
bl = b
cnt = 0
for i in range(n):
    if al != 0:
        cnt += 1
        al -= 1
    elif bl != 0:
        bl -= 1
    
    if al == 0 and bl == 0:
        bl = b
        al = a
    
print(cnt)

### FIXED CODE ###

n, a, b = map(int, input().split())

ans = a * (n // (a + b))
if a < n % (a + b):
    ans += a
else:
    ans += n % (a + b)

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

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

dp = [[[0]*2 for s in range(3001)] for i in range(N)]

for n in range(N):
    for s in range(3000,-1,-1):
        dp[n][s][1] = dp[n-1][s][1]
        dp[n][s][0] = dp[n-1][s][0]
        if s>A[n]:
            dp[n][s][1] += dp[n-1][s-A[n]][0]*(N-n)
            dp[n][s][0] += dp[n-1][s-A[n]][0]
        elif s==A[n]:
            dp[n][s][1] += (n+1)*(N-n)
            dp[n][s][0] += n+1
        dp[n][s][1] %= mod
        dp[n][s][0] %= mod

print(dp[N-1][S][1])

### FIXED CODE ###

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

dp1 = [0]*(3001*N)
dp2 = [0]*(3001*N)

for n in range(N):
    for s in range(3000,-1,-1):
        dp2[n*N+s] = dp2[(n-1)*N+s]
        dp1[n*N+s] = dp1[(n-1)*N+s]
        if s>A[n]:
            dp2[n*N+s] += dp1[(n-1)*N+s-A[n]]*(N-n)
            dp1[n*N+s] += dp1[(n-1)*N+s-A[n]]
        elif s==A[n]:
            dp2[n*N+s] += (n+1)*(N-n)
            dp1[n*N+s] += n+1
        dp2[n*N+s] %= mod
        dp1[n*N+s] %= mod

print(dp2[(N-1)*N+S])
### BUGGY CODE ###

import math
from functools import reduce
K = 200
ans = 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += gcd(i,j,k)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    tmp = math.gcd(i,j)
    for k in range(1,K+1):
        ans += math.gcd(tmp,k)
print(ans)
### BUGGY CODE ###

H=int(input())
c=1
ans=0
while True:
    H=H//2
    ans+=c
    c*=2
    if H==1:
        ans+=c
        break
        
print(ans)

### FIXED CODE ###

H=int(input())
c=1
ans=0
while True:
    if H==1:
        ans+=c
        break
    H//=2
    ans+=c
    c*=2
print(ans)
### BUGGY CODE ###

import numpy as np
import itertools

n = int(input())
x = [list(map(int, input().split())) for i in range(n)]

res = 0
cnt = 0
for v in itertools.permutations(x):
  for i in range(n-1):
    res += np.linalg.norm(np.array(v[i+1])-np.array(v[i]))
  cnt += 1

print((res+0.0)/cnt)


### FIXED CODE ###

import math
import itertools

n = int(input())
x = [list(map(int, input().split())) for i in range(n)]

res = 0
cnt = 0
for v in itertools.permutations(x):
  for i in range(n-1):
    res += math.sqrt((v[i+1][0] - v[i][0]) ** 2 + (v[i+1][1] - v[i][1]) ** 2)
  cnt += 1

print((res+0.0)/cnt)
### BUGGY CODE ###

import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
coordinate = np.arange(1, N+1)

for _ in range(K):
    B = np.zeros(N, dtype="int")
    for i in range(N):
        end = np.minimum(coordinate[i]+A[i], N)
        start = np.maximum(coordinate[i]-A[i], 1)
        
        B[start-1] += 1
        if end < N:
            B[end] -= 1
    B = np.cumsum(B)
    A = B.copy()
    
    if (A==N).sum()==N:
      break

print(" ".join(map(str, A.tolist())))


### FIXED CODE ###

def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = read_input()
K = min(K, 41)

for _ in range(K):
    B = [0]*N
    for i in range(N):
        start = max(i-A[i], 0)
        end = min(i+A[i], N-1)

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()


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

import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i,i+len(s)]
    else:
        ma[each_s].append(i)
        ma[each_s].append(i+len(s))
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    tmp_li.sort()
    #print(tmp_li,'tmp')

    lee = len(s_li)
    new_li = tmp_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min',lee)
    if min_index>= lee:
        repeat_count += 1
        min_index = new_li[0]
    elif min_index <= last_index:
        repeat_count += 1
        min_index = new_li[0]
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)


### FIXED CODE ###

import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i]
    else:
        ma[each_s].append(i)
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 0
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li)

    lee = len(s_li)
    #add_li = [ii+lee for ii in tmp_li]
    #new_li = tmp_li + add_li
    #bi = bisect.bisect_left(new_li, last_index+1)
    bi = bisect.bisect_left(tmp_li, last_index+1)
    #print(bi,len(tmp_li),'bi',tmp_li,last_index,'last_index')
    if bi>= len(tmp_li):
        repeat_count += 1
        min_index = tmp_li[0]
    else:
        min_index = tmp_li[bi]
    #print(new_li,last_index+1,min_index,'min')
    #if min_index>= lee:
    #    repeat_count += 1
    #    min_index -= lee
    last_index = min_index
    #print(repeat_count,'repeat')
    #print(last_index,'last')
print(lee*(repeat_count)+last_index+1)
### BUGGY CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(1, m // 2):
    if m % i == 0:
        if m // i >= n:
            ans = i
        else:
            break
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(1, int(m ** .5) + 1):
    if m % i == 0:
        b = m // i
        if i * n <= m:
            ans = max(ans, i)
        if b * n <= m:
            ans = max(ans, b)
print(ans)
### BUGGY CODE ###

s = list(input())
def dp(i, j, s):
    for ii in range(i):
        if s[j] == "R":
            j = j +1
        else:
            j = j-1
    return j
dic = {}
for x in range(len(s)):
    dic[x] = dp(10**4,x,s)
nwli =[0 for q in range(len(s))]
for t in range(len(s)):
    nwli[dic[dic[t]]]+=1
print(" ".join(map(str,nwli)))

### FIXED CODE ###

s = list(input())
output = [0 for i in s]
ruiseki = 0
for p in range(len(s)):
    if s[p] == "R":
        if s[p+1] == "R":
            ruiseki+=1
        else:
            ruiseki+=1
            output[p] += ruiseki//2 + ruiseki%2
            output[p+1] += ruiseki//2
            ruiseki=0
    
ruiseki = 0
for q in range(len(s)-1, -1, -1):
    if s[q] == "L":
        if s[q-1]=="L":
            ruiseki+=1
        else:
            ruiseki+=1
            output[q] += ruiseki//2 + ruiseki%2
            output[q-1] += ruiseki//2
            ruiseki=0
print(" ".join(map(str,output)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

S = input()

def dfs(p,a):
  if p == len(S):
    return 0
  if a > 0 and S[p] == 'g':
    return max(1+dfs(p+1,a-1),dfs(p+1,a+1))
  elif a > 0 and S[p] == 'p':
    return max(dfs(p+1,a-1),-1+dfs(p+1,a+1))
  elif a == 0 and S[p]  == 'g':
    return dfs(p+1,a+1)
  else:
    return -1+dfs(p+1,a+1)

print(dfs(0,0))

### FIXED CODE ###

S = input()

A = 'gp' * (len(S)//2)
if len(S) % 2 == 1:
  A += 'g'
ans = 0
for i in range(len(S)):
  if S[i] == 'p' and A[i] == 'g':
    ans -= 1
  elif S[i] == 'g' and A[i] == 'p':
    ans += 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
pl = ""
count = 0

for l, r in lr:
    for st in S[l-1:r]:
        if st == "C" and pl == "A":
            count+=1
        pl = st

    print(count)
    count=0


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
t = [0]*N
count = 0

for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]
for l, r in lr:
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, K: int, A: "List[int]"):
    ans = 0
    max_bit = 40
    A = np.array(A)
    for i in range(max_bit+1):
        t = 2**(max_bit-i)
        count = sum([1 for a in A if a&t > 0])
        if t <= K and count < N / 2:
            count = N - count
            K -= t
        ans += count * t
    print(ans)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, K: int, A: "List[int]"):
    ans = 0
    max_bit = 40
    for i in range(max_bit+1):
        t = 2**(max_bit-i)
        count = len([1 for a in A if a&t > 0])
        if t <= K and count < N / 2:
            count = N - count
            K -= t
        ans += count * t
    print(ans)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

N=int(input())
Ln=list(map(int,input().split()))
Ln.sort(reverse=True)
Ans=0

for i in range(N-2):
    di=i+1
    for j in range(N-di-1):
        dj=di+j+1
        if (Ln[dj-1]+Ln[dj])<Ln[di-1] : break
        for k in range(N-dj):
            dk=dj+k+1
            a=Ln[di-1]
            b=Ln[dj-1]
            c=Ln[dk-1]
            if((b+c)>a)&((c+a)>b) :
                Ans +=1
            else : break

print(Ans)

### FIXED CODE ###

N=int(input())
Ln=list(map(int,input().split()))
Ln.sort(reverse=True)
Ans=0
left=0
right=0
 
for i in range(N-2):
    di=i+1
    for j in range(N-di-1):
        dj=di+j+1
        A=Ln[di-1]
        B=Ln[dj-1]
        if (B+Ln[dj])<A : break
 
        right=N-1
        left=dj
        while left<=right :
            mid=int((right+left)/2)
            if (B+Ln[mid])>A :
                left=mid+1
            else :
                right=mid-1
        Ans+=(left-1)-(dj-1)
 
print(Ans)
### BUGGY CODE ###

N=int(input())
ans=0

for i in range(1,N):
    for j in range(1,N):
        for k in range(1,N):
            if i*j==N-k:
                ans +=1
print(ans) 


### FIXED CODE ###

n=int(input())
ans=0
for a in range(1,n):
  x=(n-1)//a
  ans+=x
print(ans)
### BUGGY CODE ###

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    indexlist=my_index_multi(A,i[0])
    for j in indexlist:
        A[j]=i[1]
    print(sum(A))

### FIXED CODE ###

import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)
### BUGGY CODE ###

[R, C, K] = list(map(int, input().split()))
G = [[0]*(C+1) for i in range(R+1)]
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

dp = [[[-1]*4 for i in range(C+1)] for j in range(R+1)]
dp[0][0][0] = 0
if G[0][0] != None: dp[0][0][1] = G[0][0]

for r in range(R):
    for c in range(C):
        for k in range(4):
            if dp[r][c][k] == -1: continue

            if k < 3: # can go right and pick up
                if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                    dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
            if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
            if dp[r+1][c][0] < dp[r][c][k]:
                dp[r+1][c][0] = dp[r][c][k]
            if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]

print(max(dp[r][c]))


### FIXED CODE ###

import numpy as np
from numba import jit

R, C, K = map(int, input().split())
G = np.zeros((R+1, C+1), np.int64)
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

@jit
def main(G, R, C):
    dp = np.full((R+1, C+1, 4), -1)
    dp[0][0][0] = 0
    if G[0][0] != None: dp[0][0][1] = G[0][0]
    for r in range(R):
        for c in range(C):
            for k in range(4):
                if dp[r][c][k] == -1: continue
                if k < 3: # can go right and pick up
                    if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                        dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]
    return(max(dp[r][c]))

ret = main(G, R, C)
print(ret)
### BUGGY CODE ###

N=int(input())
A=[input() for i in range(N)]
NA=[A.count(A[i]) for i in range(N)]
MAX=max(NA)
NIN=[i for i, v in enumerate(NA) if v == MAX]
LN=len(NIN)
NM=[A[NIN[i]] for i in range (LN)]
NM=sorted(list(set(NM)))
for i in NM:
    print(i)

### FIXED CODE ###

N = int(input())
L = [input() for i in range(N)]
L = sorted(L)
D = {}

for i in L:
    if i in D:
        V = D.get(i) + 1
    else:
        V = 1
    D[i] = V

D = sorted(D.items(),key=lambda x:x[1],reverse=True)

Ans = []

Ans.append(D[0][0])

for i in range(len(D)-1):
    if D[i][1] == D[i+1][1]:
        Ans.append(D[i+1][0])
    else:
        break

Ans = sorted(Ans)

for i in Ans:
    print(i)
### BUGGY CODE ###

def Judge(a, b):
    k = 0
    while 2 ** k  - 1 <= a + b:
        if 2 ** k - 1 == a + b:
            return True
        k += 1
    return False

L = int(input(),2)
count = (L + 1) * 2 - 1
for i in range(1,L + 1):
    for j in range(1,L - i + 1):
        if Judge(i, j):
            count += 1

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

### FIXED CODE ###

L = input()
#dp1[k] := k桁目までを確定させ、その時点でA+BがL以下が確定
#dp2[k] := k桁目までを確定させ、その時点でA+BがL以下が確定していない
dp1 = [0 for i in range(len(L))]
dp2 = [0 for i in range(len(L))]
mod = 10**9 + 7
dp1[0] = 1 # A,Bの最上位bitが(0,0)
dp2[0] = 2 # A,Bの最上位bitが(0,1), (1,0)の二通り
#最上位bitを(1,1)にしてしまうと、Lを超えてしまうのでない
for i in range(1,len(L)):
    #dp1の更新から行う
    if L[i] == '1':
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod
print((dp1[-1] + dp2[-1]) % mod)
### BUGGY CODE ###

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T

if np.sum(S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.zeros(len(M))
        for s in S:
            D[:] += [sum(s[m]) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[m]) for m in M]

        if answer > ans:
            answer = ans
        elif answer==1:
            break

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

import sys

n, k = map(int, input().split())
A = list(map(int, input().split()))
A_set = set(A)
if len(A_set) <= k:
    print(0)
    sys.exit()
A_count = [0]*len(A_set)
for i, a in enumerate(A_set):
    A_count[i] = A.count(a)
A_count.sort()

num = len(A_set) - k
s = 0
for i in range(num):
    s += A_count[i]
print(s)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
num = [0]*n
for a in A:
    num[a-1] += 1
num.sort(reverse=True)
cnt = 0
for i in range(k):
    cnt += num[i]
ans = n - cnt
print(ans)
### BUGGY CODE ###

import collections

def main():
	n, q = map(int, input().split())
	s = input()
	# 地点iにいるゴーレムの数
	golems = [1]*n
	# 呪文に該当する場所
	points = collections.defaultdict(list)

	for i in range(n):
		points[s[i]].append(i)

	total = n
	for _ in range(q):
		point, move = input().split()
		for pos in points[point]:
			current_golems = golems[pos]
			golems[pos] = 0
			if move == "L":
				if pos == 0:
					total -= current_golems
				else:
					golems[pos-1] += current_golems
			else:
				if pos == n-1:
					total -= current_golems
				else:
					golems[pos+1] += current_golems
	print(total)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	n, q = map(int, input().split())
	s = "."+input()+"."
	pm = [input().split() for _ in range(q)]

	def is_outside(x:int) -> int:
		for point, move in pm:
			if s[x] == point:
				if move == "L":
					x -= 1
				else:
					x += 1
			if x == 0:
				return -1
			if x == n+1:
				return 1
		return 0

	ok, ng = 0, n+1
	while ng - ok > 1:
		mid = (ng + ok) >> 1
		if is_outside(mid) == -1:
			ok = mid
		else:
			ng = mid
	l = ok

	ng, ok = 0, n+1
	while ok - ng > 1:
		mid = (ng + ok) >> 1
		if is_outside(mid) == 1:
			ok = mid
		else:
			ng = mid
	r = ng

	print(max(r-l, 0))

if __name__ == '__main__':
    main()