Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

from collections import deque

q = deque()

def calc(d, c):
    if c&1:
        q.append(d)
    if c == 1:
        return 0
    d *= 2
    if d >= 10:
        return c//2 * 2 + calc(1+d%10, c//2)
    return c//2 + calc(d, c//2)
    

def main():
    M = int(input())
    ans = 0
    for i in range(M):
        d, c = map(int, input().split())
        ans += calc(d, c)
    
    num = q.popleft()
    while len(q) > 0:
        t = q.popleft()
        num += t
        if num >= 10:
            num = 1 + num%10
            ans += 1
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

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

from collections import deque

q = deque()

def calc(d, c):
    if c&1:
        q.append(d)
    if c == 1:
        return 0
    d *= 2
    c>>=1
    if d >= 10:
        return c * 2 + calc(1+d%10, c)
    return c + calc(d, c)
    

def main():
    M = int(input())
    ans = 0
    for i in range(M):
        d, c = map(int, input().split())
        ans += calc(d, c)
    
    num = q.popleft()
    while len(q) > 0:
        t = q.popleft()
        num += t
        if num >= 10:
            num = 1 + num%10
            ans += 1
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline

def solve(N, K, a, f, num):
    cost = 0
    for i in range(N):
        cost += max(0, a[i] - (num//f[i]))
        if cost > K:
            return False
    return True


def main():
    N, K = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    f = sorted(list(map(int, input().split())), reverse=True)

    l, r = 0, int(1e12)
    while l != r:
        # print(l, r)
        p = (l + r) // 2
        tmp = solve(N, K, a, f, p)
        # print(l, p, r, tmp)
        if tmp:
            r = p
        else:
            l = p + 1
        # break
    
    print(l)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    a = np.array(sorted(list(map(int, input().split()))))
    f = np.array(sorted(list(map(int, input().split())), reverse=True))

    Asum = a.sum()

    l, r = 0, int(1e13)
    while l != r:
        p = (l + r) // 2
        tmp = Asum - np.minimum(a, p//f).sum() <= K
        # print(p, tmp)
        if tmp:
            r = p
        else:
            l = p + 1
    
    print(l)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input = sys.stdin.readline

def main():
    N = int(input())
    l = sorted(list(map(int, input().split())))

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            a = l[i]
            b = l[j]
            left = bisect.bisect_right(l, b - a)
            right = bisect.bisect_left(l, a + b)
            ans += max(0, right - 1 - max(left-1, j))
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    l = sorted(list(map(int, input().split())))
    memo = [-1] * (l[-2] + l[-1] + 1)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            a = l[i]
            b = l[j]
            if memo[a + b] == -1:
                right = bisect.bisect_left(l, a + b)
                memo[a + b] = right
            else:
                right = memo[a + b]
            ans += max(0, right - j - 1)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = sys.stdin.readline

def main():
    H, W, A, B = map(int, input().split())

    if A * 2 > W or B * 2 > H:
        print("No")
        return
    
    ans = np.zeros((H, W), dtype=int)
    ans[:H-B, W-A:] = 1
    ans[H-B:, :W-A] = 1
    
    for i in range(H):
        for j in range(W):
            print(ans[i][j], end="")
        print()


if __name__ == "__main__":
    main()

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

def main():
    H, W, A, B = map(int, input().split())

    if A * 2 > W or B * 2 > H:
        print("No")
        return
    
    for i in range(H-B):
        for j in range(W-A):
            print(1, end="")
        for j in range(A):
            print(0, end="")
        print()
    for i in range(B):
        for j in range(W-A):
            print(0, end="")
        for j in range(A):
            print(1, end="")
        print()


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    s = []
    for i in range(N):
        s.append("".join(sorted(list(input().strip()))))
    s = sorted(s)
    
    tmp = []
    check = [False] * N
    ans = 0
    for i in range(N-1):
        count = 1
        for j in range(i+1, N):
            if not check[j]:
                ok = True
                for k in range(10):
                    if s[i][k] != s[j][k]:
                        ok = False
                        break
                if ok:
                    count += 1
                    check[j] = True
        if count > 1:
            tmp.append(count)
    
    ans = 0
    for n in tmp:
        ans += (n * (n-1))//2
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    s = []
    for i in range(N):
        s.append("".join(sorted(list(input().strip()))))
    s = sorted(s)
    # print(s)
    tmp = []
    pre = s[0]
    count = 1
    for i in range(1, N):
        if s[i] == pre:
            count += 1
        else:
            if count > 1:
                tmp.append(count)
            count = 1
        if i == N-1:
            if count > 1:
                tmp.append(count)
        pre = s[i]
    ans = 0
    for n in tmp:
        ans += (n * (n-1))//2
    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    s = []
    for i in range(N):
        s.append("".join(sorted(list(input().strip()))))
    s = sorted(s)

    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ok = True
            for k in range(10):
                if s[i][k] != s[j][k]:
                    ok = False
                    break
            if ok:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    s = []
    for i in range(N):
        s.append("".join(sorted(list(input().strip()))))
    s = sorted(s)
    # print(s)
    tmp = []
    pre = s[0]
    count = 1
    for i in range(1, N):
        if s[i] == pre:
            count += 1
        else:
            if count > 1:
                tmp.append(count)
            count = 1
        if i == N-1:
            if count > 1:
                tmp.append(count)
        pre = s[i]
    ans = 0
    for n in tmp:
        ans += (n * (n-1))//2
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
N = input()

tmp = len(N)

ans = 0
for i in range(tmp):
    if i&1 == 1:
        ans += 10**(i) - 10**(i-1)
    elif i == tmp-1:
        ans += int(N[1:]) + 1

# if N[0] == "1" and N[1:]
print(ans)


Fixed submission:
N = input()

tmp = len(N)

if tmp == 1:
    print(int(N))
else:
    ans = 0
    for i in range(tmp):
        if i&1 == 1:
            ans += 10**(i) - 10**(i-1)
        elif i == tmp-1:
            ans += int(N) - int("9"*i)

    # if N[0] == "1" and N[1:]
    print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    zero_count = 0
    ok = False
    dic = {}
    for a in A:
        if a == 0:
            zero_count += 1
        else:
            if a in dic:
                dic[a] += 1
            else:
                dic[a] = 1
    # print(dic, zero_count)
    if len(dic) == 3:
        if zero_count == 0:
            tmp = list(dic.values())
            # print(tmp)
            if tmp[0] == tmp[1] and tmp[1] == tmp[2]:
                key = list(dic.keys())
                tmp = key[0]
                tmp ^= key[1]
                tmp ^= key[2]
                if tmp == 0:
                    print("Yes")
                    return
    if len(dic) == 1:
        if n%3 == 0:
            if zero_count == N/3:
                print("Yes")
                return
    if zero_count == N:
        print("Yes")
        return
    print("No")




if __name__ == "__main__":
    main()


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

def main():
    N = int(input())
    a = list(map(int, input().split()))
    tmp = 0
    for i in range(N):
        tmp ^= a[i]
    if tmp == 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())

    MOD = int(1e9) + 7

    val = N-K+1

    kai = [1] * (val+1)
    for i in range(2, len(kai)):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    for i in range(1, K+1):
        tmp = kai[val] * pow(kai[val-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)
        tmp %= MOD
        tmp *= pow(i, K-i, MOD)
        tmp %= MOD
        print(tmp)

if __name__ == "__main__":
    main()

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

def main():
    N, K = map(int, input().split())

    MOD = int(1e9) + 7

    val = N-K+1

    kai = [1] * (max(val+1, K))
    for i in range(2, len(kai)):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    for i in range(1, K+1):
        if val-i < 0:
            print(0)
            continue
        tmp = kai[val] * pow(kai[val-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)
        tmp %= MOD
        # print(K-1, K-i, i-1)
        tmp *= kai[K-1] * pow(kai[K-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
        tmp %= MOD
        print(tmp)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
s = input()

ans = 0

check = s.count("ABC")

while check > 0:
    ans += check
    s = s.replace("ABC", "BCA")
    check = s.count("ABC")

print(ans)


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

def main():
    s = input().strip()

    ans = 0
    count_a = 0
    if s[0] == "A":
        count_a += 1
    for i in range(len(s)-1):
        tmp = s[i:i+2]
        if tmp == "AA":
            count_a += 1
        elif tmp == "AB":
            pass
        elif tmp == "BC":
            ans += count_a
        elif tmp == "CB":
            pass
        elif tmp == "CA":
            count_a += 1
        elif tmp == "BA":
            count_a = 1
        else:
            count_a = 0
        # print(i, count_a)
    print(ans)
        

        


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import math

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

g_l = [1 for i in range(N)]
g_r = [1 for i in range(N)]

g_l[0] = A[0]
g_r[-1] = A[-1]

for i in range(1, N):
    g_l[i] = math.gcd(A[i], g_l[i-1])
    g_r[-i-1] = math.gcd(A[-i-1], g_r[-i])

ans = max(g_r[1], g_l[-2])
for i in range(1, N-1):
    ans = max(ans, math.gcd(A[i-1], A[i+1]))

print(ans)


Fixed submission:
def gcd(a, b):
    tmp = a%b
    if tmp == 0:
        return b
    return gcd(b, tmp)

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

g_l = [1 for i in range(N)]
g_r = [1 for i in range(N)]

g_l[0] = A[0]
g_r[-1] = A[-1]

for i in range(1, N):
    g_l[i] = gcd(A[i], g_l[i-1])
    g_r[-i-1] = gcd(A[-i-1], g_r[-i])

ans = max(g_r[1], g_l[-2])
for i in range(1, N-1):
    ans = max(ans, gcd(g_l[i-1], g_r[i+1]))

print(ans)

Buggy python submission (verdict: Runtime Error):
import math

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

g_l = [1 for i in range(N)]
g_r = [1 for i in range(N)]

g_l[0] = A[0]
g_r[-1] = A[-1]

for i in range(1, N):
    g_l[i] = math.gcd(A[i], g_l[i-1])
    g_r[-i-1] = math.gcd(A[-i-1], g_r[-i])

ans = max(g_r[1], g_l[-2])
for i in range(1, N-1):
    ans = max(ans, math.gcd(A[i-1], A[i+1]))

print(ans)


Fixed submission:
def gcd(a, b):
    tmp = a%b
    if tmp == 0:
        return b
    return gcd(b, tmp)

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

g_l = [1 for i in range(N)]
g_r = [1 for i in range(N)]

g_l[0] = A[0]
g_r[-1] = A[-1]

for i in range(1, N):
    g_l[i] = gcd(A[i], g_l[i-1])
    g_r[-i-1] = gcd(A[-i-1], g_r[-i])

ans = max(g_r[1], g_l[-2])
for i in range(1, N-1):
    ans = max(ans, gcd(g_l[i-1], g_r[i+1]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, K = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
check = [[[False for i in range(K)] for j in range(K)] for k in range(K)]
q = [[0, 0, 0, 0]]
check[0][0][0] = True
while len(q) > 0:
    i, j, k, step = q.pop(0)
    if step < min(K, 3000):
        ans.append(a[i]+b[j]+c[k])
        if i+1 < x:
            if not check[i+1][j][k]:
                check[i+1][j][k] = True
                q.append([i+1, j, k, step+1])
        if j+1 < y:
            if not check[i][j+1][k]:
                check[i][j+1][k] = True
                q.append([i, j+1, k, step+1])
        if k+1 < z:
            if not check[i][j][k+1]:
                check[i][j][k+1] = True
                q.append([i, j, k+1, step+1])

ans = sorted(ans, reverse=True)
for i in range(K):
    print(ans[i])


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

def main():
    x, y, z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())), reverse=True)

    ind = []
    for i in range(x):
        for j in range(y):
            if (i+1)*(j+1) <= K:
                for k in range(z):
                    if (i+1)*(j+1)*(k+1) <= K:
                        ind.append(A[i]+B[j]+C[k])
                    else:
                        break
            else:
                break
    ind = sorted(ind, reverse=True)
    for i in range(K):
        print(ind[i])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split(" "))
S = input().strip()

check = [0 for i in range(N+2)]

for i in range(N):
    if S[i:i+2] == "AC":
        check[i+1] = 1

ans = [0 for i in range(Q)]

for i in range(Q):
    l, r = map(int, input().split())
    ans[i] = sum(check[l:r])

for i in range(Q):
    print(ans[i])


Fixed submission:
N, Q = map(int, input().split(" "))
S = input().strip()

check = [0 for i in range(N+1)]

tmp = 0
for i in range(N):
    check[i+1] = tmp
    if S[i:i+2] == "AC":
        tmp += 1

ans = [0 for i in range(Q)]

for i in range(Q):
    l, r = map(int, input().split())
    ans[i] = check[r] - check[l]

for i in range(Q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split(" "))
S = input().strip()

check = [False for i in range(len(S))]
for i in range(len(S)-1):
    if S[i:i+2] == "AC":
        check[i] = True

output = []
for i in range(Q):
    start, end = map(int, input().split(" "))
    output.append(check[start-1:end-1].count(True))

for i in output:
    print(i)


Fixed submission:
N, Q = map(int, input().split(" "))
S = input().strip()

check = [0 for i in range(N+1)]

tmp = 0
for i in range(N):
    check[i+1] = tmp
    if S[i:i+2] == "AC":
        tmp += 1

ans = [0 for i in range(Q)]

for i in range(Q):
    l, r = map(int, input().split())
    ans[i] = check[r] - check[l]

for i in range(Q):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.child_num = 0
    
    def root_node(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

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

    nodes = [Node() for i in range(N)]

    ab = [list(map(int, input().split())) for i in range(M)]
    
    inc = (N * (N-1)) // 2
    ans = [inc]
    for i in range(M-1, -1, -1):
        a, b = ab[i]
        a -= 1
        b -= 1
        root_a = nodes[a].root_node()
        root_b = nodes[b].root_node()
        if root_a == root_b:# もともと連結成分だった場合
            ans.append(inc)
        else:# 新たに連結成分になった場合
            # if root_b.child_num > root_a.child_num:
            #     tmp = root_a
            #     root_a = root_b
            #     root_b = tmp
            inc -= (root_a.child_num + 1) * (root_b.child_num + 1)
            ans.append(inc)
            root_b.is_root = False
            root_b.parent = root_a
            root_a.child_num += root_b.child_num + 1

    for i in range(M-1, -1, -1):
        print(ans[i])

if __name__ == "__main__":
    main()



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

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.child_num = 0
    
    def root_node(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

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

    nodes = [Node() for i in range(N)]

    ab = [list(map(int, input().split())) for i in range(M)]
    
    inc = (N * (N-1)) // 2
    ans = [inc]
    for i in range(M-1, -1, -1):
        a, b = ab[i]
        a -= 1
        b -= 1
        root_a = nodes[a].root_node()
        root_b = nodes[b].root_node()
        if root_a == root_b:# もともと連結成分だった場合
            ans.append(inc)
        else:# 新たに連結成分になった場合
            if root_b.child_num > root_a.child_num:
                tmp = root_a
                root_a = root_b
                root_b = tmp
            inc -= (root_a.child_num + 1) * (root_b.child_num + 1)
            ans.append(inc)
            root_b.is_root = False
            root_b.parent = root_a
            root_a.child_num += root_b.child_num + 1

    for i in range(M-1, -1, -1):
        print(ans[i])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = np.full(N, int(1e15))

    dp[0] = 0
    for i in range(N):
        for j in range(i+1, min(N, i+K+1)):
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
    # print(dp)
    print(int(dp[N-1]))

if __name__ == "__main__":
    main()

Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    h = np.array(list(map(int, input().split())))
    dp = np.zeros(N, dtype=int)

    dp[0] = 0
    for i in range(1, N):
        start = max(0, i - K)
        dp[i] = min(dp[start:i] + np.abs(h[start:i] - h[i]))
    # print(dp)
    print(int(dp[N-1]))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    INF = int(1e20)
    dp = np.array([[INF] * (1000 * N + 1) for i in range(N+1)])
    dp[0][0] = 0

    for i in range(N):
        w, v = wv[i]
        dp[i+1] = dp[i]
        dp[i+1, v:] = np.minimum(dp[i+1, v:], dp[i, :-v] + w)
    
    for i in range(1000, -1, -1):
        if dp[N][i] <= W:
            print(i)
            break

if __name__ == "__main__":
    main()

Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]

    INF = int(1e18)
    dp = np.full(1000 * N + 1, INF, dtype=int)
    dp[0] = 0

    max_v = 0
    for i in range(N):
        w, v = wv[i]
        dp[v:max_v + v + 1] = np.minimum(dp[v:max_v + v + 1], dp[:max_v + 1] + w)
        max_v += v
    
    print(np.where(dp <= W)[0].max())

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    st = [""] * len_
    tmp = len_ // N
    for i in range(N):
        st[i*tmp] = s[i]
    ok = True
    tmp = len_ // M
    for i in range(M):
        if st[i*tmp] == "" or st[i*tmp] == t[i]:
            st[i*tmp] = t[i]
        else:
            ok = False
            break
    # print(st)
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Fixed submission:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    tmp1 = len_ // N
    tmp2 = len_ // M
    # print(tmp1, tmp2)
    ok = True
    for i in range(0, len_, tmp1 * (tmp2//gcd(tmp1, tmp2))):
        # print(i, s[i//tmp1], t[i//tmp2])
        if s[i//tmp1] != t[i//tmp2]:
            ok = False
            break
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import math

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = math.gcd(N, M)
    len_ = N * (M//gcd_)
    st = [""] * len_
    tmp = len_ // N
    for i in range(N):
        st[i*tmp] = s[i]
    ok = True
    tmp = len_ // M
    for i in range(M):
        if st[i*tmp] == "" or st[i*tmp] == t[i]:
            st[i*tmp] = t[i]
        else:
            ok = False
            break
    # print(st)
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Fixed submission:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    tmp1 = len_ // N
    tmp2 = len_ // M
    # print(tmp1, tmp2)
    ok = True
    for i in range(0, len_, tmp1 * (tmp2//gcd(tmp1, tmp2))):
        # print(i, s[i//tmp1], t[i//tmp2])
        if s[i//tmp1] != t[i//tmp2]:
            ok = False
            break
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()