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

import sys
sys.setrecursionlimit(202020)

n, q = map(int, input().split())
to = [[] for _ in range(n)]
score = [0 for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    score[p] += x

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        score[u] += score[v]
        dfs(u, p=v)

dfs(0)
print(*score)

### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
### BUGGY CODE ###

from sys import stdin
#n = int(stdin.readline().rstrip())
n,k = map(int, stdin.readline().rstrip().split())
#S = [list(map(int, stdin.readline().rstrip().split())) for _ in range(h)]#hの定義を忘れずに
p = list(map(int, stdin.readline().rstrip().split()))

ans = 0
for i in range(n-k+1):
    sum = 0
    for j in range(k):
        sum += p[i+j]
    ans = max(sum,ans)
    if ans == sum:
        real = 0
        for l in range(k):
            s = 0
            num = p[i+l]
            for j in range(num):
                s += 1+j
            real += s/num
    else:
        pass

print(real)


### FIXED CODE ###

from sys import stdin
#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
N,K = map(int, stdin.readline().rstrip().split())
P = list(map(int, stdin.readline().rstrip().split()))

Q = [(p+1)/2 for p in P]
c = [0]
for q in Q:
    c.append(c[-1] + q)

ans = 0
for i in range(K,N+1):
    ans = max(ans, c[i] - c[i-K])
print(ans)
### BUGGY CODE ###


from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    mod = 998244353

    dp = [defaultdict(int) for i in range(num)]
    for i in range(num):
        now_num = data[i]
        if i == 0:
            dp[i][0] = 2
            dp[i][now_num] = 1
            continue
        for key, value in dp[i - 1].items():
            dp[i][key] += value * 2
            dp[i][key + now_num] += value
            dp[i][key] %= mod
            dp[i][key + now_num] %= mod

    dp2 = [defaultdict(int) for i in range(num)]
    for i in range(num):
        now_num = data[i]
        if i == 0:
            dp2[i][0] = 1
            dp2[i][now_num] = 1
            continue
        for key, value in dp2[i - 1].items():
            dp2[i][key] += value
            dp2[i][key + now_num] += value
            dp2[i][key] %= mod
            dp2[i][key + now_num] %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    sum_num = sum(data)
    for key, value in dp[num - 1].items():
        if key >= math.ceil(sum_num / 2):
            hikukazu += value
    if sum_num % 2 == 0:
        hikukazu -= dp2[num - 1][sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)
### BUGGY CODE ###


N,M = map(int,input().split())

num = [0] * N
far = [0] * N
RD = []
tps = []
p = []

for i in range(N):
    RD.append([])
    p.append(set([i]))

for i in range(M):

    L,R,D = map(int,input().split())

    num[R-1] += 1
    RD[L-1].append([R-1,D])

Q = []

for i in range(N):
    if num[i] == 0:
        Q.append(i)

while len(Q) > 0:

    q = Q.pop(0)
    num[q] -= 1
    tps.append(q)

    for rd in RD[q]:

        r = rd[0]
        num[r] -= 1
        if num[r] == 0:
            Q.append(r)


flag = True
for i in range(N):

    if num[i] > 0:
        flag = False

maxfar = 0
#print (flag)


if flag:

    for i in tps:

        for ra in RD[i]:

            if len(p[ra[0]] & p[i]) > 0 and far[ra[0]] != far[i] + ra[1]:
                flag = False

            p[ra[0]] = p[ra[0]] | p[i]
            far[ra[0]] = max(far[ra[0]],far[i] + ra[1])
            maxfar = max(maxfar,far[ra[0]])

            

#print (far)
if flag and maxfar <= 10 ** 9:
    print ("Yes")
else:
    print ("No")
    




### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


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

# -*- coding: cp932 -*-

import sys
import os
import re
import datetime
import bisect

### main ###

X = input()

restS = []
for c in X:
    #print("c = {}".format(c))
    restS.append(c)
    if c == 'T':
        while(len(restS) >= 2):
            #print("restS = {}, last 2 string = {} ".format(restS, restS[-2:]))
            if("".join(restS[-2:]) == 'ST'):
                #print("hit")
                restS = restS[:-2]
                #print("new restS = {}".format(restS))
            else:
                #print("no hit")
                break # out of while

print(len(restS))

### FIXED CODE ###

# -*- coding: cp932 -*-

import sys
import os
import re
import datetime
import bisect

### main ###

X = input()

restS = []
for c in X:
    #print("c = {}".format(c))
    restS.append(c)
    if c == 'T':
        while(len(restS) >= 2):
            #print("restS = {}, last 2 string = {} ".format(restS, restS[-2:]))
            if("".join(restS[-2:]) == 'ST'):
                #print("hit")
                #restS = restS[:-2] # TLE
                del restS[-2:]
                #print("new restS = {}".format(restS))
            else:
                #print("no hit")
                break # out of while

print(len(restS))
### BUGGY CODE ###

N = int(input())
A = [input() for i in range(N)]
M = 1046527
T = [0 for i in range(M)]

# 各文字をバイト列にした後、それらを10進数にして、文字列として結合する
def get_key(value: str) -> int:
    converted_value = ""
    for s in value:
        b = s.encode()
        converted_value += str(b[0])
    return int(converted_value)

def h1(key: int) -> int:
    return key % M

def h2(key: int) -> int:
    move_value = 1 + (key % (M-1))
    return move_value

def h(key:int, i:int) -> int:
    hash_value = (h1(key) + i+h2(key)) % M
    return hash_value

def find(key: int) -> bool:
    i = 0
    while True:
        j = h(key, i)
        if T[j] == key:
            return True
        elif T[j] == 0 or i >= M:
            return False
        else:
            i += 1


def insert(key: int) -> None:
    i = 0
    while True:
        j = h(key, i)
        if T[j] == 0:
            T[j] = key
            return
        else:
            i += 1


for row in A:
    order, value = row.split()
    key = get_key(value)
    if order[0] == "i":
        insert(key)
    else:
        if find(key):
            print("yes")
        else:
            print("no")


### FIXED CODE ###

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

D = {}
for row in A:
    order, key = row.split()
    if order[0] == "i":
        D[key] = 1
    else:
        if key in D.keys():
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import math
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
Ans = 0
for i in range(n-k+1):
    exp = sum(p[i:i+k])
    if ans < exp:
        ans = exp
        s = p[i:i+k]
        Ans = 0
        for j in range(k):
            Ans += (sum(list(range(s[j]+1)))/s[j])
print(Ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
exp = sum(p[0:k])
ans = exp
for i in range(n-k):
  exp = exp-p[i]+p[i+k]
  #print(ans, exp)
  if ans<exp:
    ans = exp
    #print("ans", exp, ans)
print((ans+k)/2)
### BUGGY CODE ###

import re
a = input()
operations = 0
re.search("01", a) or re.search("10", a)
i = 0
while re.search("01", a) or re.search("10", a):
    if re.search("01", a):
        a = a.replace("01", "", 1)
        operations += 2
    if re.search("10", a):
        a = a.replace("10", "", 1)
        operations += 2
print(operations)

### FIXED CODE ###

num = input()
predicted_value = 0
finished = False
i = 1
while i < len(num):
    if num[i] != num[i-1]:
        num = num[:i-1] + num[i+1:]
        predicted_value += 2
        if i > 1:
            i -= 2
        elif i == 1:
            i = 0
    i += 1
print(predicted_value)
### BUGGY CODE ###

import itertools

n = int(input())
c = list(input())

deta = list(range(n))
r = c.count("R")
g = c.count("G")
b = c.count("B")

ans = r*g*b

count  = 0

sub1 = 0

for i in range(n):
    for j in range(i,n):
        if 2*j-i<n and 2*j-i>0:
            if c[2*j-i] != c[i] and c[i] != c[j] and c[2*j-i] != c[j]:
                sub1 += 1


print(ans-sub1)


### FIXED CODE ###

n = int(input())
c = list(input())

r = c.count("R")
g = c.count("G")
b = c.count("B")

ans = r*g*b
count  = 0
sub1 = 0

for i in range(n):
    for j in range(i+1,n):
        if 2*j-i >= n or 2*j-i <0:
            break
        elif c[2*j-i] != c[i] and c[i] != c[j] and c[2*j-i] != c[j]:
                sub1 += 1


print(ans-sub1)
### BUGGY CODE ###

def main():
  from itertools import groupby

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

  num = []
  cot = []
  for k, n in groupby(S):
    num.append(k)
    cot.append(len(list(n)))

  if num[0] == "1":
    x = K*2+1
  else:
    x = K*2

  ans = 0
  for i in range(len(cot)-x+1):
    if num[i] == "1":
      x = K*2+1
    else:
      x = K*2
    ans = max(ans,sum(cot[i:i+x]))
  if ans == 0:
    ans = len(S)
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  from itertools import groupby

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

  num = []
  cot = []
  for k, n in groupby(S):
    num.append(k)
    cot.append(len(list(n)))

  if num[-1] == "0":
    cot += [0]
    num += [0]

  X = [0]*(len(cot)+1)
  for i in range(len(cot)):
    X[i+1] = X[i]+cot[i]

  ans = 0
  for i in range(len(X)):
    x = K*2
    if num[i] == "1":
      x += 1
    try:
      ans = max(ans, X[i+x]-X[i])
    except:
      break
  if ans == 0:
    ans = len(S)
  print(ans)

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

from sys import stdin

def main():
    n = int(stdin.readline().rstrip())
    xs = [int(stdin.readline().rstrip()) for _ in range(n)]

    for i in range(n):
        print(max(xs[0:i]+xs[i+1:]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin

def main():
    n = int(stdin.readline().rstrip())
    xs = [int(stdin.readline().rstrip()) for _ in range(n)]

    max_1, max_2 = sorted(xs)[-1], sorted(xs)[-2]

    for i in range(n):
        if xs[i] == max_1:
            print(max_2)
        else:
            print(max_1)
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t] + 1: break
      #dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t] + 1: break
      #dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t] + 1: break
      #dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t] + 1: break
      #dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)

### FIXED CODE ###

import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
x, y, u, v = map(int, input().split())
x -= 1
y -= 1
u -= 1
v -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([(0, x * W + y)])
inf = H * W + 1
dp = [inf] * (H * W)
dp[x * W + y] = 0
while len(Q):
  cost, t = Q.popleft()
  dp[t] = cost
  p = t // W
  q = t % W
  if (p, q) == (u, v):
    print(cost)
    exit(0)
  for i in range(1, K + 1):
    pp = p + i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      if dp[pp * W + q] != inf: continue
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))
  for i in range(1, K + 1):
    pp = p - i
    if pp in range(H):
      if a[pp][q] == "@": break
      if dp[pp * W + q] <= dp[t]: break
      if dp[pp * W + q] != inf: continue
      dp[pp * W + q] = dp[t] + 1
      Q.append((dp[t] + 1, pp * W + q))

  for i in range(1, K + 1):
    qq = q + i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      if dp[p * W + qq] != inf: continue
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))

  for i in range(1, K + 1):
    qq = q - i
    if qq in range(W):
      if a[p][qq] == "@": break
      if dp[p * W + qq] <= dp[t]: break
      if dp[p * W + qq] != inf: continue
      dp[p * W + qq] = dp[t] + 1
      Q.append((dp[t] + 1, p * W + qq))
print(-1)
### BUGGY CODE ###

inputlist = list(map(int, input().split()))
n, m = inputlist[0], inputlist[1]

for i in range(1,m+1):
    if m % i != 0:
        continue
    if n > i:
        continue
    print(m // i)
    break

### FIXED CODE ###

def f():
  n, m = map(int, input().split())
  for i in range(m//n+1)[::-1]:
    if m%i==0:return i
print(f())
### BUGGY CODE ###

h,w=map(int,input().split())
s=[input() for x in range(h)]

e=[[0 for i in range(w)] for j in range(h)]
r=[[0 for i in range(w)] for j in range(h)]
l=[[0 for i in range(w)] for j in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
u=[[0 for i in range(w)] for j in range(h)]


for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      e[i][j] = 1

for i in range(h):
  l[i][0] = e[i][0]
  r[i][w-1] = e[i][w-1]
  for j in range(1,w):
    l[i][j] = (l[i][j-1]+1) * e[i][j]
    r[i][w-j-1] = (r[i][w-j]+1) * e[i][w-j-1]

for i in range(w):
  u[0][i]=e[0][i]
  d[h-1][i]=e[h-1][i]
  for j in range(1,h):
    u[j][i] = (u[j-1][i]+1) * e[j][i]
    d[h-j-1][i] = (d[h-j][i]+1) * e[h-j-1][i]

m = 0
for i in range(h):
   for j in range(w):
      m = max(m,l[i][j]+r[i][j]+u[i][j]+d[i][j])

print(m-3)


### FIXED CODE ###

import numpy as np

h,w=map(int,input().split())
s=np.array([[(1 if x=='.' else 0) for x in list(input())] for y in range(h)])

r=np.zeros((h,w),dtype=int)
l=np.zeros((h,w),dtype=int)
d=np.zeros((h,w),dtype=int)
u=np.zeros((h,w),dtype=int)

l[:,0] = s[:,0]
r[:,w-1] = s[:,w-1]
for i in range(1,w):
  l[:,i] = (l[:,i-1]+1) * s[:,i]
  r[:,w-i-1] = (r[:,w-i]+1) * s[:,w-i-1]

u[0]=s[0]
d[h-1]=s[h-1]
for i in range(1,h):
  u[i] = (u[i-1]+1) * s[i]
  d[h-i-1] = (d[h-i]+1) * s[h-i-1]

print(((l+r+u+d).max()-3))
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = list(input())
Q = int(input())

for i in range(Q):
    a, b, c = input().split()
    if a == "1":
        S[int(b)-1] = c
    else:
        count = Counter([S[i] for i in range(int(b)-1, int(c))])
        print(len(count))

### FIXED CODE ###

import bisect

n = int(input())
s = list(input())
q = int(input())

pos = [[] for i in range(26)]
alp = "abcdefghijklmnopqrstuvwxyz"
atoi = {}
for i in range(26):
    atoi[alp[i]] = i
for i in range(n):
    pos[atoi[s[i]]].append(i)

for i in range(q):
    a, b, c = input().split()
    if a == "1":
        b = int(b)-1
        if c == s[b]:
            continue
        index = bisect.bisect_left(pos[atoi[s[b]]], b)
        del pos[atoi[s[b]]][index]
        bisect.insort_left(pos[atoi[c]], b)
        s[b] = c
    else:
        l, r = int(b)-1, int(c)
        ans = 0
        for i in range(26):
            cnt = bisect.bisect_left(pos[i], r) - bisect.bisect_left(pos[i], l)
            if cnt > 0:
                ans += 1
        print(ans)
### BUGGY CODE ###

S=input()
# S="".join(["1" for _ in range(10**4)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    tt = 10**t
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (t,(j*tt+i)%13)
                dp[k] += dp[(t-1,i)]
                dp[k] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (t,(s*tt+i)%13)
            dp[k] += dp[(t-1,i)]
            dp[k] %= MOD

print(dp[(t,5)])

### FIXED CODE ###

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)
### BUGGY CODE ###

N,M = map(int,input().split())
E = [[] for _ in range(N)]
root = [True] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    root[B-1] = False
root = root.index(True)

from collections import deque

dist = [-1] * N
dist[root] = 0
parent = [-1] * N
q = deque([root])
while q:
    par = q.pop()
    for e in E[par]:
        if dist[e] < dist[par] + 1:
            parent[e] = par
            dist[e] = dist[par] + 1
        q.append(e)

for ans in parent:
    print(ans + 1)

### FIXED CODE ###

N,M = map(int,input().split())

# E[i]: 頂点iから伸びる頂点の集合
E = [[] for _ in range(N)]
# parent_cnt[i]: 頂点iの親
parent_cnt = [0] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    parent_cnt[B-1] += 1

# 根を見つける
for i,num in enumerate(parent_cnt):
    if num == 0:
        root = i
        break

parent = [None] * N
parent[root] = 0

q = [root]
# DFS O(N+M)
while q:
    qq = []
    for V in q:
        for Vto in E[V]:
            parent_cnt[Vto] -= 1

            # 親が決定
            if parent_cnt[Vto] == 0:
                parent[Vto] = V + 1
                qq.append(Vto)
    
    q = qq

print(*parent, sep="\n")
### BUGGY CODE ###

a = list(map(int, input().split()))
b = 1
while b <= a[1]:
    c = a[0] * b
    if c % a[1] != 0 and c <= 10 ** 18:
        print(c)
        break
    else:
        b = b + 1
if b == a[1] + 1 or c > 10 ** 18:
    print(-1)

### FIXED CODE ###

a = list(map(int, input().split()))
if a[0] % a[1] == 0:
    print(-1)
else:
    b = 1
    while b <= a[1]:
        c = a[0] * b
        if c % a[1] != 0 and c <= 10 ** 18:
            print(c)
            break
        else:
            b = b + 1
    if b == a[1] + 1 or c > 10 ** 18:
        print(-1)
### BUGGY CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える

N,Q = map(int,input().split())
s = str(input())
T = []
D = []
for i in range(Q):
    t,d = map(str,input().split())
    T.append(t)
    D.append(d)

golem = [1 for i in range(N)]

positions = {}
for i in range(len(s)):
    if s[i] in positions.keys():
        tmp =  positions[s[i]]
        tmp.append(i)
        positions[s[i]] = tmp
    else:
        positions[s[i]] = [i]
# print(positions)
ans = N

for i in range(Q):
    if T[i] in positions.keys():
        move_poss = positions[T[i]]
        # print(golem)
        if D[i] == "R":
            for j in range(len(move_poss))[::-1]:
                if move_poss[j] == N-1:
                    ans -= golem[N-1]
                    golem[N-1] = 0
                else:
                    golem[move_poss[j]+1] += golem[move_poss[j]]
                    golem[move_poss[j]] = 0

        else:
            for j in range(len(move_poss)):
                if move_poss[j] == 0:
                    ans -= golem[0]
                    golem[0] = 0
                else:
                    golem[move_poss[j]-1] += golem[move_poss[j]]
                    golem[move_poss[j]] = 0

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える

N,Q = map(int, input().split())
s = input()
td = [input().split() for i in range(Q)]

td.reverse()

nl = 0
nr = N-1
L = []
R = []
for i in td:#全ての指示
    # print(L,R)
    if i[1]=="L":
        if nl < N:
            if s[nl] == i[0]:
                L.append(i[0])
                nl += 1
            if len(R) != 0:
                if R[-1]==i[0]:
                    R.pop()
                    nr += 1
    else:
        if nr >= 0:
          if s[nr] == i[0]:
            R.append(i[0])
            nr -= 1
        if len(L) != 0:
          if L[-1] == i[0]:
            L.pop()
            nl -= 1

print(N-len(L)-len(R))
### BUGGY CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,c):
    l = -1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            c = arr[i] + arr[j]
            l = arr[j+1:]
            ans += bin_search(l,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------


### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,ls,c):
    l=ls-1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l-ls+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            ans += bin_search(arr,j+1,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------