Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
move=[input().split() for i in range(Q)]
target=[m[0] for m in move]
d=[m[1] for m in move]

def check(i):
    now=i
    t=-1
    while True:
        if S[now] not in target[t+1:]:
            break
        t+=1+target[t+1:].index(S[now])
        if d[t]=="L":
            now-=1
        else:
            now+=1
        if now<0:
            return -1
        if now>=N:
            return 1
    return 0
Lmin=-1
Lmax=N
Rmin=-1
Rmax=N
C=[[1,2]]
while True:
    if len(C)==0:
        break
    c=C.pop()
    now=N*c[0]//c[1]
    x=check(now)
    if x==0:
        if Lmax>now:
            Lmax=now
            C.append([c[0]*2-1,c[1]*2])
        if Rmin<now:
            Rmin=now
            C.append([c[0]*2+1,c[1]*2])
    elif x==1:
        if now<Rmax:
            Rmax=now
            C.append([c[0]*2-1,c[1]*2])
    elif x==-1:
        if Lmin<now:
            Lmin=now
            C.append([c[0]*2+1,c[1]*2])
print(Rmax-Lmin-1)

Fixed submission:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[tuple(input().split()) for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for j in range(Q):
        if move[j][0]==s[now]:
            if move[j][1]=='L':
                now-=1
            elif move[j][1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Fixed submission:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[tuple(input().split()) for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for j in range(Q):
        if move[j][0]==s[now]:
            if move[j][1]=='L':
                now-=1
            elif move[j][1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
from collections import deque
search=deque([(1,2)])
while len(search)>0:
    now=search.popleft()
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            search.append((2*now[0]-1,2*now[1]))
            search.append((2*now[0]+1,2*now[1]))
        elif idx<alive[0]:
            alive[0]=idx
            search.append((2*now[0]-1,2*now[1]))
        elif idx>alive[1]:
            alive[1]=idx
            search.append((2*now[0]+1,2*now[1]))
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            search.append((2*now[0]+1,2*now[1]))
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            search.append((2*now[0]-1,2*now[1]))
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Fixed submission:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
target=''
move=''
for i in range(Q):
    t,d=input().split()
    target+=t
    move+=d
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    time=0
    while time<Q:
        if s[now] in target[time:]:
            idx=time+target[time:].index(s[now])
            if move[idx]=='L':
                now-=1
            elif move[idx]=='R':
                now+=1
            time=idx+1
            if now<0:
                return 'left'
            if now>N-1:
                return 'right'
        elif s[now] not in target[time:]:
            time=Q
    return 'alive'
from collections import deque
search=deque([(1,2)])
while len(search)>0:
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        break
    now=search.popleft()
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            search.append((2*now[0]-1,2*now[1]))
            search.append((2*now[0]+1,2*now[1]))
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1==dead[0]:
                continue
            search.append((2*now[0]-1,2*now[1]))
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1==dead[1]:
                continue
            search.append((2*now[0]+1,2*now[1]))
        elif idx==0 or idx==N-1:
            continue
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1==alive[0]:
                continue
            search.append((2*now[0]+1,2*now[1]))
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1==alive[1]:
                continue
            search.append((2*now[0]-1,2*now[1]))
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Fixed submission:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[tuple(input().split()) for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for j in range(Q):
        if move[j][0]==s[now]:
            if move[j][1]=='L':
                now-=1
            elif move[j][1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
from collections import deque
search=deque([(1,2)])
while len(search)>0:
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        break
    now=search.popleft()
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            search.append((2*now[0]-1,2*now[1]))
            search.append((2*now[0]+1,2*now[1]))
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1==dead[0]:
                continue
            search.append((2*now[0]-1,2*now[1]))
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1==dead[1]:
                continue
            search.append((2*now[0]+1,2*now[1]))
        elif idx==0 or idx==N-1:
            continue
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1==alive[0]:
                continue
            search.append((2*now[0]+1,2*now[1]))
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1==alive[1]:
                continue
            search.append((2*now[0]-1,2*now[1]))
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)

Fixed submission:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)