Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02814 (python)

Fixed submission:
from fractions import gcd

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    B = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        B.sort()
        g = 1
        for b in B:
            l = gcd(b, g)
            g = g*b//l
            if g > M:
                ok = False
                break
        if not ok:
            print(0)
        else:
            p = g*2**(c-1)
            ans = (M+p)//(2*p)
            print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import numpy as np

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    B = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        g = np.lcm.reduce(B)
        p = g*2**(c-1)
        ans = (M+p)//(2*p)
        print(ans)

if __name__ == "__main__":
    main()
Problem p02839 (python)

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    P = W+1
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80
    dp = [[False]*(L+1) for _ in range((W+1)*(H+1))]
    dp[P+1][abs(A[0][0]-B[0][0])] = True
    
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0: continue
            c = abs(A[h][w] - B[h][w])
            for l in range(L-c+1):
                b1 = abs(l-c)
                b2 = abs(l+c)
                dp[(h+1)*P+w+1][l] = dp[h*P+w+1][b1] or dp[(h+1)*P+w][b1] or dp[h*P+w+1][b2] or dp[(h+1)*P+w][b2]

    for l in range(L+1):
        if dp[H*P+W][l]:
            print(l)
            break


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80*4
    mid = L//2
    dp = [[[False]*(L+1) for _ in range(W+1)] for _ in range(H+1)]
    for h in range(H+1):
        dp[h][0][mid] = True
    for w in range(H+1):
        dp[0][w][mid] = True
    
    for h in range(H):
        for w in range(W):
            for l in range(L+1):
                c = A[h][w] - B[h][w]
                if 0 <= l-c <= L:
                    dp[h+1][w+1][l] = dp[h][w+1][l-c] or dp[h+1][w][l-c]
                if 0 <= l+c <= L:
                    dp[h+1][w+1][l] = dp[h+1][w+1][l] or dp[h][w+1][l+c] or dp[h+1][w][l+c]
    ans = 10**9
    for l in range(L+1):
        if dp[H][W][l]:
            ans = min(abs(l-mid), ans)
    print(ans)


if __name__ == "__main__":
    main()
Problem p02840 (python)

Fixed submission:
import sys
input = sys.stdin.readline

N, X, D = map(int, input().split())

if D == 0:
    ans = N+1 if X != 0 else 1
else:
    C = {}
    Que = {}
    for l in range(N+1):
        start = l*X//D + l*(l-1)//2
        end = start + l*(N-l)
        key = l*X%D
        if key in Que:
            Que[key].append((start, end))
            C[key] += [start, end, start+1, end+1, start-1, end-1]
        else:
            Que[key] = [(start, end)]
            C[key] = [start, end, start+1, end+1, start-1, end-1]


    ans = 0
    for key, List in C.items():
        ind_to_co = sorted(list(set(List)))
        co_to_ind = {a:i for i, a in enumerate(ind_to_co)}

        Imos = [0]*(len(ind_to_co)+1)
        for start, end in Que[key]:
            Imos[co_to_ind[start]] += 1
            Imos[co_to_ind[end+1]] -= 1

        for i in range(len(ind_to_co)-1):
            a = ind_to_co[i]; b = ind_to_co[i+1]
            Imos[i+1] += Imos[i]
            if Imos[i+1] > 0 and Imos[i] > 0:
                ans += b-a
            elif Imos[i] > 0:
                ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, X, D = map(int, input().split())

C = {}
Que = {}
for l in range(N+1):
    start = l*X//D + l*(l-1)//2
    end = start + l*(N-l)
    key = l*X%D
    if key in Que:
        Que[key].append((start, end))
        C[key] += [start, end, start+1, end+1, start-1, end-1]
    else:
        Que[key] = [(start, end)]
        C[key] = [start, end, start+1, end+1, start-1, end-1]


ans = 0
for key, List in C.items():
    ind_to_co = sorted(list(set(List)))
    co_to_ind = {a:i for i, a in enumerate(ind_to_co)}

    Imos = [0]*(len(ind_to_co)+1)
    for start, end in Que[key]:
        Imos[co_to_ind[start]] += 1
        Imos[co_to_ind[end+1]] -= 1

    for i in range(len(ind_to_co)-1):
        a = ind_to_co[i]; b = ind_to_co[i+1]
        Imos[i+1] += Imos[i]
        if Imos[i+1] > 0 and Imos[i] > 0:
            ans += b-a
        elif Imos[i] > 0:
            ans += 1
print(ans)
Problem p02918 (python)

Fixed submission:
N, K = map(int, input().split())
S = list(input())

c = 0
p = 0
for i, s in enumerate(S):
    if i == 0:
        pres = s
        continue
    elif s != pres:
        c += 1
    else:
        p += 1
    pres = s

if c == 0 or c == 1 or c <= 2*K:
    ans = N-1
else:
    ans = p+2*K
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
S = list(input())

sl = 0
for i in range(N-1, -1, -1):
    if S[i] == S[0]:
        sr = i
        break
    else:
        sl += 1
if sl == 0:
    sl = 1
r = sr
l = 0
change = 0
while l<=r and change <= K:
    if S[l] != S[l+1]:
        if S[r] != S[r-1]:
            change += 1
            l += 1
            r -= 1
        else:
            r -= 1
    else:
        l += 1
if change < K:
    ans = N-1
else:
    if r < l:
        ans = sr + sl-1
    else:
        ans = l-1 + (sr-r-1) + sl-1
        for i in range(l, r):
            if S[i] == S[i+1]:
                ans += 1
print(ans)
Problem p02936 (python)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(900000)


N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
PX = [list(map(int, input().split())) for _ in range(Q)]

def dfs(p, s, checked, score):
    #print(p, s, score)
    ns = s + score[p]
    score[p] += s
    for q in graph[p]:
        if not checked[q]:
            checked[q] = True
            score = dfs(q, ns, checked, score)
    return score


def main():


    score = [0 for _ in range(N)]
    for p, x in PX:
        score[p-1] += x

    checked = [False for _ in range(N)]
    checked[0] = True
    
    ans = dfs(0, 0, checked, score)
    print(' '.join([str(a) for a in ans]))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    PX = [list(map(int, input().split())) for _ in range(Q)]

    score = [0 for _ in range(N)]
    for p, x in PX:
        score[p-1] += x

    checked = [False for _ in range(N)]
    checked[0] = True
    def dfs(p, s, checked, score):
        #print(p, s, score)
        ns = s + score[p]
        score[p] += s
        for q in graph[p]:
            if not checked[q]:
                checked[q] = True
                score = dfs(q, ns, checked, score)
        return score

    ans = dfs(0, 0, checked, score)
    print(' '.join([str(a) for a in ans]))


if __name__ == "__main__":
    main()
Problem p02949 (python)

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    Edges = [list(map(int, input().split())) for _ in range(M)]
    INF = 10**18

    graph1 = [[] for _ in range(N+1)]
    graph2 = [[] for _ in range(N+1)]
    for a, b, c in Edges:
        graph1[a].append(b)
        graph2[b].append(a)

    checked1 = [False]*(N+1)
    checked1[1] = True
    q = [1]
    while q:
        qq = []
        for p in q:
            for np in graph1[p]:
                if not checked1[np]:
                    checked1[np] = True
                    qq.append(np)
        q = qq
    
    checked2 = [False]*(N+1)
    checked2[N] = True
    q = [N]
    while q:
        qq = []
        for p in q:
            for np in graph2[p]:
                if not checked2[np]:
                    checked2[np] = True
                    qq.append(np)
        q = qq
    
    Canuse = [False]*(N+1)
    for i in range(1, N+1):
        if checked1[i] and checked2[i]:
            Canuse[i] = True



    D = [INF for _ in range(N+1)]
    D[1] = 0
    for i in range(2*N+100):
        update = False
        for a, b, c in Edges:
            if not Canuse[a] or not Canuse[b]: continue
            if D[b] > D[a] + P - c:
                D[b] = D[a] + P - c
                update = True


    if update:
        print(-1)
    else:
        print(max(-D[N], 0))

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M, P = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a-1].append([b-1, c-P])

def dfs(p, dis, maxd):
    for q, d in graph[p]:
        if q == p:
            continue
        if q == N-1:
            if dis+d > maxd:
                maxd = dis+d
            return maxd
        maxd = dfs(q, dis+d, maxd)
    return maxd

ans = dfs(0, 0, 0)
for q, d in graph[N-1]:
    if N-1 == q:
        ans = -1

print(ans)
Problem p02975 (python)

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

x = False
k = {}
for i in range(N):
    if not A[i] in k:
        k[A[i]] = 1
    else:
        k[A[i]] += 1
B = 0
a = 0
if len(k.keys()) == 3:
    B = 0
    for key, val in k.items():
        if val == N // 3:
            a += 1
        B = B ^ key
elif len(k.keys()) == 2:
    for key, val in k.items():
        if val == N // 3 and key == 0:
            a += 1
        elif val == N // 3 * 2:
            a += 2
    B = 0
elif len(k.keys()) == 1:
    a = list(k.keys())
    if a[0] == 0:
        x = True

if (N % 3 == 0 and B == 0 and a == 3) or x:
    ans = 'Yes'
else:
    ans = 'No'

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

k = {}
for i in range(N):
    if not A[i] in k:
        k[A[i]] = 1
    else:
        k[A[i]] += 1

a = 0
if len(k.keys()) == 3:
    B = 0
    for key, val in k.items():
        if val == N // 3:
            a += 1
        B = B ^ key
elif len(k.keys()) == 2:
    for key, val in k.items():
        if val == N // 3 and key == 0:
            a += 1
        elif val == N // 3 * 2:
            a += 2
    B = 0

if N % 3 == 0 and B == 0 and a == 3:
    ans = 'Yes'
else:
    ans = 'No'

print(ans)
Problem p02992 (python)

Fixed submission:
N, K = map(int, input().split())
mod = 10**9+7

n = 1
A = []
while True:
    A.append(N//n)
    if N//(n+1) < n+1: break
    n += 1
A.append(n)

L = 2*n
dp = [[0]*L for _ in range(K)]
for l in range(n):
    dp[0][l] = 1

i = 0
for l in reversed(range(n, L)):
    dp[0][l] = A[i] - A[i+1]
    i += 1

for k in range(1, K):
    s = 0
    for l in reversed(range(L)):
        s = (s+dp[k-1][L-l-1]) % mod
        dp[k][l] = s * dp[0][l] % mod

ans = 0
for l in range(L):
    ans = (ans + dp[K-1][l]) % mod

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import math
import copy
N, K = map(int, input().split())

mod = 10**9+7

Keys = set()
for n in range(1, int(math.sqrt(N))+2):
    Keys.add(n)
    Keys.add(N//n)

L = sorted(list(Keys))
Counts = {1: 1}
for i in range(len(L)-1):
    Counts[L[i+1]] = L[i+1]-L[i]

dp = copy.copy(Counts)
for _ in range(K-1):
    sdp = {}
    c = 0
    for l in L:
        c = (c + dp[l]) % mod
        sdp[l] = c

    for l in L:
        r = N//l
        dp[l] = sdp[r] * Counts[l] % mod

ans = 0
for v in dp.values():
    ans = (ans + v) % mod
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import math
import copy
N, K = map(int, input().split())

mod = 10**9+7

Keys = set()
for n in range(1, int(math.sqrt(N))+2):
    Keys.add(n)
    Keys.add(N//n)

L = sorted(list(Keys))
Counts = {1: 1}
for i in range(len(L)-1):
    Counts[L[i+1]] = L[i+1]-L[i]

dp = copy.copy(Counts)
for _ in range(K-1):
    sdp = {}
    c = 0
    for l in L:
        c = (c + dp[l]) % mod
        sdp[l] = c

    for l in L:
        r = N//l
        dp[l] = sdp[r] * Counts[l] % mod

ans = 0
for v in dp.values():
    ans = (ans + v) % mod
print(ans)
Problem p02995 (python)

Fixed submission:
A, B, C, D = map(int, input().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

A_C = A // C
A_D = A // D
A_CD = A // lcm(C, D)

B_C = B // C
B_D = B // D
B_CD = B // lcm(C, D)

A_e = A - (A_C + A_D - A_CD)
B_e = B - (B_C + B_D - B_CD)

if A % C == 0 or A % D == 0:
    ans = B_e - A_e
else:
    ans = B_e - A_e + 1
print(ans)

Buggy submission (verdict: Runtime Error):
import math

A, B, C, D = map(int, input().split())

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A_C = A // C
A_D = A // D
A_CD = A // lcm(C, D)

B_C = B // C
B_D = B // D
B_CD = B // lcm(C, D)

A_e = A - (A_C + A_D - A_CD)
B_e = B - (B_C + B_D - B_CD)

if A % C == 0 or A % D == 0:
    ans = B_e - A_e
else:
    ans = B_e - A_e + 1
print(ans)
Problem p03032 (python)

Fixed submission:
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for k in range(K+1):
    for n in range(k+1):
        if n >= N or k > N:
            break
        A = V[:n]
        A.extend(V[N-k+n:])
        A.sort()
        
        c = sum(A)
        for i in range(min(K-k, k)):
            if A[i] <= 0:
                c -= A[i]
        #print(k, n, c)
        ans = max(ans, c)
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for k in range(K+1):
    for n in range(k+1):
        if n >= N:
            break
        A = V[:n]
        A.extend(V[N-k+n:])
        A.sort()
        c = sum(A)
        for i in range(min(K-k, k)):
            if A[i] <= 0:
                c -= A[i]
        #print(k, n, c)
        ans = max(ans, c)
print(ans)
Problem p03044 (python)

Fixed submission:
N = int(input())
import sys
sys.setrecursionlimit(90000)

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

color = [-1 for _ in range(N)]
def dfs(p, c, color):
    color[p] = c
    cinv = 0 if c == 1 else 1
    for q, d in graph[p]:
        if color[q] != -1:
            continue
        if d % 2 == 1:
            color = dfs(q, cinv, color)
        else:
            color = dfs(q, c, color)
    return color

A = dfs(0, 0, color)
for a in A:
    print(a)

Buggy submission (verdict: Runtime Error):
N = int(input())
import sys
sys.setrecursionlimit(10000)

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

color = [-1 for _ in range(N)]
def dfs(p, c, color):
    color[p] = c
    cinv = 0 if c == 1 else 1
    for q, d in graph[p]:
        if color[q] != -1:
            continue
        if d % 2 == 1:
            color = dfs(q, cinv, color)
        else:
            color = dfs(q, c, color)
    return color

A = dfs(0, 0, color)
for a in A:
    print(a)

Buggy submission (verdict: Runtime Error):
N = int(input())

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


color = [-1 for _ in range(N)]
def dfs(p, c, color):
    color[p] = c
    cinv = 0 if c == 1 else 1
    for q, d in graph[p]:
        if color[q] != -1:
            continue
        if d % 2 == 1:
            color = dfs(q, cinv, color)
        else:
            color = dfs(q, c, color)
    return color
A = dfs(0, 0, color)
for a in A:
    print(a)
Problem p03061 (python)

Fixed submission:
from fractions import gcd

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

GCD1 = []
g = A[0]
for a in A:
    g = gcd(g, a)
    GCD1.append(g)

B = A[::-1]
g = B[0]
GCD2 = []
for b in B:
    g = gcd(g, b)
    GCD2.append(g)

ans = 1
for i in range(N):
    if i == 0:
        a = GCD2[N-2]
    elif i == N-1:
        a = GCD1[N-2]
    else:
        a = gcd(GCD1[i-1], GCD2[N-i-2])
    ans = max(ans, a)
print(ans)

Buggy submission (verdict: Runtime Error):
import math

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

def gcd_list(num_list):
    for i, num in enumerate(num_list):
        if i == 0:
            g = num
        else:
            g = math.gcd(num, g)
    return g

GCD = 0
for i in range(N):
    others = A[:]
    others.pop(i)
    gcd = gcd_list(others)
    if gcd > GCD:
        GCD = gcd
print(GCD)

Buggy submission (verdict: Runtime Error):
import math

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

def gcd_list(num_list):
    for i, num in enumerate(num_list):
        if i == 0:
            g = num
        else:
            g = math.gcd(num, g)
    return g

GCD = 0
for i in range(N):
    others = A[:i] + A[i+1:]
    gcd = gcd_list(others)
    if gcd > GCD:
        GCD = gcd
print(GCD)

Buggy submission (verdict: Runtime Error):
import math
from functools import reduce

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

def gcd_list(num_list):
    return reduce(math.gcd, num_list)

GCD = 0
for i in range(N):
    others = A[:i] + A[i+1:]
    gcd = gcd_list(others)
    if gcd > GCD:
        GCD = gcd
print(GCD)
Problem p03074 (python)

Fixed submission:
N, K = map(int, input().split())
S = list(input())

l = 0
r = 0
change = 0 if S[0] == '1' else 1
ans = 0
while l < N and r < N:
    #print(l, r, change)
    ans = max(ans, r-l+1)
    if r == N-1:
        break
    if S[r] == '0':
        r += 1
    else:
        if S[r+1] == '0':
            if change < K:
                change += 1
                r += 1
            else:
                if S[l] == '0' and S[l+1] == '1':
                    r += 1
                l += 1
        else:
            r += 1
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split()) # 横に2個
S = [int(i) for i in list(input())]

N0 = []
N1 = []
n0 = 0
n1 = 0
for s in S:
    if s == 0:
        if n1 > 0:
            N1.append(n1)
            n1 = 0
        n0 += 1
    if s == 1:
        if n0 > 0:
            N0.append(n0)
            n0 = 0
        n1 += 1
if n0 > 0:
    N0.append(n0)
if n1 > 0:
    N1.append(n1)

M0 = [0]
m0 = 0
for n0 in N0:
    m0 += n0
    M0.append(m0)

M1 = [0]
m1 = 0
for n1 in N1:
    m1 += n1
    M1.append(m1)
#print(M0)
#print(M1)

c = 0 if S[0] == 0 else 1

if len(N1) == 1 and len(N0) == 0:
    ans = N1[0]
elif len(N1) == 0 and len(N0) == 1:
    ans = N0[0]
else:
    ans = 0
    for i in range(N):
        if i + K >= len(M0):
            break
        if c == 0:
            if i == 0:
                l = M0[K] + M1[i+K]
            elif i == len(M1)-1:
                l = M0[i+K]-M0[i] + M1[i+K-1]-M1[i-1]
            else:
                l = M0[i+K]-M0[i] + M1[i+K]-M1[i-1]
        else:
            if i == len(M1)-2:
                l = M0[i+K]-M0[i] + M1[i+K]-M1[i]
            else:
                l = M0[i+K]-M0[i] + M1[i+K+1]-M1[i]
        #print(i, l)
        ans = max(ans, l)
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split()) # 横に2個
S = [int(i) for i in list(input())]

N0 = []
N1 = []
n0 = 0
n1 = 0
for s in S:
    if s == 0:
        if n1 > 0:
            N1.append(n1)
            n1 = 0
        n0 += 1
    if s == 1:
        if n0 > 0:
            N0.append(n0)
            n0 = 0
        n1 += 1
if n0 > 0:
    N0.append(n0)
if n1 > 0:
    N1.append(n1)

M0 = [0]
m0 = 0
for n0 in N0:
    m0 += n0
    M0.append(m0)

M1 = [0]
m1 = 0
for n1 in N1:
    m1 += n1
    M1.append(m1)
#print(M0)
#print(M1)

#d = 0 if len(M0)==len(M1) and c == 0


if len(N1) == 1 and len(N0) == 0:
    ans = N1[0]
elif len(N1) == 0 and len(N0) == 1:
    ans = N0[0]
else:
    ans = 0
    for i in range(N):
        if i+K+1 >= len(M1):
            a = M1[-1]-M1[-1-K]
            if i == 0:
                ans = a
        else:
            a = M1[i+K+1]-M1[i]
        if i + K >= len(M0):
            break
        l = M0[i+K]-M0[i] + a
        #print(l)
        ans = max(ans, l)
print(ans)
Problem p03081 (python)

Fixed submission:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().rstrip()
TD = [list(map(str, input().split())) for _ in range(Q)]

l = 0
r = N
while r - l > 1:
    m = (l+r)//2
    right_over = False
    pl = m
    for t, d in TD:
        if S[pl] == t:
            if d == 'L':
                pl -= 1
                if pl == -1:
                    break
            else:
                pl += 1
                if pl == N:
                    right_over = True
                    break
    if right_over:
        r = m
    else:
        l = m

right = l

l = 0
r = N
while r - l > 1:
    m = (l+r)//2
    left_over = False
    pl = m
    for t, d in TD:
        if S[pl] == t:
            if d == 'L':
                pl -= 1
                if pl == -1:
                    left_over = True
                    break
            else:
                pl += 1
                if pl == N:
                    break
    if left_over:
        l = m
    else:
        r = m

left = l

print(right-left)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().rstrip()
Query = []
for _ in range(Q):
    Alp, LR = map(str, input().rstrip().split())
    Query.append((Alp, LR))

left = 0
for Alp, LR in reversed(Query):
    if S[left] == Alp and LR == "L":
        left += 1
right = 0
for Alp, LR in reversed(Query):
    if S[N-1-right] == Alp and LR == "R":
        right += 1
print(max(0, N-left-right))