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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = input()
RLlist = [None]*len(S)
location = []
for i in range(len(S)-1):
    if S[i]=='R' and S[i+1] == 'L':
        RLlist[i] = 'r'
        RLlist[i+1] = 'l'
        location.append(i)

location.sort()
def findhigh(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i]


def findlow(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i-1]
    return ylist[-1]

ans_list = [1 if RLlist[i] != None else 0 for i in range(len(S))]

for i in range(len(S)):
    if S[i] == 'R' and RLlist[i] != 'r':
        diff = abs(findhigh(i,location)-i)
        if diff%2 == 1:
            ans_list[findhigh(i,location)+1]+=1
        else:
            ans_list[findhigh(i,location)]+=1
    if S[i] == 'L' and RLlist[i] != 'l':
        diff = abs(findlow(i,location)-i)
        if diff%2 == 1:
            ans_list[findlow(i,location)+1]+=1
        else:
            ans_list[findlow(i,location)]+=1
        

print(*ans_list)

### FIXED CODE ###

'''from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
'''
S = input()
RLlist = [None]*len(S)
location = []
for i in range(len(S)-1):
    if S[i]=='R' and S[i+1] == 'L':
        RLlist[i] = 'r'
        RLlist[i+1] = 'l'
        location.append(i)

location.sort()
def findhigh(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i]


def findlow(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i-1]
    return ylist[-1]

ans_list = [1 if RLlist[i] != None else 0 for i in range(len(S))]

for i in range(len(S)):
    if S[i] == 'R' and RLlist[i] != 'r':
        high =findhigh(i,location) 
        diff = abs(high-i)
        if diff%2 == 1:
            ans_list[high+1]+=1
        else:
            ans_list[high]+=1
    if S[i] == 'L' and RLlist[i] != 'l':
        low = findlow(i, location)
        diff = abs(low-i)
        if diff%2 == 1:
            ans_list[low+1]+=1
        else:
            ans_list[low]+=1
        

print(*ans_list)
### BUGGY CODE ###

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

h += [float("inf")] * (K)
dp = [float("inf")] * (N+K)
dp[0] = 0
for i in range(N):
    for j in range(K):
        dp[i+j+1] = min(dp[i+j+1], dp[i]+abs(h[i] - h[i+j+1]))


print(dp[N-1])

### FIXED CODE ###

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

h += [float("inf")] * (K)
dp = [float("inf")] * (N+K)
dp[0] = 0
for i in range(N):
    for j in range(K):
        dp[i+j+1] = min(dp[i+j+1], dp[i]+abs(h[i] - h[i+j+1]))


print(dp[N-1])
### BUGGY CODE ###

n = int(input())
s = input()

count = 0
for i in range(0,n-3):
  ii = s[i]
  for j in range(i+1, n-1):
    jj = s[j]
    if ii==jj:
      continue
    for k in range(j+1,n):
      kk=s[k]
      if j-i == k-j:
        continue
      if jj != kk and kk!=ii:
          count = count + 1
print(count)


### FIXED CODE ###

n = int(input())
s = input()

count = 0
r=0
g=0
b=0
for i in range(0,n):
  if s[i] == 'R':
    r = r + 1
  if s[i]=='G':
    g = g+1
  if s[i]=='B':
    b = b+1
    
for i in range(0,n):
  ii = s[i]
  for j in range(i+1, n):
    jj = s[j]
    if ii==jj:
      continue
    if (2*j-i)<=(n-1):
      if ii!=s[2*j-i] and jj!=s[2*j-i]:
        count = count + 1
print(r*g*b-count)
### BUGGY CODE ###

A,B = map(int,input().split())
T = A
for i in range(A+1,B+1):T ^= i 
else:print(T)

### FIXED CODE ###

def xor_sum(n):
    m1 = (n+1)//4
    m2 = (n+1)%4
    if m2 == 0:return 0
    else:
        ret = 0
        for i in range(m1*4,m1*4+m2):ret ^= i
        else: return ret

a,b = map(int, input().split())
if a==b:print(a)
else:
    ans = xor_sum(a-1) ^ xor_sum(b)
    print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for v in range(min(A), max(A) + 1):
    ans = max(A.count(v - 1) + A.count(v) + A.count(v + 1), ans)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = 0
start, end = min(A), max(A) + 1
for v in range(start, end):
    ans = max(C[v - 1] + C[v] + C[v + 1], ans)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))

e_nums = [(i+1)/2 for i in nums]

max_sum = 0
for i in range(n):
  if i+k <= n:
    max_sum = max(max_sum, sum(e_nums[i:i+k]))

print(max_sum)


### FIXED CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))
 
sum_max = sum(nums[:k])
temp = sum_max
for i in range(k,n):
  temp -= nums[i-k]
  temp += nums[i]
  sum_max = max(temp, sum_max)
print((sum_max +k)/2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

a=[0]*(n+1)
for i in range(1,n+1):
    for j in range(1,42):
        for k in range(1,42):
            for l in range(1,42):
                if j**2+k**2+l**2+j*k+k*l+l*j==i:
                    a[i]+=1
                    break
                elif j**2+k**2+l**2+j*k+k*l+l*j>i:
                    break
for x in range(1,n+1):
    print(a[x])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

a=[0]*(n)
for j in range(1,n+1):
    for k in range(1,n+1):
        for l in range(1,n+1):
            if j**2+k**2+l**2+j*k+k*l+l*j>n:
                break
            else:
                a[j**2+k**2+l**2+j*k+k*l+l*j-1]+=1

for i in a:
    print(i)
### BUGGY CODE ###

import collections
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(int(i) for i in input().split())
ans_list = []
ans = 0
for i in range(N):
	if a[N-1-i] == 1:
		ans += 1
		ans_list.append(N-i)
		chk = make_divisors(N-i)
		for j in range(len(chk)):
			a[chk[j]-1] = (1+a[chk[j]-1])%2
print(ans)
if len(ans_list) != 0:
	print(*ans_list)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
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(int(i) for i in input().split())
ans_list = []
ans = 0
for i in range(N):
	if a[N-1-i] == 1:
		ans += 1
		ans_list.append(N-i)
		chk = make_divisors(N-i)
		for j in range(len(chk)):
			a[chk[j]-1] = (1+a[chk[j]-1])%2
print(ans)
if len(ans_list) != 0:
	print(*ans_list)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())

pairs = []
for _ in range(M):
    pairs.append(list(map(int, input().split())))
pairs = pairs[::-1]

# rank保持のためにunionでrankを足し合わせる
# 島を数えるためにデフォルトのrank=1とする
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

    def root(self, x):
        if (self.par[x]==x):
            return x
        else:
            # path compression
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if (x==y):
            return

        if (self.rank[x] < self.rank[y]):
            self.par[x] = y
            self.rank[y] += self.rank[x]
            self.rank[x] = 0
        else:
            self.par[y] = x
            self.rank[x] += self.rank[y]
            self.rank[y] = 0

    def find(self, x, y):
        return self.root(x)==self.root(y)
    
    def get_inconvenience(self):
        rank = np.array(self.rank)
        return int(np.sum(rank*(len(self.rank)-rank))/2)

uf = UnionFind(N)
inconvenience = []
for m in range(M):
    inconvenience.append(uf.get_inconvenience())
    uf.union(pairs[m][0]-1, pairs[m][1]-1)

print(*inconvenience[::-1], sep='\n')


### FIXED CODE ###

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

pairs = []
for _ in range(M):
    pairs.append(list(map(int, input().split())))
pairs = pairs[::-1]

# rank保持のためにunionでrankを足し合わせる
# 島を数えるためにデフォルトのrank=1とする
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

    def root(self, x):
        if (self.par[x]==x):
            return x
        else:
            # path compression
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if (x==y):
            return

        if (self.rank[x] < self.rank[y]):
            self.par[x] = y
            self.rank[y] += self.rank[x]
            self.rank[x] = 0
        else:
            self.par[y] = x
            self.rank[x] += self.rank[y]
            self.rank[y] = 0

    def find(self, x, y):
        return self.root(x)==self.root(y)
    
    def get_inconvenience(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x==y:
            return 0
        else:
            return self.rank[x] * self.rank[y]

uf = UnionFind(N)
inconvenience = [int(N*(N-1)/2)]
for m in range(M-1):
    inconvenience.append(inconvenience[-1] - uf.get_inconvenience(pairs[m][0]-1, pairs[m][1]-1))
    uf.union(pairs[m][0]-1, pairs[m][1]-1)

print(*inconvenience[::-1], sep='\n')
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)

    f(weights[0], 0)
    for a in ans:
        print(a, end=' ')
    print()


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].add(b-1)
        G[b-1].add(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)
        return  0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


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

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, point):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        point[c] += point[v]
        dfs(G, c, v, point)


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

    point = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        point[p] += x

    dfs(G, 0, -1, point)
    print(" ".join(map(str, point)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, point):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        point[c] += point[v]
        dfs(G, c, v, point)


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

    point = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        point[p] += x

    dfs(G, 0, -1, point)
    print(" ".join(map(str, point)))


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

def main():
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    for i in range(m):
        choice_time, num = map(int, input().split())
        if num > min(data):
            for _ in range(choice_time):
                if num > min(data):
                    data[ data.index( min(data) ) ] = num
        
    return sum(data)

print(main())


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [list(map(int,input().split())) for p in range(m)]
b.sort(key=lambda q: -q[1])
 
c = 0
for s in b:
	for t in [0]*s[0]:
		if c + 1 > n:
			break
		if s[1] <= a[c]:
			break
		a[c] = s[1]
		c += 1
	else:
		continue
	break
print(sum(a))
### BUGGY CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while ng - ok > 1 and c < 1000:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))


### FIXED CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))
### BUGGY CODE ###

s = input()
t = input()

ls,lt = len(s), len(t)
# dp[i][j] : siとtjにおけるLCS
dp = [['']*(lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i]==t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
            if len(dp[i][j+1])>len(dp[i+1][j+1]):
                dp[i+1][j+1] = dp[i][j+1]
            if len(dp[i+1][j])>len(dp[i+1][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]

print(dp[ls][lt])

### FIXED CODE ###

s = input()
t = input()
ls, lt = len(s), len(t)

ans = ''
dp = [[0]*(lt+1) for _ in range(ls+1)]
for j in range(ls):
    for i in range(lt):
        if s[j]==t[i]:
            dp[j+1][i+1] = dp[j][i]+1
        else:
            dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])

if dp[ls][lt] == 0:
    print('')
    exit()

i = lt
j = ls

while i>0 and j>0:
    if s[j-1] == t[i-1]:
        ans += s[j-1]
        i -= 1
        j -= 1
    else:
        if dp[j-1][i]>dp[j][i-1]:
            j -= 1
        else:
            i -= 1
print(ans[::-1])
### BUGGY CODE ###

n = input()
a = list(map(int, input().split()))
r = 1

for i in range(len(a)):
  r *= a[i]

if r > pow(10, 18):
  print(-1)
else:
  print(r)

### FIXED CODE ###

import sys
def input():
  return sys.stdin.readline()[:-1]


n = input()
a = input().split()
r = 1

if '0' in a:
  print(0)
  exit()

for i in range(len(a)):
  aa = int(a[i])
  r *= aa
  if r > pow(10, 18):
    print(-1)
    exit()

print(r)
### BUGGY CODE ###

import numpy as np


def move_and_compute_cost(field, d, l, r):
    if l == r:
        return 0

    # create l to r route
    route = np.arange(l, r + 1, d)

    points = np.squeeze([np.where(field == ch) for ch in route])
    next_points = np.vstack([points[1:], points[-1]])

    cost = np.abs(points - next_points).sum()
    return cost


if __name__ == '__main__':
    h, w, d = [int(v) for v in input().split()]

    # read field
    field = np.empty((h, w), dtype=int)
    for i in range(h):
        line = [int(v) for v in input().split()]
        field[i, :] = line

    ls, rs = [], []
    q = int(input())
    for i in range(q):
        line = [int(v) for v in input().split()]
        ls.append(line[0])
        rs.append(line[1])

    costs = [move_and_compute_cost(field, d, l, r) for l, r in zip(ls, rs)]
    for c in costs:
        print(c)


### FIXED CODE ###

if __name__ == '__main__':
    h, w, d = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(h)]

    # f => (y, x) mapping
    c_map = [0] * (h * w)
    for y in range(h):
        for x in range(w):
            c_map[f[y][x] - 1] = (y, x)

    # cost accumulation
    d_map = [0] * (h * w)
    for i in range(d, h * w):
        y, x = c_map[i]
        y2, x2 = c_map[i - d]
        d_map[i] = d_map[i - d] + abs(y2 - y) + abs(x2 - x)

    results = []
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        results.append(d_map[r - 1] - d_map[l - 1])

    print("\n".join(map(str, results)))
### BUGGY CODE ###

import functools
A,B=[int(_) for _ in input().split()]
def fxor(a,b):
    return a^b
def fxorA2B(a,b):
    if a < b:
        return functools.reduce(fxor,range(a,b+1))
    else:
        return a
def lenbin(X):
    return len(bin(X)) - 3
iA = lenbin(A)
iB = lenbin(B)
if iA == iB:
    print(fxorA2B(A,B))
else:
    print(fxorA2B(A,(2**(iA+1) - 1))^fxorA2B(2**iB,B))


### FIXED CODE ###

A,B=[int(_) for _ in input().split()]
def fxor(a,b):
    return a^b

def fxorA2B(a,b,iD):
    def calcFD(g,b):
        return (g -1) //2 % 2 if b else g//2 % 2
    if a < b:
        if a == 2**iD :
            sB = bin(b)[2:][::-1]
            i2 = 2**iD -1
            bB = (b - i2)%2
            iC = 0
            for i in range(iD+1):
                iB = int(sB[i])
                if i == 0 and calcFD(b-i2,bB):
                    iC += 1
                elif iB and bB:
                    iC += 2**i
        else:
            a -= 1
            sA = bin(a)[2:][::-1]
            sB = bin(b)[2:][::-1]
            i2 = 2**iD -1
            bA = (a - i2)%2
            bB = (b - i2)%2
            iC = 0
            for i in range(iD+1):
                iA = int(sA[i])
                iB = int(sB[i])
                if i == 0 and calcFD(a-i2,bA) ^ calcFD(b-i2,bB):
                    iC += 1
                elif (iA and bA) ^ (iB and bB):
                    iC += 2**i
        return iC
    else:
        return a
def lenbin(X):
    return len(bin(X)) - 3
iA = lenbin(A)
iB = lenbin(B)
if iA == iB:
    print(fxorA2B(A,B,iA))
else:
    if iA == 0 :
        print(fxorA2B(2**iB,B,iB))
    else:
        print(fxorA2B(A,(2**(iA+1) - 1),iA)^fxorA2B(2**iB,B,iB))
### BUGGY CODE ###

# coding: utf-8
import itertools


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = len(set(''.join(c) for c in itertools.combinations(s, 3)))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0

    index = [[] for _ in range(10)]
    for i in range(n):
        index[int(s[i])].append(i)

    for i in range(1000):
        iii = '{:03d}'.format(i)
        cur = -1
        found = False

        for e, j in enumerate(iii):
            found = False

            for k in index[int(j)]:
                if cur < k:
                    found = True
                    cur = k
                    break

            if not found:
                break

        if found:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
  c,d=map(int,input().split())
  e,f=c,d
  times=1
  while(e<t or f<a):
    #print(e,f)
    times+=1
    e,f=c*times,d*times
    #print(e,f)
  t,a=e,f
print(t+a)


### FIXED CODE ###

n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
  c,d=map(int,input().split())
  if(t/c>a/d):
    if(t%c==0):times=t//c
    else:times=t//c+1
  else:
    if(a%d==0):times=a//d
    else:times=a//d+1
  #print(times)
  t,a=c*times,d*times
  #print(t,a)
print(t+a)
### BUGGY CODE ###

s=input()
n=len(s)
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
mod=10**9+7

for i in range(n):
  if s[i]=="?":
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)


### FIXED CODE ###

s=input()
n=len(s)
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
mod=10**9+7

for i in range(n):
  if s[i]=="?":
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)
### BUGGY CODE ###

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [1 if a[0] >= j else 0 for j in range(K+1)]
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())


### FIXED CODE ###

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [0] * (K+1)
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())