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

def solve(n, ga, sa, ba, gb, sb, bb):
    gd, sd, bd = gb - ga, sb - sa, bb - ba

    if bd <= 0:
        if sd <= 0:
            if gd <= 0:
                return n
            return n + n // ga * gd
        if gd <= 0:
            return n + n // sa * sd
        return max(n + g * gd + (n - g * ga) // sa * sd for g in range(n // ga + 1))
    if sd <= 0:
        if gd <= 0:
            return n + n // ba * bd
        return max(n + g * gd + (n - g * ga) // ba * bd for g in range(n // ga + 1))
    if gd <= 0:
        return max(n + s * sd + (n - s * sa) // ba * bd for s in range(n // sa + 1))
    (_, ga, gd), (_, sa, sd), (_, ba, bd) = \
        sorted([(gb / ga, -ga, gd), (sb / sa, -sa, sd), (bb / ba, -ba, bd)], reverse=True)
    ga, sa, ba = -ga, -sa, -ba
    return max(n + g * gd + s * sd + (n - g * ga - s * sa) // ba * bd
               for g in range(n // ga // 3, n // ga + 1)
               for s in range((n - g * ga) // sa + 1))


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)


### FIXED CODE ###

def solve(n, ga, sa, ba, gb, sb, bb):
    ans = n
    for g in range(1 if ga >= gb else n // ga + 1):
        n2 = n - g * ga
        tmp1 = g * gb
        if ba >= bb:
            s = n2 // sa
            ans = max(ans, n2 + tmp1, n2 - s * sa + tmp1 + s * sb)
        elif sa >= sb:
            b = n2 // ba
            ans = max(ans, n2 + tmp1, n2 - b * ba + tmp1 + b * bb)
        else:
            for s in range(n2 // sa + 1):
                b = (n2 - s * sa) // ba
                ans = max(ans, n2 - s * sa - b * ba + tmp1 + s * sb + b * bb)
    return ans


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)
### BUGGY CODE ###

def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


Q = int(input())
prime_list = [None] * 100001
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r+1, 2):
        i2 = (i + 1) // 2
        if prime_list[i] == None:
            prime_list[i] = is_prime(i)
        if prime_list[i2] == None:
            prime_list[i2] = is_prime(i2)
        ans += 1 if prime_list[i] and prime_list[i2] else 0
    print(ans)


### FIXED CODE ###

def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


Q = int(input())
prime_list = [False] * 100001
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
a = [0] * 100001
prime_list[2] = True
for i in range(1, 100001):
    prime_list[i] = is_prime(i)
    if prime_list[i] and prime_list[(i+1)//2]:
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
for i in range(Q):
    ans = a[R[i]] - a[L[i]-1]
    print(ans)
### BUGGY CODE ###

import sys
import bisect
input=sys.stdin.readline

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

a.sort()

e=a[:n-m]
d=a[n-m:]

for _ in range(m):
    val=d.pop()//2
    bisect.insort(d, val)

print(sum(e)+sum(d))


### FIXED CODE ###

import sys
import heapq
import numpy as np
input=sys.stdin.readline

n,m=map(int, input().split())
a=list(map(int, input().split()))
h=[]
for val in a:
    heapq.heappush(h, -val)

for _ in range(m):
    val=(-heapq.heappop(h))//2
    heapq.heappush(h, -val)

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

import math

N, K = map(int, input().split())
K = min(41, K)
A = list(map(int, input().split()))
A.insert(0, 0)
ans = [N] * N

def operation():
  global A, N
  B = [0] * (N+1)
  for i in range(1, N+1):
    left = max(1, math.ceil(i - A[i] - 0.5))
    right = min(N, math.floor(i + A[i] + 0.5))
    B[left] += 1
    if right+1 <= N:
      B[right+1] -= 1
  for i in range(1, N+1):
    B[i] += B[i-1]
  return B


operation()

#print(A)
#print(B)

for _ in range(K):
  A = operation()

print(*A[1:])



### FIXED CODE ###

import math

N, K = map(int, input().split())
K = min(41, K)
A = list(map(int, input().split()))
A.insert(0, 0)

def operation():
  global A, N
  B = [0] * (N+1)
  for i in range(1, N+1):
    left = max(1, math.ceil(i - A[i] - 0.5))
    right = min(N, math.floor(i + A[i] + 0.5))
    B[left] += 1
    if right+1 <= N:
      B[right+1] -= 1
  for i in range(1, N+1):
    B[i] += B[i-1]
  return B


operation()

#print(A)
#print(B)

for _ in range(K):
  A = operation()

print(*A[1:])
### BUGGY CODE ###

from functools import reduce
import sys
import operator
n = int(input())
l = list(map(int,input().split()))
a = reduce(operator.mul,l)
if a > 10**18:
    print("-1")
    sys.exit()
print(a)

### FIXED CODE ###

import sys
n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 1
for i in l:
    count= count*i
    if count == 0:
        print("0")
        sys.exit()
    elif count > 10**18:
        print("-1")
        sys.exit()
if count > 10**18:
    print("-1")
    sys.exit()
print(count)
### BUGGY CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n = i_input()
    l = i_list()
    l.sort()
    ans = 0
    for i in range(len(l)):
        for k in range(i+1,len(l)):
            for u in range(k+1,len(l)):
                a = l[i]
                b = l[k]
                c = l[u]
                if b < a+c and c < a+b:
                    ans += 1
                if a+b < c:
                    break
    print(ans)

if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    import bisect
    n = i_input()
    l = sorted(i_list())
    ans = 0
    for a in range(n-2):
        for b in range(a+1,n-1):
            ans += bisect.bisect(l, l[a]+l[b]-1) -b-1
    print(ans)

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

S = list(input())
T = list(input())
r = "Yes"
for i in range(len(S)):
    s1 = S[i]
    t1 = T[i]
    s_bit = list(map(lambda x:1 if x==s1 else 0, S))
    t_bit = list(map(lambda x:1 if x==t1 else 0, T))
    if s_bit != t_bit:
        r = "No"
        break
print(r)

### FIXED CODE ###

import numpy as np
S = list(input())
T = list(input())
r = "Yes"
end_list = np.array([0] * len(S))
for i in range(len(S)):
    if end_list[i] == 0:
        s1 = S[i]
        t1 = T[i]
        s_bit = list(map(lambda x:1 if x==s1 else 0, S))
        t_bit = list(map(lambda x:1 if x==t1 else 0, T))
        if s_bit != t_bit:
            r = "No"
            break
        end_list += np.array(s_bit)
print(r)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import bisect

def main():
    _,M= map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    
    B = []
    for _ in range(M):
        b,c = map(int,input().split())
        B.append((b,c))
    B.sort(key=lambda x: x[1])

    x = 0
    while B:
        b,c = B.pop()
        n = bisect.bisect(A,c,hi=min(b,len(A)))
        x += n*c
        A = A[n:]

    print(x + sum(A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import bisect

def main():
    _,M= map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    
    B = []
    for _ in range(M):
        b,c = map(int,input().split())
        B.append((b,c))
    B.sort(key=lambda x: x[1])

    x = 0
    m = 0
    while B:
        b,c = B.pop()
        n = bisect.bisect(A,c,lo=m,hi=min(m+b,len(A)))
        x += (n-m)*c
        m = n

    print(x + sum(A[n:]))

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

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    for k in range(K):
        next_A = [0 for i in range(N)]
        for i in range(len(A)):
            high = i + A[i] + 1
            if high > N:
                high = N
            low = i - A[i]
            if low < 0:
                low = 0
            for j in range(low,high):
                next_A[j] += 1
        A = next_A
    
    print(*A)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    if K > 41:
        K = 41
    
    for k in range(K):
        B = [0 for i in range(N)]
        for i in range(N):
            low = max(0,i-A[i])
            high = min(N-1,i+A[i])
            B[low] += 1
            if high+1 < N:
                B[high+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    
    print(*A)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**6)
INF = 10**12

N, Z, W = map(int, input().split())
a = [Z] + list(map(int, input().split()))
# print(a)

def rec(X,Y,i,count):# i枚目まで取った
    if i == N:# 山札がないので得点計算して更新
        return abs(X-Y)
    else:
        if count % 2 == 0:# 今はXのターン
            tmp = []
            for j in range(i+1,N+1):
                # print(i,j,count)
                tmp.append(rec(a[j], Y, j, count+1))
            return max(tmp)
        else:# 今はYのターン
            tmp = []
            for j in range(i+1,N+1):
                # print(i,j,count)
                tmp.append(rec(X, a[j], j, count+1))
            return min(tmp)

ans = rec(Z,W,0,0)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))

if N == 1:
    print(abs(a[0] - W))
else:
    print(max(abs(a[-1]-W), abs(a[-1]-a[-2])))
### BUGGY CODE ###

N, M = list(map(int, input().split()))
C = list(map(int, input().split()))
C = sorted(C)
AB = [list(map(int, input().split())) for i in range(M)]
AB = sorted([ab[1] for ab in AB for i in range(ab[0])], reverse=True)

result = sum(C)
for i in range(len(AB)):
  if i >= N or AB[i] <= C[i]:
    break
  result += AB[i] - C[i]
print(result)

### FIXED CODE ###

def main():
  N, M = list(map(int, input().split()))
  C = list(map(int, input().split()))
  C = sorted(C)
  AB = [list(map(int, input().split())) for i in range(M)]
  AB = sorted(AB, key=lambda x: x[1], reverse=True)
  
  result = 0
  i, j = 0, 0
  while i < N:
    A, B = AB[j] if j < M else (0, 0)
    j += 1
    if i+A < N and B >= C[i+A]:
      i += A
      result += A * B
    else:
      break
    
  while i < N:
    if C[i] > B:
      result += sum(C[i:])
      break
    else:
      result += B
      A -= 1      
      if j < M and A == 0:
        A, B = AB[j] if j < M else (0, 0)
        j += 1
    
    i += 1
  
  print(result)

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

from itertools import product, compress

N = int(input())
Ss = input()

Fss = [list(compress(Ss[:N], sels))[::-1] for sels in product([0, 1], repeat=N)]

ans = 0
for iFs in range(2 ** N):
    Fs = Fss[iFs]
    Gs = Fss[2 ** N - 1 - iFs]

    lenF = len(Fs)
    lenG = N - lenF
    dp = [1] + [0] * lenF
    for i, s in enumerate(Ss[N:], 1):
        dp2 = [0] * (lenF + 1)
        flg = False
        for j in range(lenF + 1):
            if 0 <= j-1 and s == Fs[j-1]:
                dp2[j] += dp[j-1]
            if 0 <= i-j-1 < lenG and s == Gs[i-j-1]:
                dp2[j] += dp[j]
            if dp2[j]:
                flg = True
        dp = dp2
        if not flg: break

    ans += dp[lenF]

print(ans)


### FIXED CODE ###

from itertools import product, compress

N = int(input())
Ss = input()

Fss = [list(compress(Ss[:N], sels))[::-1] for sels in product([0, 1], repeat=N)]

ans = 0
for iFs in range(2 ** N):
    Fs = Fss[iFs]
    Gs = Fss[2 ** N - 1 - iFs]

    lenF = len(Fs)
    lenG = N - lenF
    dp = [1] + [0] * lenF
    for i, s in enumerate(Ss[N:]):
        dp2 = [0] * (lenF + 1)
        for j in range(lenF + 1):
            if dp[j] == 0: continue
            if j < lenF and s == Fs[j]:
                dp2[j+1] += dp[j]
            if 0 <= i-j < lenG and s == Gs[i-j]:
                dp2[j] += dp[j]
        dp = dp2

    ans += dp[lenF]

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

n = int(input())

if n == 1:
    print(0)
else:
    print(sum(range(n)))


### FIXED CODE ###

n = int(input())

if n == 1:
    print(0)
else:
    print(sum(range(n)))
### BUGGY CODE ###

k,s=map(int,input().split())
counter=0

for x in range(k+1):
	for y in range(k+1):
		for z in range(k+1):
			if x+y+z==s:
				counter+=1

print(counter)


### FIXED CODE ###

k,s=map(int,input().split())
counter=0

for x in range(k+1):
	for y in range(k+1):
		if 0<=s-x-y<=k:
			counter+=1

print(counter)
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
  return sn

base = create_list()
#print(base)
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )
### BUGGY CODE ###

import os, sys, re, math

n = int(input())
a = list(map(int,input().split(' ')))


cnt = 0
while True:
    a.sort(reverse=True)
    if (sum(map(lambda x: x % 2, a))) == n:
        break
    flg = False
    for i in range(n):
        if a[i] % 2 == 0 and flg == False:
            a[i] = a[i] // 2
            flg = True
        else:
            a[i] = a[i] * 3
    cnt += 1

print(cnt)


### FIXED CODE ###

import os, sys, re, math

n = int(input())
a = list(map(int,input().split(' ')))


cnt = 0
for ai in a:
    while ai % 2 == 0:
        cnt += 1
        ai = ai // 2
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 1
for i in range(n):
    sum = sum * a[i]

if sum > 10**18:
    print('-1')
else:
    print(sum)



### FIXED CODE ###

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

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

print(sum([sum(A[i:j])==0 for i in range(0,N) for j in range(i+1,N+1)]))

### FIXED CODE ###

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

B = {}
B[0] = 1

s = 0
ans = 0

for a in A:
    s += a
    ans += B.get(s,0)
    B[s] = B.get(s,0)+1

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

k, s = map(int, input().split())
apple = [i + j + l for i in range(k + 1) for j in range(k + 1) for l in range(k + 1)]
print(apple.count(s))

### FIXED CODE ###

k, s = map(int, input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0 <= s-z-y <= k]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
X,Y = (int(x) for x in input().split())
def route(x,y):
    d = min(x,y) - ((x+y)//3)
    if d == 0:
        return 1
    else:
        return (route(x-2,y-1) + route(x-1,y-2))%1000000007
if (X+Y) % 3 != 0 or min(X,Y) < (X+Y) // 3:
    print('0')
else:
    print(route(X,Y))

### FIXED CODE ###

from functools import reduce
X,Y = (int(x) for x in input().split())
def route(x,y):
    d = min(x,y) - ((x+y)//3)
    if d == 0:
        return 1
    else:
        return (route(x-2,y-1) + route(x-1,y-2))%1000000007
def modmul(a,b):
    return a * b % 1000000007
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 1000000007)
if (X+Y) % 3 != 0 or min(X,Y) < (X+Y) // 3:
    print('0')
else:
    d = min(X,Y) - ((X+Y)//3)
    if d == 0:
        print('1')
    else:
        t = (X+Y) // 3
        print((comb(t-1,d)+comb(t-1,d-1))%1000000007)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
sum_n = [0]*n
sumall = sum(l)
sum_n = list(sumall-sum(l[:i+1]) for i in range(n))
for i in range(n):
    ans += ((l[i]*sum_n[i])%1000000007)
print(ans%1000000007)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
sum_n = [0]*n
sum_n[0] = l[0]
sumall = sum(l)
for i in range(1,n):
    sum_n[i] = sum_n[i-1] + l[i]
for i in range(n):
    ans += ((l[i]*(sumall-sum_n[i]))%1000000007)
print(ans%1000000007)
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
arr = [0]
ans = 0
for i, j in enumerate(a):
    arr.append(arr[i] + j)

_set = set(arr)
for i in _set:
    c = arr.count(i)
    if c == 2:
        ans += 1
    elif c > 2:
        ans += len(list(itertools.combinations(range(c), 2)))

print(ans)

### FIXED CODE ###

import itertools
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
arr = [0]
arr += list(itertools.accumulate(a))
ans = 0

c = Counter(arr)
for v in c.values():
    if v > 1:
        ans += v * (v - 1) // 2

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

import sys
input = sys.stdin.readline
N,Q = [int(n) for n in input().split()]
S = "f" + str(input()) + "f"
# print(S)
t = [""]*Q
d = [""]*Q
for i in range(Q):
    t[i],d[i] = [str(n) for n in input().split()]

#左に落ちるやつで一番右のゴーレムのインデックスを探す
def leftbinarysearch():
    l = 0
    r = N + 1
    cnt = 0#デバグ用カウンタ
    while(l<r):
        m = (l+r)//2 + 1#探索範囲の中央値のIndexのゴーレムでシミュレーション
        cur = m#探す一つのゴーレムの現在地
        fall = False
        # print(l,r,m)
        for i in range(Q):
            if t[i] == S[cur]:
                if d[i] == "L":
                    cur-=1
                else:
                    cur+=1
                if(cur == 0):#左端に落ちるなら次はもっと右のやつを確かめる
                    l = m
                    fall = True
                    break
                elif(cur == N+1):#右端に落ちるなら下の処理に飛ぶ
                    break
        if not fall:#落ちなかったならそれより左端を探す
            r = m - 1
        cnt+=1
        # if(cnt == 10):print("loop", file=sys.stderr);break;
    return l

#→に落ちるやつを返す
def rightbinarysearch():
        l = 0
        r = N + 1
        cnt = 0
        while(l<r):
            m = (l+r)//2#探索範囲の中央値のIndexのゴーレムでシミュレーション
            cur = m#探す一つのゴーレムの現在地
            fall = False
            # print(l,r,m)
            for i in range(Q):
                if t[i] == S[cur]:
                    if d[i] == "L":
                        cur-=1
                    else:
                        cur+=1
                    if(cur == N+1):#右端に落ちるなら次はもっと左のやつを確かめる
                        r = m
                        fall = True
                        break
                    elif(cur == -1):#左端に落ちるなら下の処理まで飛ぶ
                        break
            if not fall:#落ちなかったならそれより右端を探す
                l = m + 1
            cnt+=1
            # if(cnt == 10):print("loop", file=sys.stderr);break;
        return l
# print(rightbinarysearch())
# print(leftbinarysearch())
print(rightbinarysearch()-leftbinarysearch()-1)


### FIXED CODE ###

n, q = [int(_) for _ in input().split()]
s = input()

Q = [(input().split()) for i in range(q)]
Q.reverse()
l = 0
r = n - 1
for t,d in Q:
    if s[l] == t and d == "L":
        l += 1
    elif l > 0 and s[l - 1] == t and d == "R":
        l -= 1
    if s[r] == t and d == "R":
        r -= 1
    elif r < n - 1 and s[r + 1] == t and d == "L":
        r += 1
    # print(r,l,r-l+1)
    if l > r:
        break
print(r - l + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

counts = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    counts[p-1] += x


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        counts[v2] += counts[v]
        dfs(v2, v)


dfs(0, -1)
print(*counts)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())

graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)

values = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    values[p-1] += x

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])

dfs(0, 0, 0)
print(*values)