Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_left, bisect_right
n = int(input()) # 入力が1つ
s = input()
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
# n = 4
# s = 'RRGB'
r = []
g = []
b = []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)
ans = 0
for i in range(len(r)):
    j = bisect_left(g, r[i])
    k = bisect_left(b, g[j])
    ans += (len(g) - j) * (len(b) - k)

def bs(nums, target):
    l = 0
    r = len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return True
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return False

def solution(t1, t2, t3):
    ans = 0
    if len(t1) < 1 or len(t2) < 1 or len(t3) < 1:
        return ans
    for i in range(len(t2)):
        num = t2[i]
        left = bisect_left(t1, num)
        right = bisect_right(t3, num)
        ans += left * (len(t3) - right)

    for i in t1:
        for j in t3:
            if i < j:
                if (i + j) % 2 == 0 and bs(t2, (i + j) // 2):
                    ans -= 1
    return ans

ans = 0
ans += solution(r, g, b)
ans += solution(r, b, g)
ans += solution(g, r, b)
ans += solution(g, b, r)
ans += solution(b, r, g)
ans += solution(b, g, r)
print(ans)

Fixed submission:
from bisect import bisect_left, bisect_right
n = int(input()) # 入力が1つ
s = input()
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
r = []
g = []
b = []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)
ans = 0

def bs(nums, target):
    l = 0
    r = len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return True
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return False

def solution(t1, t2, t3):
    ans = 0
    if len(t1) < 1 or len(t2) < 1 or len(t3) < 1:
        return ans
    for i in range(len(t2)):
        num = t2[i]
        left = bisect_left(t1, num)
        right = bisect_right(t3, num)
        ans += left * (len(t3) - right)

    for i in t1:
        for j in t3:
            if i < j:
                if (i + j) % 2 == 0 and bs(t2, (i + j) // 2):
                    ans -= 1
    return ans

ans = 0
ans += solution(r, g, b)
ans += solution(r, b, g)
ans += solution(g, r, b)
ans += solution(g, b, r)
ans += solution(b, r, g)
ans += solution(b, g, r)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
# int(input()) # 入力が1つ
n, x, y = map(int, input().split()) # 入力が複数
graph = [[] for _ in range(n)]

for i in range(n - 1):
    graph[i].append((1, i + 1))
    graph[i + 1].append((1, i))
graph[x - 1].append((1, y - 1))
graph[y - 1].append((1, x - 1))

def dijkstra(graph, n, start):
    inf = float('inf')
    visited = [inf] * n
    visited[start] = 0
    heap = [(0, start)] #(cost, vertex)
    while heap:
        _, vertex = heappop(heap)
        for c, v in graph[vertex]:
            cost = visited[vertex] + c
            if visited[v] > cost:
                visited[v] = cost
                heappush(heap, (cost, v))
    return visited

path = []
for i in range(n):
    visited = dijkstra(graph, n, i)
    path.append(visited)
    
for k in range(1, n):
    ans = 0
    for i in range(len(path)):
        visited = path[i]
        for j in range(i, len(visited)):
            if visited[j] - visited[i] == k:
                ans += 1
    print(ans)


Fixed submission:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
# int(input()) # 入力が1つ
n, x, y = map(int, input().split()) # 入力が複数
graph = [[] for _ in range(n)]

for i in range(n - 1):
    graph[i].append((1, i + 1))
    graph[i + 1].append((1, i))
graph[x - 1].append((1, y - 1))
graph[y - 1].append((1, x - 1))

def dijkstra(graph, n, start):
    inf = float('inf')
    visited = [inf] * n
    visited[start] = 0
    heap = [(0, start)] #(cost, vertex)
    while heap:
        _, vertex = heappop(heap)
        for c, v in graph[vertex]:
            cost = visited[vertex] + c
            if visited[v] > cost:
                visited[v] = cost
                heappush(heap, (cost, v))
    return visited

path = []
for i in range(n):
    visited = dijkstra(graph, n, i)
    path.append(visited)

# for k in range(1, n):
#     ans = 0
#     for i in range(len(path)):
#         visited = path[i]
#         for j in range(i, len(visited)):
#             if visited[j] - visited[i] == k:
#                 ans += 1
#     print(ans)

t = [0] * n
for i in range(len(path)):
    visited = path[i]
    for j in range(i, len(visited)):
        diff = visited[j] - visited[i]
        t[diff] += 1
for k in range(1, n):
    ans = t[k]
    print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
x, y, a, b, c = map(int, input().split()) # 入力が複数

reds = sorted([int(i) for i in input().split()], reverse=True)
greens = sorted([int(i) for i in input().split()], reverse=True)
whites = sorted([int(i) for i in input().split()], reverse=True)

reds = reds[:x] + [-float('inf')]
greens = greens[:y] + [-float('inf')]
whites.append(-float('inf'))

ans = 0
num = 0
r = g = w = 0
while num != x + y:
    red = reds[r]
    green = greens[g]
    white = whites[w]
    if red > green and red > white:
        r += 1
        ans += red
    elif green > red and green > white:
        g += 1
        ans += green
    else:
        w += 1
        ans += white
    num += 1
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
x, y, a, b, c = map(int, input().split()) # 入力が複数

reds = sorted([int(i) for i in input().split()], reverse=True)
greens = sorted([int(i) for i in input().split()], reverse=True)
whites = sorted([int(i) for i in input().split()], reverse=True)

reds = reds[:x]
greens = greens[:y]

apples = sorted(reds + greens + whites, reverse=True)
ans = sum(apples[:x + y])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
pre = 0
reverse = 0
for _ in range(q):
    query = input()
    if query == '1':
        if pre:
            pre = 0
        else:
            pre = 1
        reverse += 1
    else:
        _, f, c = query.split()
        if f == '1':
            if pre == 0:
                s = c + s
            else:
                s = s + c
        else:
            if pre == 1:
                s = c + s
            else:
                s = s + c
if reverse % 2 == 1:
    s = s[::-1]
print(s)

Fixed submission:
from collections import deque
s = input()
queue = deque(list(s))
q = int(input())
pre = 0
reverse = 0
for _ in range(q):
    query = input()
    if query == '1':
        if pre:
            pre = 0
        else:
            pre = 1
        reverse += 1
    else:
        _, f, c = query.split()
        if f == '1':
            if pre == 0:
                # s = c + s
                queue.appendleft(c)
            else:
                # s = s + c
                queue.append(c)
        else:
            if pre == 1:
                # s = c + s
                queue.appendleft(c)
            else:
                # s = s + c
                queue.append(c)
if reverse % 2 == 1:
    queue = reversed(queue)
print(''.join(queue))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
for _ in range(q):
    query = input()
    if query == '1':
        s = s[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            s = c + s
        else:
            s = s + c
print(s)

Fixed submission:
from collections import deque
s = input()
queue = deque(list(s))
q = int(input())
pre = 0
reverse = 0
for _ in range(q):
    query = input()
    if query == '1':
        if pre:
            pre = 0
        else:
            pre = 1
        reverse += 1
    else:
        _, f, c = query.split()
        if f == '1':
            if pre == 0:
                # s = c + s
                queue.appendleft(c)
            else:
                # s = s + c
                queue.append(c)
        else:
            if pre == 1:
                # s = c + s
                queue.appendleft(c)
            else:
                # s = s + c
                queue.append(c)
if reverse % 2 == 1:
    queue = reversed(queue)
print(''.join(queue))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))

start = end = 0
MAX = 0
for i in range(n):
    dices = p[i:i+k]
    expec = 0
    for d in dices:
        expec += (((1 + d) * d) / 2) / d
    MAX = max(MAX, expec)

print(MAX)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

expectations = [(((1 + i) * i) / 2) / i for i in p] # O(n)
i = 0
MAX = e = sum(expectations[i:i + k])
while i + k < n: # O(n)
    i += 1
    t = e - expectations[i - 1] + expectations[i + k - 1]
    MAX = max(MAX, t)
    e = t

print(MAX)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))

start = end = 0
MAX = 0
for i in range(n):
    dices = p[i:i+k]
    expec = 0
    for d in dices:
        expec += sum([i for i in range(1, d + 1)]) / d
    MAX = max(MAX, expec)

print(MAX)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

expectations = [(((1 + i) * i) / 2) / i for i in p] # O(n)
i = 0
MAX = e = sum(expectations[i:i + k])
while i + k < n: # O(n)
    i += 1
    t = e - expectations[i - 1] + expectations[i + k - 1]
    MAX = max(MAX, t)
    e = t

print(MAX)
Buggy python submission (verdict: Runtime Error):
n, d, a = map(int, input().split())

monsters = []
for _ in range(n):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort(key=lambda x: x[0])
attack = 0

left_m, left_hp = monsters[0]
MAX_HP = left_hp
attacked = [False] * len(monsters)
for i in range(len(monsters)):
    cur_m, cur_hp = monsters[i]
    if cur_m - left_m <= d:
        MAX_HP = max(MAX_HP, cur_hp)
    else:
        attacked[:i + d] = [True] * (i + d)
        if MAX_HP % a == 0:
            attack += MAX_HP // a
        else:
            attack += MAX_HP // a + 1
        left_m, left_hp = monsters[i]

if not attacked[-1]:
    hp = monsters[-1][1]
    if hp % a == 0:
        attack += hp // a
    else:
        attack += hp // a + 1
print(attack)

Fixed submission:
from collections import deque

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

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

XH = []

for i in range(N):

    x,h = map(int,input().split())
    XH.append([x,h])

XH.sort()

q = deque([])
qs = 0
ans = 0

for i in range(N):

    X = XH[i][0]
    H = XH[i][1]

 
    while len(q) > 0 and q[0][0] < X-D:
        po = q.popleft()
        qs -= po[1] * A

    if H - qs <= 0:
        continue
        
    else:
        pl = updiv(H-qs,A)
        qs += pl * A
        ans += pl
        q.append([X+D,pl])

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = input().split()
p = [int(i) for i in p]

c = 0
for i in range(n):
    for j in range(i):
        if p[i] <= p[j]:
            continue
        else:
            break
    else:
        c += 1

print(c)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

'''
選んだ数字(iで場所指定)より、左の数字が全て大きい。
'''
c = 0
MIN = p[0]
for i in range(n):
    if p[i] <= MIN:
        c += 1
        MIN = p[i]

print(c)
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())

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

ans = lcm(A, B)
print(ans)

Fixed submission:
from fractions import gcd
A, B = map(int, input().split())

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

ans = lcm(A, B)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc147/tasks/abc147_d
n = int(input())
nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += (nums[i] ^ nums[j]) % mod

print(ans % mod)

Fixed submission:
# https://atcoder.jp/contests/abc147/tasks/abc147_d
n = int(input())
nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
one = [0] * 61
zero = [0] * 61

for i in range(61):
    for num in nums:
        if (num >> i) & 1:
            one[i] += 1
        else:
            zero[i] += 1
ans = 0
for k in range(61):
    ans = (ans + (one[k] * zero[k] * (1 << k))) % mod
print(ans % mod)
Buggy python submission (verdict: Time Limit Exceeded):
# int(input()) # 入力が1つ
n, k = map(int, input().split()) # 入力が複数
nums = [int(i) for i in input().split()] # 配列で数字

nums = [0] + nums
for i in range(n):
    nums[i + 1] += nums[i]
ans = 0
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        left = nums[i]
        right = nums[j]
        if (left - i) % k == (right - j) % k and j - i < k:
            ans += 1
print(ans)


Fixed submission:
# int(input()) # 入力が1つ
from collections import defaultdict
n, k = map(int, input().split()) # 入力が複数
nums = [int(i) for i in input().split()] # 配列で数字

nums = [0] + nums
for i in range(n):
    nums[i + 1] = (nums[i] + nums[i + 1] + k - 1) % k
ans = 0
d = defaultdict(int)
for i in range(n + 1):
    ans += d[nums[i]]
    d[nums[i]] += 1
    if i - (k - 1) >= 0:
        d[nums[i - (k - 1)]] -= 1
print(ans)
Buggy python submission (verdict: Runtime Error):
h, w, k=map(int,input().split())
s = [list(input()) for _ in range(h)]
g = 1
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            continue
        s[i][j] = g
        k = j-1
        while k >= 0 and s[i][k]=='.':
            s[i][k] = g
            k -= 1
        k = j + 1
        while k < w and s[i][k] == '.':
            s[i][k] = g
            k += 1
        g += 1
for i in range(h)[::-1]:
    if s[i][0]=='.':
        for j in range(w):
            s[i][j] = s[i+1][j]
for i in range(h):
    if s[i][0] == '.':
        for j in range(w):
            s[i][j] = s[i-1][j]
for t in s:
    print(*t)


Fixed submission:
h,w,k=map(int,input().split())
s=[list(input())for _ in range(h)]
g=1
for i in range(h):
    for j in range(w):
        if s[i][j]!='#':continue
        s[i][j]=g
        k=j-1
        while k>=0 and s[i][k]=='.':
            s[i][k]=g
            k-=1
        k=j+1
        while k<w and s[i][k]=='.':
            s[i][k]=g
            k+=1
        g+=1
for i in range(h-2,-1,-1):
    if s[i][0]=='.':
        for j in range(w):
            s[i][j]=s[i+1][j]
for i in range(h):
    if s[i][0]=='.':
        for j in range(w):
            s[i][j]=s[i-1][j]
for t in s:
    print(*t)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b
# まず、本当に木を構築するモノではないだろう
from collections import Counter
n = int(input())
nums = [int(i) for i in input().split()]
mod = 998244353
MAX = max(nums)

c = Counter(nums)
if nums[0] != 0 or nums.count(0) != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, MAX + 1):
        ans = ans * pow(c.get(i - 1), c.get(i), mod) % mod
    ans %= mod
print(ans)

Fixed submission:
# https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b
# まず、本当に木を構築するモノではないだろう
from collections import Counter
n = int(input())
nums = [int(i) for i in input().split()]
mod = 998244353
MAX = max(nums)

c = Counter(nums)
if nums[0] != 0 or nums.count(0) != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, MAX + 1):
        ans = ans * pow(c.get(i - 1, 0), c.get(i, 0), mod) % mod
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc143/tasks/abc143_d
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
L = [int(i) for i in input().split()]
L.sort()
pairs = []
for i in range(n):
    for j in range(i + 1, n):
        pairs.append((i, j))

ans = 0
for i, j in pairs:
    p = L[:i] + L[i + 1:j] + L[j + 1:]
    a, b = L[i], L[j]
    l = bisect_left(p, b - a + 1)
    r = bisect_left(p, a)
    if l < r:
        ans += (r - l)
print(ans)

Fixed submission:
# https://atcoder.jp/contests/abc143/tasks/abc143_d
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
L = [int(i) for i in input().split()]
L.sort()
pairs = []
for i in range(n):
    for j in range(i + 1, n):
        pairs.append((i, j))

ans = 0
for i, j in pairs:
    a, b = L[i], L[j]
    ans += bisect_left(L, a + b) - 1 - j
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc141/tasks/abc141_d
from copy import deepcopy
from heapq import heappop, heappush, heapify
n, m = map(int, input().split())

nums = [-int(i) for i in input().split()]
heapify(nums)
def check(nums, money, m):
    while m:
        m -= 1
        item = -1 * heappop(nums)
        item //= 2
        nums.append(-1 * item)
    pay = 0
    for num in nums:
        pay += -1 * num
        if pay > money:
            return False
    return True
l = 0
r = -1 * sum(nums)
ans = r
while l <= r:
    items = deepcopy(nums)
    mid = (l + r) // 2
    if check(items, mid, m):
        ans = min(ans, mid)
        r = mid - 1
    else:
        l = mid + 1
print(ans)

Fixed submission:
# https://atcoder.jp/contests/abc141/tasks/abc141_d
from copy import deepcopy
from heapq import heappop, heappush, heapify
n, m = map(int, input().split())

items = [-int(i) for i in input().split()]
heapify(items)
while m:
    m -= 1
    item = -1 * heappop(items)
    item //= 2
    heappush(items, -1 * item)
pay = 0
for i in items:
    pay += -1 * i
print(pay)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/agc037/tasks/agc037_a

s = input()

ans = 0
pre = s[0]
i = 0
while i < len(s):
    cur = s[i]
    if pre == cur:
        pre = s[i] + s[i + 1]
        i += 2
    else:
        pre = cur
        i += 1
    ans += 1
print(ans)


Fixed submission:
# https://atcoder.jp/contests/agc037/tasks/agc037_a

s = input()

ans = 0
pre = ''
cur = ''
for i in range(len(s)):
    pre += s[i]
    if pre != cur:
        ans += 1
        cur = pre
        pre = ''
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
nums = [int(i) for i in input().split()]

box = [0] * (n + 1)
for i in range(1, n + 1)[::-1]:
    ball = nums[i - 1]
    t = i * 2
    while t <= n:
        ball ^= box[t - 1]
        t += i
    box[t - 1] = ball

ans = box.count(1)
index = []
for i in range(len(box)):
    if box[i]:
        index.append(i)
print(ans)
print(*index)

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

for _ in range(N):
  ans.append(-1)

for i in range(N,0,-1):
  C = i*2
  BALL = A[i-1]
  while C <= N:
    BALL = BALL ^ ans[C-1]
    C += i
  ans[i-1] = BALL 

print(ans.count(1))
ans2 = []
for i in range(N):
  if ans[i] == 1:
    ans2.append(i+1)

L=[str(a) for a in ans2]
L=" ".join(L)
print(L)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_right, bisect_left
n, m = map(int, input().split())
cards = [int(i) for i in input().split()]
cards.sort()
manu = []
for i in range(m):
    b, c = map(int, input().split())
    manu.append((b, c))

manu.sort(reverse=True, key=lambda x: x[1]) # 変更すると大きいモノから行う。
p = 0
for b, c in manu:
    if cards[p] < c and p < n:
        for i in range(b):
            if p + i < n and cards[p + i] < c:
                cards[p + i] = c
        p += b
    else:
        break
ans = sum(cards)
print(ans)

Fixed submission:
from bisect import bisect_right, bisect_left
n, m = map(int, input().split())
cards = [int(i) for i in input().split()]
cards.sort()
manu = []
for i in range(m):
    b, c = map(int, input().split())
    manu.append((b, c))

manu.sort(reverse=True, key=lambda x: x[1]) # 変更すると大きいモノから行う。
p = 0
for b, c in manu:
    if p < n and cards[p] < c:
        for i in range(b):
            if p + i < n and cards[p + i] < c:
                cards[p + i] = c
        p += b
    else:
        break
ans = sum(cards)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_right
n, m = map(int, input().split())
cards = [int(i) for i in input().split()]
cards.sort()
manu = []
for i in range(m):
    b, c = map(int, input().split())
    manu.append((b, c))

manu.sort(reverse=True, key=lambda x: x[1]) # 変更すると大きいモノから行う。
p = 0
for b, c in manu:
    for i in range(b):
        if p + i < n and cards[p + i] < c:
            cards[p + i] = c
    p += b
ans = sum(cards)
print(ans)

Fixed submission:
from bisect import bisect_right, bisect_left
n, m = map(int, input().split())
cards = [int(i) for i in input().split()]
cards.sort()
manu = []
for i in range(m):
    b, c = map(int, input().split())
    manu.append((b, c))

manu.sort(reverse=True, key=lambda x: x[1]) # 変更すると大きいモノから行う。
p = 0
for b, c in manu:
    if p < n and cards[p] < c:
        for i in range(b):
            if p + i < n and cards[p + i] < c:
                cards[p + i] = c
        p += b
    else:
        break
ans = sum(cards)
print(ans)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/agc028/tasks/agc028_a

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

def gcd(x, y):
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

l = n * m // gcd(n, m)
x = [''] * (l)
ans = l
for i in range(n):
    p = i * (l // n)
    x[p] = s[i]
for i in range(m):
    p = i * (l // m)
    if x[p] == '':
        x[p] = t[i]
    else:
        if x[p] == t[i]:
            continue
        else:
            ans = -1
            break
print(ans)

Fixed submission:
# https://atcoder.jp/contests/agc028/tasks/agc028_a

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

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

l = lcm(n, m)
d = gcd(n, m)
n //= d
m //= d

for i in range(d):
    if s[i * n] != t[i * m]:
        print(-1)
        break
else:
    print(l)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
ans = 1
i = 1
limit = (m / n)
while i <= limit:
    if m % i == 0 and m // i >= n:
        ans = max(ans, i)
    i += 1
print(ans)


Fixed submission:
# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
if n == 1:
    ans = m
else:
    ans = 1
    i = 1
    limit = m / n
    while i <= limit:
        if m % i == 0 and m // i >= n:
            ans = max(ans, i)
        i += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
ans = 1
i = 1
while i <= (m / n):
    if m % i == 0 and m // i >= n:
        ans = max(ans, i)
    i += 1
print(ans)


Fixed submission:
# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
if n == 1:
    ans = m
else:
    ans = 1
    i = 1
    limit = m / n
    while i <= limit:
        if m % i == 0 and m // i >= n:
            ans = max(ans, i)
        i += 1
print(ans)