Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        return divisors
    n = int(input())
    A = list(map(int, input().split()))
    d = {}
    ans = []
    for i in range(1, n + 1):
        d[i] = 0
    for i, a in enumerate(A[::-1]):
        i = n - i
        if d[i] % 2 != a:
            ans.append(str(i))
            for divisor in make_divisors(i):
                d[divisor] += 1
    print(len(ans))
    print(' '.join(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    ans = []
    for i, a in enumerate(A[::-1]):
        i = n - i
        b = sum(B[i - 1::i])
        if b % 2 != a:
            ans.append(str(i))
            B[i - 1] = 1
    print(len(ans))
    print(' '.join(ans))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
def main():
    N = int(input())
    max_x = 100
    max_y = 100
    ans = [0] * N
    for x in range(1, max_x+1):
        for y in range(1, max_y+1):
            for i in range(N):
                a, b = divmod(x**2 + y**2 + x*y - (i+1), -1 * (x+y))
                a = 1
                b = x + y
                c = x**2 + y**2 + x*y - (i+1)
                d = b**2 - 4 * a * c
                if d < 0:
                    continue
                z1 = -1 * (a+b) + math.sqrt(d)
                z2 = -1 * (a+b) - math.sqrt(d)
                if (z1.is_integer() and z1 > 0) or (z2.is_integer() and z2 > 0):
                    ans[i] += 1
    for ni in ans:
        print(ni)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N = int(input())
    max_x = 100
    max_y = 100
    max_z = 100
    ans = [0] * N
    for x in range(1, max_x+1):
        for y in range(1, max_y+1):
            for z in range(1, max_z+1):
                a = (x+y+z)**2 - x*y - y*z - z*x
                if 1 <= a <= N:
                    ans[a-1] += 1
    for ni in ans:
        print(ni)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
l=[input() for i in range(n)]

ll=[]
for i in range(n):
    ll.append(l.count(l[i]))

lll=[]
for i in range(n):
    if ll[i]==max(ll):
        lll.append(l[i])

lll=sorted(set(lll))
for i in lll:
    print(i)


### FIXED CODE ###

n=int(input())
l=[input() for i in range(n)]

l=sorted(l)
ll=[]
k=1
for i in range(n-1):
    if l[i]==l[i+1]:
        ll.append(k)
        k+=1
    else:
        ll.append(k)
        k=1
ll.append(k)
c=max(ll)
lll=[]
for i in range(n):
    if ll[i]==c:
        lll.append(l[i])

lll=sorted(set(lll))
for i in lll:
    print(i)
### BUGGY CODE ###

A, B, LIMIT = map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))

t=0
newA=[]
for a in A:
  t += a
  newA.append(a)
  if t>LIMIT:
    newA.pop()
    break
    
newA=sorted(newA)
newAsum=[0]
for i, v in enumerate(newA):
  newAsum.append(newAsum[i]+v)

cnt=0
for i, a in enumerate(newAsum):
  j=0
  cnt2=i
  t = a
  for b in B:
    t += b
    if t>LIMIT:
      break
    cnt2+=1
  cnt = max(cnt, cnt2)
print(cnt)


### FIXED CODE ###

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

Asum=[0]
Bsum=[0]
for i, a in enumerate(A):
  Asum.append(Asum[i]+a)
for i, b in enumerate(B):
  Bsum.append(Bsum[i]+b)

ans, b = 0, M
for a, asum in enumerate(Asum):
  if asum > K:
    break
  while Bsum[b]>K - asum:
    b-=1
  ans = max(ans, a+b)
print(ans)
### BUGGY CODE ###

mod=10**9+7
def num2bi(x, k):
  #10進数xを2進数k桁(string)で出力
  out=format(x, '0'+str(k)+'b')
  return out

N=int(input())
A=list(map(int, input().split()))
ma=max(A)
keta=1
while ma>=2**keta:
  keta+=1
  
onekazu=[0 for i in range(keta)]
for i in range(N):
  temp=num2bi(A[i], keta)
  for j in range(keta):
    onekazu[-1-j]+=int(temp[-1-j])
    
out=0
for i in range(keta):
  temp=onekazu[i]*(N-onekazu[i])*(2**(keta-1-i))
  out+=temp
  out%=mod
  
print(out)

### FIXED CODE ###

mod=10**9+7
def num2bi(x, k):
  #10進数xを2進数k桁(string)で出力
  out=format(x, '0'+str(k)+'b')
  return out

N=int(input())
A=list(map(int, input().split()))
ma=max(A)
keta=1
while ma>=2**keta:
  keta+=1
  
onekazu=[0 for i in range(keta)]
k=str(keta)
for i in range(N):
  temp=format(A[i], '0'+str(k)+'b')
  onekazu=[onekazu[j]+1 if temp[j]=='1' else onekazu[j] for j in range(keta)]
    
out=0
out=sum([(onekazu[i]*(N-onekazu[i])%mod)*(2**(keta-1-i))%mod for i in range(keta)])
out%=mod  
print(out)
### BUGGY CODE ###

import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

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

    ans = 0
    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0

        d[0] = 1
        for i in range(N):
            s += int(S[N-i-1]) * 10**i
            d[s % P] += 1

        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2

    else:
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i+1



    print(ans)


if __name__ == "__main__":
  main()


### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)


INF=10**20
def solve(N,P,S,fact):
    ans = 0

    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0
 
        d[0] = 1
        for i in range(N):
            s += S[N-i-1] * fact[i]
            s %= P
            # s = int(s)
            d[s] += 1
            # print(s)
 
        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2
 
    else:
        for i in range(N):
            if S[i] % P == 0:
                ans += i+1

 
    return ans

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = list(next(tokens))  # type: str

    fact = [pow(10,i,P) for i in range(N)]

    S = list(map(int,S))
    S = np.array(S)
    print(solve(N, P, S,np.array(fact)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:],i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ab=[0]*K
abc=[]
i=0

for x in range(X):
  for y in range(Y):
    if i<=K-1:
    	ab[i]=A[x]+B[y]
    else:
      	ab.append(A[x]+B[y])
    i +=1

ab.sort(reverse=True)

K=min(K,3000)

for k in range(K):
  for z in range(Z):
    abc.append(ab[k]+C[z])

abc.sort(reverse=True)

for k in range(K):
	print(abc[k])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

K=min(K,3000)

AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:K] for c in C[:K]]
ABC.sort(reverse=True)

for k in range(K):
	print(ABC[k])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)

for i in range(n):
    if a[i] == a_max:
        print(max(a[0:i]+a[i+1:]))
    else:
        print(a_max)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)
idx = [i for i, x in enumerate(a) if x==a_max]

if len(idx) > 1:
    for i in range(n):
        print(a_max)
else:
    for i in range(n):
        if a[i] == a_max:
            print(max(a[0:i]+a[i+1:]))
        else:
            print(a_max)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
import collections
#d=collections.Counter(d)
t=collections.Counter(t)
for i in t.items():
  if i[0] not in d:
    print("NO")
    break
  if i[0] in d and i[1]>d.count(i[0]):
    print("NO")
    break
else:
  print("YES")


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
import collections
d=collections.Counter(d)
t=collections.Counter(t)
for i in t.items():
  if i[0] not in d:
    print("NO")
    break
  elif i[0] in d and i[1]>d[i[0]]:
    print("NO")
    break
else:
  print("YES")
### BUGGY CODE ###

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

ans = N

for i in range(N):
    for j in range(i):
        if P[i] > P[j]:
            ans -= 1
            break

print(ans)

### FIXED CODE ###

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

ans = 0
check = 10**9 + 7

for i in range(N):
    if check > P[i]:
        ans += 1
        check = P[i]

print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] += dp1[i]
            dp2_[i + a] += dp2[i]
        # G, B に塗った場合
        dp1_[i] += dp1[i] * 2
        dp2_[i] += dp2[i]
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans -= dp1[i] * 3
    if i * 2 == sum_A:
        ans += dp2[i] * 3
print(ans % MOD)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] = (dp1_[i + a] + dp1[i]) % MOD
            dp2_[i + a] = (dp2_[i + a] + dp2[i]) % MOD
        # G, B に塗った場合
        dp1_[i] = (dp1_[i] + dp1[i] * 2) % MOD
        dp2_[i] = (dp2_[i] + dp2[i]) % MOD
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)
### BUGGY CODE ###

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

opes = [0] * (K+1)
for i in range(2**N):
    blue_cnt = 0
    ope_count = 0
    operating = False
    bin2str = format(i, '0' + str(N) + 'b')
    for j in range(N):
        if blue_cnt > K:
            break
        elif j == (N - 1):
            if int(bin2str[-1]) == 1:
                blue_cnt += 1
                ope_count += 1
            elif operating:
                ope_count += 1
        elif operating and int(bin2str[j:j+1:]) == 0:
            operating = False
            ope_count += 1
        elif operating == False and int(bin2str[j:j+1:]) == 1:
            operating = True
            blue_cnt += 1
        elif operating and int(bin2str[j:j+1:]) == 1:
            blue_cnt += 1
    if blue_cnt == K:
        opes[ope_count] += 1
for i in opes[1::]:
    print(i%100000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

nCr = {}
def combination(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = combination(n-1,r) + combination(n-1,r-1)
    return nCr[(n,r)]

N, K = map(int, input().split())
for i in range(1, K+1):
	if i <= N-K+1:
		A = combination(N-K+1, i)
		P = combination(K-1, i-1)
		B = A * P
		print(B % (10**9+7))
	else:
		print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
    import sys

    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    point_K = 1
    
    for i in range(K):
        point_K *= A_list[i]
    
    current = 1
    prev = point_K

    for i in range(K, len(A_list)):
        current = prev / A_list[i-K] * A_list[i]

        if current > prev:
            print("Yes")
        else:
            print("No")
        
        prev = current


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    import sys
    import math

    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))

    for i in range(len(A_list)):
        A_list[i] = math.log10( A_list[i] )


    point_K = 0
    
    for i in range(K):
        point_K += A_list[i]


    prev = point_K

    for i in range(K, len(A_list)):
        current = prev - A_list[i-K] + A_list[i]

        if current > prev:
            print("Yes")
        else:
            print("No")
        
        prev = current


if __name__ == "__main__":
    main()
### BUGGY CODE ###

def solve(n, k):
    occurence = set()

    while n not in occurence:
        if k == 1:
            print(0)
            return

        occurence.add(n)

        n = abs(n - k)
        if n == 0:
            print(n)
            return

    min_value = min(occurence)
    print(min_value)


if __name__ == '__main__':
    nk = input().split()

    n = int(nk[0])
    k = int(nk[1])

    solve(n, k)


### FIXED CODE ###

def solve(n, k):
    occurence = set()

    diff = n % k
    n = diff
    
    if diff == 0 or diff == 1:
        print(diff)
        return
    else:
        while n not in occurence:
            if k == 1:
                print(0)
                return

            occurence.add(n)

            n = abs(n - k)

            if n == 0:
                print(n)
                return

    min_value = min(occurence)
    print(min_value)


if __name__ == '__main__':
    nk = input().split()

    n = int(nk[0])
    k = int(nk[1])

    solve(n, k)
### BUGGY CODE ###

S = input()
Q = int(input())
count = 0
for i in range(Q):
    arr = list(input().split())
    if len(arr) == 1:
        count += 1
    else:
        if arr[1] == '1':
            if count%2==0:
                S = arr[2] + S
            else:
                S = S + arr[2]
        else:
            if count%2!=0:
                S = arr[2] + S
            else:
                S = S + arr[2]
if count%2 == 0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
count = 0
right = ''
left = ''
for i in range(Q):
    arr = list(input().split())
    if len(arr) == 1:
        count += 1
    else:
        if arr[1] == '1':
            if count%2==0:
                left = arr[2] + left
            else:
                right = right + arr[2]
        else:
            if count%2!=0:
                left = arr[2] + left
            else:
                right = right + arr[2]
S = left + S + right
if count%2 == 0:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

n,m=(int(x) for x in input().split())
import math as math
import numpy as np


A = [int(x) for x in input().split()]

for i in range(m):
    A.sort()
    A [-1] = A[-1]/2
for i in range(n):
   A[i] =  math.floor(A[i]) 
print( sum(int(i) for i in A))


### FIXED CODE ###

#キューを使っている。ところどころマイナスにしているのはキューの性質のため。実行時間が全然違うのはソートが早いから
n,m = map(int,input().split())
a = list(map(lambda x: -int(x) ,input().split()))

import heapq
heapq.heapify(a)
for _ in range(m):
  tmp = -heapq.heappop(a)
  tmp //= 2
  heapq.heappush(a,-tmp)
print(-sum(a))
### BUGGY CODE ###

N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    if c == 'W':
        MW[a] = i
    else:
        MB[a] = i
data = [0]*(2*N+1)
def add(k, x):
    while k <= 2*N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
AW = sorted(MW)
AB = sorted(MB)
cB = [[0]*(N+1) for i in range(N+1)]
cW = [[0]*(N+1) for i in range(N+1)]

IW = [MW[a]+1 for a in AW]
IB = [MB[a]+1 for a in AB]

for i in range(2*N):
    add(i+1, 1)
for i in range(N):
    cWi = cW[i]; cBi = cB[i]
    for j in range(N):
        cWi[j] = get(IW[i])-1
        cBi[j] = get(IB[j])-1
        add(IB[j], -1)
    cWi[N] = get(IW[i])-1

    for j in range(N):
        add(IB[j], 1)
    if i < N:
        add(IW[i], -1)
cBi = cB[N]
for j in range(N):
    cBi[j] = get(IB[j])-1
    add(IB[j], -1)

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N+1):
    T = dp[i]
    S = dp[i-1]
    cWi = cW[i-1]; cBi = cB[i]
    for j in range(N+1):
        v = T[j]
        if i:
            v = min(v, S[j] + cWi[j])
        if j:
            v = min(v, T[j-1] + cBi[j-1])
        T[j] = v
print(dp[N][N])


### FIXED CODE ###

from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
    dist[i+1][0] = dist[i][0] + P[i][0]
for i in range(N):
    dist[0][i+1] = dist[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dist[i+1][j+1] = min(dist[i][j+1] + P[i][j+1], dist[i+1][j] + Q[j][i+1])
print(dist[N][N])
### BUGGY CODE ###

N,M = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(M) ]

up = [ set([]) for i in range(N)]
dw = [ set([]) for i in range(N)]

for l,r,d in li:
  dw[l-1].add(r-1)
  up[r-1].add(l-1)

S = []
for n in range(N):
  if ( len(up[n])==0 ):
    S.append(n)
L = []
for i in range(N+M):

  if ( len(S)==0 ):
    break
  n = S.pop()
  L.append(n)
  for r in dw[n]:
    up[r].discard(n)
    if ( len(up[r]) == 0 ):
      S.append(r)
  dw[n]=set()

BREAK=False
if (sum([len(s) for s in up])>0):
    BREAK=True

dwl = [ set([]) for i in range(N)]
for l,r,d in li:
  dwl[l-1].add((r-1,d))

dis = [-1]*N

for n in L:
  if (BREAK):
    break
  if (dis[n]==-1):
    dis[n]=0
  for r,d in dwl[n]:
    if (dis[r]==-1):
        dis[r]=dis[n]+d
    else:
        if not (dis[r]==dis[n]+d):
            BREAK=True
            break
if (BREAK):
    print ("No")
else:
    print ("Yes")


        

### FIXED CODE ###

N,M = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(M) ]

up = [ set([]) for i in range(N)]
dw = [ set([]) for i in range(N)]

for l,r,d in li:
  dw[l-1].add(r-1)
  up[r-1].add(l-1)

S = []
for n in range(N):
  if ( len(up[n])==0 ):
    S.append(n)
L = []
for i in range(N+M):

  if ( len(S)==0 ):
    break
  n = S.pop()
  L.append(n)
  for r in dw[n]:
    up[r].discard(n)
    if ( len(up[r]) == 0 ):
      S.append(r)
  dw[n]=set()

BREAK=False
if (sum([len(s) for s in up])>0):
    BREAK=True

dwl = [ set([]) for i in range(N)]
for l,r,d in li:
  dwl[l-1].add((r-1,d))

dis = [-1]*N

for n in L:
  if (BREAK):
    break
  if (dis[n]==-1):
    dis[n]=0
  for r,d in dwl[n]:
    if (dis[r]==-1):
        dis[r]=dis[n]+d
    else:
        if not (dis[r]==dis[n]+d):
            BREAK=True
            break
if (BREAK):
    print ("No")
else:
    print ("Yes")
### BUGGY CODE ###

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append([i, j, 0])
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x, y] = 1
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N = ini()


def solve():
    p = q = 1
    for i in range(N):
        x, y = inm()
        k = 1
        while True:
            if x * k >= p and y * k >= q:
                p = x * k
                q = y * k
                break
            k += 1
    return p + q


print(solve())


### FIXED CODE ###

import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N = ini()


def solve():
    p = q = 1
    for i in range(N):
        x, y = inm()
        k = max(p // x, q // y, 1)
        while True:
            if x * k >= p and y * k >= q:
                p = x * k
                q = y * k
                break
            k += 1
    return p + q


print(solve())
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
S = list(input())
T = list(input())
from math import gcd

leng = N*M//gcd(N, M)

for i in range(1, leng+1):
    if (i-1)%(leng//N)==0 and(i-1)%(leng//M)==0:
        if S[(i-1)//(leng//N)]!=T[(i-1)//(leng//M)]:
            print(-1)
            break
else:
    print(leng)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
S = list(input())
T = list(input())
from math import gcd

leng = N*M//gcd(N, M)
step = (leng//N)*(leng//M)//gcd((leng//N), (leng//M))

for i in range(1, leng+1, step):
    if (i-1)%(leng//N)==0 and(i-1)%(leng//M)==0:
        if S[(i-1)//(leng//N)]!=T[(i-1)//(leng//M)]:
            print(-1)
            break
else:
    print(leng)