Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid - 1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += min(max(A[mid]+M-v,0),M)

        if voted <=M*V:
            right = mid-1
        else:
            left= mid+1

print(low)


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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid -1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += A[mid]+M-v

        if voted >= M*V:
            left= mid+1
        else:
            right = mid-1

print(left)

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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid - 1
    else:
        voted = P * M
        voted += (N-mid-1)*M

        for v in A[P-1:mid]:
            voted += min(max(A[mid]+M-v,0),M)

        if voted <=M*V:
            right = mid-1
        else:
            left= mid+1

print(left)


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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid -1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += A[mid]+M-v

        if voted >= M*V:
            left= mid+1
        else:
            right = mid-1

print(left)
Buggy python submission (verdict: Runtime Error):
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
assert len(ans)==1
print(int(ans[0]))


Fixed submission:
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(ans.pop())

Buggy python submission (verdict: Runtime Error):
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(int(ans))


Fixed submission:
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(ans.pop())
Buggy python submission (verdict: Runtime Error):
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if dist_v_dst % 2 == 0:
    ans = dist_u_dst+(dist_v_dst-dist_u_dst)//2
else:
    ans = dist_u_dst+dist_v_dst-dist_u_dst
print(ans)


Fixed submission:
def solve():
    _N = int(input())
    N = _N
    ans = 0
    if N % 2 == 0:
        div = 10
        while N // div > 0:
            ans += N//div
            div *= 5
    print(ans)


solve()
Buggy python submission (verdict: Runtime Error):
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)


Fixed submission:
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next] or True:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp

ans = 0
for i in range(N):
    if dist_from_u[i] < dist_from_v[i]:
        ans = max(ans, dist_from_v[i]-1)
print(ans)
exit()

dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
N = int(input())
L = list(map(lambda x: bin(int(x))[2:], input().split()))
max_len = max([len(v) for v in L])
padL = ["0"*(max_len-len(v))+v for v in L]
cnt = [0]*max_len
for i in range(max_len):
    for l in padL:
        cnt[i] += 1 if l[i] == "1" else 0

ans = 0
v = 1
for i in range(max_len):
    ans += v*cnt[max_len-1-i]*(N-cnt[max_len-i-1])
    ans %= MOD
    v *= 2

print(ans)


Fixed submission:
MOD = 10**9+7
N = int(input())
L = list(map(lambda x: bin(int(x))[2:], input().split()))
max_len = max([len(v) for v in L])
padL = ["0"*(max_len-len(v))+v for v in L]
cnt = [0]*max_len
for i in range(max_len):
    for l in padL:
        cnt[i] += 1 if l[i] == "1" else 0

ans = 0
v = 1
for i in range(max_len):
    ans += v*cnt[max_len-1-i]*(N-cnt[max_len-i-1])
    ans %= MOD
    v *= 2

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

ans = 1
dp = [0]*3
for a in A:
    ans = ans*dp.count(a) % MOD
    dp[dp.index(a)] += 1
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

ans = 1
dp = [0]*3
for a in A:
    cnt = 0
    for i in range(3):
        if a == dp[i]:
            cnt += 1
    for i in range(3):
        if a == dp[i]:
            dp[i] += 1
            break
    ans = ans*cnt % MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())


#A1>=B1にする
if A1>=B1:
    pass
else:
    A1,B1=B1,A1
    A2,B2=B2,A2

D1=(A1-B1)*T1#>=0
D2=(A2-B2)*T2#?

if D1==-D2:
    print("infinity")
elif D1+D2>=0:
    print("0")
else:
    diff = abs(D1+D2)#マイからこれだけ差が開く
    if D1%diff==0:
        print(D1//diff*2)
    else:
        assert 1==2


Fixed submission:
from math import ceil
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())


#A1>=B1にする
if A1>=B1:
    pass
else:
    A1,B1=B1,A1
    A2,B2=B2,A2

D1=(A1-B1)*T1#>=0
D2=(A2-B2)*T2#?

if D1==-D2:
    print("infinity")
elif D1+D2>=0:
    print("0")
else:
    diff = abs(D1+D2)#マイからこれだけ差が開く
    if D1%diff==0:
        print(D1//diff*2)
    else:
        print(ceil(D1/diff)*2-1)

Buggy python submission (verdict: Runtime Error):
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())


#A1>=B1にする
if A1>=B1:
    pass
else:
    A1,B1=B1,A1
    A2,B2=B2,A2

D1=(A1-B1)*T1#>=0
D2=(A2-B2)*T2#?

if D1==-D2:
    print("infinity")
elif D2>=0:
    print("0")
else:
    diff = abs(D1+D2)#マイからこれだけ差が開く
    if D1%diff==0:
        print(D1//diff*2)
    else:
        assert 1==2


Fixed submission:
from math import ceil
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())


#A1>=B1にする
if A1>=B1:
    pass
else:
    A1,B1=B1,A1
    A2,B2=B2,A2

D1=(A1-B1)*T1#>=0
D2=(A2-B2)*T2#?

if D1==-D2:
    print("infinity")
elif D1+D2>=0:
    print("0")
else:
    diff = abs(D1+D2)#マイからこれだけ差が開く
    if D1%diff==0:
        print(D1//diff*2)
    else:
        print(ceil(D1/diff)*2-1)

Buggy python submission (verdict: Runtime Error):
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())


if A1>=B1:
    pass
else:
    A1,B1=B1,A1
    A2,B2=B2,A2
D1=(A1-B1)*T1
D2=(A2-B2)*T2

if D1==-D2:
    print("infinity")
elif D1*D2>0:
    print("0")
else:
    assert D1>=0 and D2<=0
    diff = abs(D1+D2)
    D1=abs(D1)
    if D1%diff==0:
        print(D1//diff*2+1)
    else:
        assert 1==2


Fixed submission:
from math import ceil
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())


#A1>=B1にする
if A1>=B1:
    pass
else:
    A1,B1=B1,A1
    A2,B2=B2,A2

D1=(A1-B1)*T1#>=0
D2=(A2-B2)*T2#?

if D1==-D2:
    print("infinity")
elif D1+D2>=0:
    print("0")
else:
    diff = abs(D1+D2)#マイからこれだけ差が開く
    if D1%diff==0:
        print(D1//diff*2)
    else:
        print(ceil(D1/diff)*2-1)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))

ans = 0
for l in range(N):
    for r in range(l+1, min(l+K, N+1)):
        if r % K == (A_acc[r]-A_acc[l]+l) % K:
            ans += 1
print(ans)


Fixed submission:
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))


ans = 0
D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    if l>=K:
      r = (A_acc[l-K]-(l-K))
      D[r%K]-=1
    ans += D[t]
    D[t] += 1


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N, K = map(int, input().split())
A = list(map(int, input().split()))
Seg = SegmentTree(N, lambda a, b: (a+b) % K, 0)
for i, a in enumerate(A):
    Seg.set(i, a)
Seg.build()

ans = 0
for l in range(N):
    for r in range(l+1, N+1):
        if Seg.query(l, r) == r-l:
            ans += 1
print(ans)


Fixed submission:
from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))


ans = 0
D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    if l>=K:
      r = (A_acc[l-K]-(l-K))
      D[r%K]-=1
    ans += D[t]
    D[t] += 1


print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
if all(a==b for a,v in zip(S,S[N:]):
       print("Yes")
else:
       print("No")

Fixed submission:
N = int(input())
S=input()

if N%2==0 and all(a==b for a,b in zip(S,S[N//2:])):
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N,T = map(int,input().split())
item=sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])

dp=[0]*(T+1)

for a,b in item:
    for t in reversed(range(T)):
        dist=min(T,t+a)
        dp[dist] = max(dp[t]+b,dp[dist])
print(max(dp))


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

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

dp=[[0]*(T+3000) for _ in range(N+1)]

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,T = map(int,input().split())

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

dp=[[0]*(T+3000) for _ in range(N+1)]

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)


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

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

dp=[[0]*(T+3000) for _ in range(N+1)]

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
for i in range(1,10):
  for j in range(i,10):
    if i*j==N:
      print("Yes")
   	  exit()
print("No")

Fixed submission:
N=int(input())
for i in range(1,10):
  for j in range(i,10):
    if i*j==N:
      print("Yes")
      exit()
print("No")
Buggy python submission (verdict: Runtime Error):
import numpy as np
A,B,X=map(int,input().split())
rad = np.arctan((A*B-X)/(A*A)*2)
print(np.rad2deg(rad))

Fixed submission:
import numpy as np
A,B,X=map(int,input().split())
X/=A
if A*B/2<=X:
	print(np.rad2deg(np.arctan(2*(A*B-X)/(A*A))))
else:
    print(np.rad2deg(np.arctan(B*B/(2*X))))
Buggy python submission (verdict: Time Limit Exceeded):
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    c = set(map(int, input().split()))
    keys.append([a, c])

ans = float('inf')
for b in range(2**(M)):
    opened = set()
    money = 0
    for key in range(M):
        if (b >> key) & 1:  # key番目の鍵を買う
            money += keys[key][0]
            opened |= keys[key][1]
        if len(opened) == N:
            break
    if len(opened) == N:
        ans = min(ans, money)
if ans == float('inf'):
    ans = -1
print(ans)


Fixed submission:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    key_set = set(map(int, input().split()))
    key_bin = 0
    for c in key_set:
        key_bin += (2**(c-1))
    keys.append([a, key_bin])


N_bin = 2**N
# i番目までのkeyで
dp = [[float('inf')]*N_bin for _ in range(2)]
dp[0][0] = 0
for key in range(M):  # 新加えるkey
    key_val, key_set = keys[key]
    for bit in range(N_bin):  # 加える前の状態
        dp[(key+1) % 2][bit] = min(dp[(key+1) %
                                      2][bit], dp[key % 2][bit])  # くわえない
        dp[(key+1) % 2][bit | key_set] = min(dp[(key+1) % 2][bit | key_set],
                                             dp[key % 2][bit]+key_val)  # 加える
ans = float('inf')
for c in range(2):
    ans = min(ans, dp[c][-1])
if ans == float("inf"):
    ans = -1
print(ans)
Buggy python submission (verdict: Runtime Error):
Wethers={"Sunny":0,"Cloudy":1,"Rainy":2}
Wether=["Sunny","Cloudy","Rainy"]
S=input()
S_id = Wethers[S]
print(Wether(S_id+1)%3)



Fixed submission:
Wethers={"Sunny":0,"Cloudy":1,"Rainy":2}
Wether=["Sunny","Cloudy","Rainy"]
S=input()
S_id = Wethers[S]
print(Wether[(S_id+1)%3])

Buggy python submission (verdict: Runtime Error):
Wethers={"Sunny":0,"Cloudy":1,"Rainy":2}
Wether=["Sunny","Cloudy","Rainy"]
S=input()[:-1]
S_id = Wethers[S]
print(Wether(S_id+1)%3)



Fixed submission:
Wethers={"Sunny":0,"Cloudy":1,"Rainy":2}
Wether=["Sunny","Cloudy","Rainy"]
S=input()
S_id = Wethers[S]
print(Wether[(S_id+1)%3])

Buggy python submission (verdict: Runtime Error):
Wethers={"Sunny":0,"Cloudy":1,"Rainy":2}
Wether=["Sunny","Cloudy","Rainy"]
S=input()[:-1]
S_id = Wethers[S]
print((S_id+1)%3)



Fixed submission:
Wethers={"Sunny":0,"Cloudy":1,"Rainy":2}
Wether=["Sunny","Cloudy","Rainy"]
S=input()
S_id = Wethers[S]
print(Wether[(S_id+1)%3])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
S = input()[:-1]


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i, c in enumerate(S, 1):
        for j, k in enumerate(S, 1):
            if c == k:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1 if i +
                               dp[i-1][j-1] < j else 0)
    print(max([max(v) for v in dp]))


solve()


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
S = input()[:-1]


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i, c in enumerate(S, 1):
        for j, k in enumerate(S, 1):
            if c == k:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1 if i +
                               dp[i-1][j-1] < j else 0)
    print(max([max(v) for v in dp]))


solve()
Buggy python submission (verdict: Runtime Error):
S=input
print(sum(u==v for u,v in zip(S(),T())))

Fixed submission:
S=input()
T=input()
print(sum([1 for u,v in zip(S,T) if u==v]))

Buggy python submission (verdict: Runtime Error):
S=input
print(sum([u==v for u,v in zip(S(),T())]))

Fixed submission:
S=input()
T=input()
print(sum([1 for u,v in zip(S,T) if u==v]))
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
if B<3200:
  print(S)
else:
  print("red")

Fixed submission:
B=int(input())
S=input()
if B>=3200:
  print(S)
else:
  print("red")
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: set())
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i)
    min_D[s] = min(i, min_D[s])

for s in D.keys():
  D[s]=sorted(D[s])
cur_pos = 0
repeat = 0
for t in T:
    for next_cand in D[t]:
        if next_cand >= cur_pos:
            cur_pos = next_cand+1
            break
    else:
        repeat += 1
        cur_pos = min_D[t]
print(len(S)*repeat+cur_pos)


Fixed submission:
import bisect
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: [])
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i)
    min_D[s] = min(i, min_D[s])

for s in D.keys():
    D[s] = sorted(D[s])

cur_pos = 0
repeat = 0
for t in T:
    #print("cur->", cur_pos)
    ind = bisect.bisect_left(D[t], cur_pos)
    if ind >= len(D[t]):
        repeat += 1
        cur_pos = min_D[t]+1
    else:
        cur_pos = D[t][ind]+1

print(len(S)*repeat+cur_pos)
Buggy python submission (verdict: Time Limit Exceeded):
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


def solve():
    S = input()[:-1]
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            #dig = 10**i
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   # dp[i+1][j] += dp[i][(k*dig+j) % 13]
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            #dig = 10**i
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                #dp[i+1][j] = dp[i][(int(S[i])*dig+j) % 13]
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()


Fixed submission:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


def brute():
    S = input()[:-1]
    print(S)

    Q = [""]
    for c in reversed(S):
        tmp = []
        if c == "?":
            print("?")
            for q in Q:
                for i in range(0, 10):
                    tmp.append(str(i)+q)
        else:
            for q in Q:
                tmp.append(c+q)
        Q = tmp

    Q = sorted(Q)
    cnt = 0
    for q in Q:
        if int(q) % 13 == 5:
            cnt += 1
            print(int(q))
    print(cnt)
    print(cnt % MOD)


def solve():
    S = input()[:-1]
    # dp[i+1][j]イバン目まで見て、あまりがjのこすう
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            #dig = 10**i
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   # dp[i+1][j] += dp[i][(k*dig+j) % 13]
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            #dig = 10**i
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                #dp[i+1][j] = dp[i][(int(S[i])*dig+j) % 13]
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()