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

class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time position')

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

    go = []
    stop = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        stop.append(Event(time=s - x, position=x))
        go.append(Event(time=t - x, position=x))
        xs.add(x)

    xs = sorted(xs)

    stop.sort(key=attrgetter('time'))
    go.sort(key=attrgetter('time'))

    stop = deque(stop)
    go = deque(go)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while go and go[0].time <= d:
            e = go.popleft()
            p = compress[e.position]
            b.add(p, -1)
        while stop and stop[0].time <= d:
            e = stop.popleft()
            p = compress[e.position]
            b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        
        return r(root[x])

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    
    root[x]+=root[y]
    root[y]=x

for i in range(m):
    x,y,z=map(int,input().split())
    unite(x,y)


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)



### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[i for i in range(n+1)] #自分が親なら自身の番号を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]==x:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[y]=x

for i in range(m):
    x,y,z=map(int,input().split())
    unite(x,y)

ans=0
for i in range(1,n+1):
    if root[i]==i:
        ans+=1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s += ['0']
    s = [int(c) for c in s]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            for a in (0, nd):
                ni = i+1
                nj = 0
                b = a-nd
                if b < 0:
                    nj = 1
                    b += 10
                if dp[ni][nj] >= dp[i][j]+a+b:
                    dp[ni][nj] = dp[i][j]+a+b
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = list(str(input()))
    s.reverse()
    for i in range(len(s)):
        s[i] = int(s[i])
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

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

N = int()
ans = 0
val = 0
L = list(map(int, input().split()))
while val==0:
  for i in range(N):
    if L[i] % 2 == 0:
      L[i] = L[i] /2
    else:
      val = 1
  ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
v = 0
cnt = 0
while v == 0:
    cnt += 1
    for i in range(N):
        if L[i] % 2 == 0:
            L[i] = L[i] // 2
        else:
            v += 1
print(cnt-1)
### BUGGY CODE ###

import itertools

n,y = map(int,input().split())
a = [10000,5000,1000]
l = list(itertools.combinations_with_replacement(a,n))

for i in range(len(l)):
    if sum(l[i]) == y:
        o = l[i].count(10000)
        p = l[i].count(5000)
        q = l[i].count(1000)
        print(o,p,q)
        exit(0)

print('-1 -1 -1')

### FIXED CODE ###

n,y = map(int,input().split())

for i in range(0,n+1):
    for j in range(0,n+1-i):
        k = max(0,n-i-j)
        if 10000*i + 5000*j + 1000*k == y:
            print(i,j,k)
            exit(0)

print(-1,-1,-1)
### BUGGY CODE ###

#python3

def main():
    h, w = map(int, input().split())
    ss = []
    for _ in range(h):
        s = input()
        ss.append(s)

    sumv = [[0 for _ in range(w)] for _ in range(h)]
    #横方向について連続で何マス続くかを求める
    for i in range(h):
        #doneは連続何マス続くかをすでに求めたかどうかを保持するリスト　
        done = [0 for _ in range(w)]
        for j in range(w):
            #i,jはぞれぞれ縦と横のマスの位置を表すインデックス
            if ss[i][j] == '#':
                continue
            if done[j] == 1:
                continue
            #seqは横に何マス続くかを記録する変数
            seq = 0
            while j + seq < w:
                if ss[i][j+seq] == '#':
                    break
                seq = seq + 1
            #ss[i][j]からss[i][j+seq]までのマスは連続してseqマスである
            for k in range(seq):
                sumv[i][j+k] = sumv[i][j+k] + seq
                #連続するマスが求め終わったマスを記録する
                done[j+k] = 1
    
    #縦方向について同様に
    for j in range(w):
        done = [0 for _ in range(h)]
        for i in range(h):
            if ss[i][j] == '#':
                continue
            if done[i] == 1:
                continue
            seq = 0
            while i + seq < h:
                if ss[i+seq][j] == '#':
                    break
                seq = seq + 1
            for k in range(seq):
                sumv[i+k][j] = sumv[i+k][j] +  seq
                done[i+k] = 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, sumv[i][j]-1)            
    print(ans)
main()




### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
import itertools as it
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy

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

for i in range(0,n):
  a_c=copy.copy(a)
  a_c.pop(i)
  a_uniq=list(set(a_c))
  c=0
  for i in a_uniq:
    x=a_c.count(i)
    c+=x*(x-1)/2
  print('{:.0f}'.format(c))


### FIXED CODE ###

import copy

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

c=0

a_uniq=[0]*(n+1)

for i in a:
  a_uniq[i]+=1

for i in a_uniq:
  c+=sum(range(1,i))
#a_uniq=list(set(a))
#for i in a_uniq:
#  c+=sum(range(1, a.count(i)))

for i in a:
  print('{:.0f}'.format(c-a_uniq[i]+1))
### BUGGY CODE ###

N = int(input())
N_ = int(N**0.5)+2
for i in range(1,N+1):
    ans = 0
    for x in range(1,N_):
        for y in range(1,N_):
            if N <= x*y:
                break
            for z in range(1,N_):
                tmp = x**2+y**2+z**2+x*y+y*z+z*x
                if N <= tmp:
                    break
                if tmp == i:
                    ans += 1

    print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
N_ = int(N**0.5)+2

counter = Counter()
for x in range(1,N_):
    for y in range(1,N_):
        if N <= x**2+y**2+x*y:
            break
        for z in range(1,N_):
            tmp = x**2+y**2+z**2+x*y+y*z+z*x
            if N < tmp:
                break
            counter[tmp] += 1

for i in range(1,N+1):
    print(counter[i])
### BUGGY CODE ###

n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  treasure[i] = sum(1 << c-1 for c in map(int, input().split()))
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << c-1
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

import copy
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
for j in range(N):
    B=copy.copy(A)
    C=B.pop(j)
    print(max(B))

### FIXED CODE ###

import copy
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
a=max(A)
b=A.index(a)
for j in range(N):
    if j!=b:
        print(a)
    else:
        B=copy.copy(A)
        C=B.pop(j)
        print(max(B))
### BUGGY CODE ###

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

### FIXED CODE ###

a = int(input())
b = list(map(int, input().split()))
c = [0 for i in range(a)]
for i in b:
  c[i-1] += 1
for j in c:
  print(j)
### BUGGY CODE ###

import queue
def dist(s, t, g):
    q = queue.Queue()
    dists = [-1]*len(g)
    dists[s] = 0
    q.put(s)
    f = False
    while not q.empty():
        target = q.get()
        for v in g[target]:
            if dists[v] == -1:
                dists[v] = dists[target] + 1
                if v == t:
                    f = True
                    break
                q.put(v)
        if f:
            break
    return dists[t]

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n*3)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v+n)
        g[u+n].append(v+2*n)
        g[u+2*n].append(v)
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(dist(s, t, g)//3)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def dist(s, t, g):
    q = [s]
    dists = [-1]*len(g)
    dists[s] = 0
    while len(q) != 0:
        p = []
        for u in q:
            for v in g[u]:
                if dists[v] != -1:
                    continue
                p.append(v)
                dists[v] = dists[u] + 1
        q = p
    return dists[t]

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n*3)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v+n)
        g[u+n].append(v+2*n)
        g[u+2*n].append(v)
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(dist(s, t, g)//3)

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

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

i = 2
ans = 1
while True:
    if i**N > P:
        break
    if P % i**N == 0:
        P /= i**N
        ans *= i
    else:
        i += 1

print(ans)

### FIXED CODE ###

import os
N, P = map(int, input().split())

def trial_division(n):
    if n < 2:
        return []
    prime_factors = []
    for p in range(2, int( n**0.5)):
        if p*p > n: break
        cnt = 0
        while n % p == 0:
            cnt += 1
            n //= p
        prime_factors.append([p, cnt])
    if n > 1:
        prime_factors.append([n, 1])
    return prime_factors

prime_factors = trial_division(P)
ans = 1
for p in prime_factors:
    if p[1] >= N:
        ans *= p[0]**(p[1] // N)
print(ans)
### BUGGY CODE ###

import itertools
N = int(input())
L = map(int,input().split())
tmp = list(itertools.combinations(L,3))
ans = 0
for i in range(len(tmp)):
    if abs(tmp[i][1] - tmp[i][2]) < tmp[i][0] < (tmp[i][1] + tmp[i][2]):
        ans += 1
print(ans)

### FIXED CODE ###

import itertools
import bisect
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1,N-1):
        b = L[j]
        ind_cmin = j+1
        ind_cmax = bisect.bisect_left(L,a+b)-1
        ans += ind_cmax - ind_cmin + 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
h,w,m = list(map(int,input().split()))

R = [0]*h
C = [0]*w
G = {}

for _ in range(m):
  a,b = list(map(int,input().split()))
  a,b = a-1, b-1
  R[a] += 1
  C[b] += 1
  G[(a,b)] = 1
  
best = 0
for i in range(h):
  for j in range(w):
    cor = 0
    if (i,j) in G:
      cor = 1
    best = max(best,R[i]+C[j] - cor)
    
print(best)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
h,w,m = list(map(int,input().split()))

R = [0]*h
C = [0]*w
G = {}

for _ in range(m):
  a,b = list(map(int,input().split()))
  a,b = a-1, b-1
  R[a] += 1
  C[b] += 1
  G[(a,b)] = 1
  
hhh = max(R)
ccc = max(C)
hei,wei = [],[]

for i in range(h):
  if R[i]==hhh:
    hei.append(i)
    
for i in range(w):
  if C[i]==ccc:
    wei.append(i)
  
  
best = 0
for i in hei:
  for j in wei:
    cor = 0
    if (i,j) in G:
      cor = 1
    best = max(best,R[i]+C[j] - cor)
    if cor==0:
      break
  if cor==0:
      break
      
print(best)
### BUGGY CODE ###

import copy

t_list = []
n, m, q = map(int, input().split())
for i in range(q):
    t_list.append(list(map(int, input().split())))

q = []

for i in range(1, m+1):
    q.append([i])

while True:
    if len(q[0]) == n:
        break
    else:
        item = q.pop(0)
        for i in range(item[-1], m+1):
            tmp = copy.deepcopy(item)
            tmp.append(i)
            q.append(tmp)

ret = 0

for item in q:
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - item[t_item[0]-1] == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)


### FIXED CODE ###

import itertools

t_list = []
n, m, q = map(int, input().split())
for i in range(q):
    t_list.append(list(map(int, input().split())))

q = []

for i in range(1, m+1):
    q.append(i)

ret = 0

for item in itertools.combinations_with_replacement(q, n):
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - item[t_item[0]-1] == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)
### BUGGY CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N, P = MI()
g = 1
mod = 1
ans = 0

if N > 40:
    print(1)
    exit()

while mod <= P:
    mod = pow(g, N)
    
    if P % mod == 0:
        ans = max(ans, g)
    
    g += 1
    mod = pow(g, N)
    
print(ans)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

def factrize(P):
    fac = {}
    
    for i in range(2, int(P**0.5) + 1):
        e = 0
        while P % i == 0:
            P //= i
            e += 1
            
        if e > 0:
            fac[i] = e
    
    if P > 1:
        fac[P] = 1
    
    return fac

N, P = MI()
ans = 1

for f, e in factrize(P).items():
    if e >= N:
        ans *= f**(e // N)
        
print(ans)
### BUGGY CODE ###

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

for i in range(1, n+1):
  for j in range(1, n+1):
    if a[j-1] == i:
      list.append(str(j))
print(' '.join(list))

### FIXED CODE ###

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

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

import sys
sys.setrecursionlimit(10000000)

f_inf = float("inf") # sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

max_num_sum = (N * (N + 1)) // 2

def solve(pos, cnt, num_sum):
    global cost

    if not(pos in ABC_d): return
    if cnt > N or num_sum > max_num_sum:
        cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        # elif cost[pos-1] == f_inf:
        #     cost[B-1] = f_inf
        #     solve(B, cnt + 1, num_sum + B)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1, num_sum + B)


solve(1, 1, 1)

if (cost[-1] == f_inf):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (W*H)
matS = matE = 0
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = dpr

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] < 0:
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = cnt+1

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
X = [1 for i in range(N)]
s = [x for x in input()]

for i in range(Q):
    t, d = input().split()
    if d == 'L':
        for j in range(N):
            if s[j] == t:
                if j != 0:
                    X[j-1] += X[j]
                X[j] = 0
    elif d == 'R':
        for j in range(N, 0, -1):
            if s[j-1] == t:
                if j != N:
                    X[j] += X[j-1]
                X[j-1] = 0
print(sum(X))

### FIXED CODE ###

def check_alive(n):
    p = n
    for spell in spells:
        if spell[0] == s[p]:
            p += 1 if spell[1] == 'R' else -1
        if p == -1:
            return 'L'
        elif p == N:
            return 'R'
    return 'OK'

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

def __main__():
    if check_alive(0) == 'R':
        print(0)
        return
    elif check_alive(0) == 'OK':
        left_alive = 0
    else:
        a, b = 0, N-1
        while b - a > 1:
            m = round((b+a)/2)
            if check_alive(m) == 'L':
                a = m
            else:
                b = m
        left_alive = b
    if check_alive(N-1) == 'L':
        print(0)
        return
    elif check_alive(N-1) == 'OK':
        right_alive = N-1
    else:
        a, b = 0, N-1
        while b - a > 1:
            m = round((b+a)/2)
            if check_alive(m) == 'R':
                b = m
            else:
                a = m
        right_alive = a
    
    print(right_alive - left_alive + 1)

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

import sys
sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

goal_cnt = [10**20]
def dfs(x, y, cnt):
    if cnt >= goal_cnt[0]:
        return
    if field[y][x] == "#":
        cnt += 1
    if x == W-1 and y == H-1:
        goal_cnt[0] = min(goal_cnt[0], cnt)
        return
    for nx, ny in ((1,0),(0,1)):
        nx += x
        ny += y
        if nx >= W or ny >= H:
            continue
        dfs(nx, ny, cnt)

dfs(0,0,0)
print(goal_cnt[0])


### FIXED CODE ###

H, W = map(int, input().split())
#field = [list(input()) for _ in range(H)]
field =[["."] * (W+1)]
for _ in range(H):
    tmp = ["."]
    tmp.extend(list(input()))
    field.append(tmp)

dp = [[10**9] * (W+1) for _ in range(H+1)]
dp[1][0] = 0
dp[0][1] = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        if field[h][w] == ".":
            dp[h][w] = min(dp[h-1][w], dp[h][w-1])
        else:
            u = dp[h-1][w] if field[h-1][w] == "#" else dp[h-1][w] + 1
            l = dp[h][w-1] if field[h][w-1] == "#" else dp[h][w-1] + 1
            dp[h][w] = min(u,l)

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