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

def main():
    class rolling_hash():
        def __init__(self, seq, char_list=None):
            seq_size = self.seq_size = len(seq)  # 文字列の長さ
            mod = self.mod = 2**61-1  # mod
            base = self.base = 3
            Hash = self.Hash = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(seq_size):
                Hash[i+1] = (Hash[i] + (seq[i]+1) * pow(base, i, mod)) % mod

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash[r] - self.Hash[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    memo = []

    a1 = rolling_hash([a[i-1] ^ a[i] for i in range(n)] +
                      [a[i-1] ^ a[i] for i in range(n)])
    b_hash = rolling_hash([b[i-1] ^ b[i] for i in range(n)]).calc_hash(0, n)
    for i in range(n):
        if a1.calc_hash(i, i+n) == b_hash:
            memo.append(i)
    b0 = b[0]
    for i in memo:
        x = b0 ^ a[i]
        print(i, x)


main()

### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

# DP
def main():
    from builtins import input, int, map, max, min, range

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                if dpj + v > dp[jw]:
                    dp[jw] = dpj + v
                if jw > max_w:
                    max_w = jw
    print(max(dp))


main()


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n,x,y = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(n)]

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

ans = shortest_path(np.array(graph))
u= np.unique(ans)

for i in range(1,n):
    if i in u:
        print(int(np.count_nonzero(ans == i)/2))
    else:print(0)

### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans[min(abs(i-j) , abs(i-x)+1+abs(j-y), abs(i-y)+1+abs(j-x)) ]+=1
        
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
alph = {key + 1: val for key, val in enumerate('abcdefghijklmnopqrstuvwxyz')}
alph[0] = 'z'
answer = ''
while N >= 1:
  answer = alph[N % 26] + answer
  if N == 26:
    break
    N //= 26

    print(answer)

### FIXED CODE ###

N = int(input())
alph = {key + 1: val for key, val in enumerate('abcdefghijklmnopqrstuvwxyz')}
alph[0] = 'z'
answer = ''
while N >= 1:
  answer = alph[N % 26] + answer
  if N == 26:
    break
  N = (N - 1) // 26

print(answer)
### BUGGY CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod))
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa)

    lc = C[n - 1] - C[b]
    lqc = Q[n - 1] - Q[b]
    c = (lc * mod_pow(3, lqc, mod))
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc)
    
    ans = (ans + (a * c)) % mod

print(ans % mod)

### FIXED CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

dp = [[0] * 4 for _ in range(n + 1)]

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])
### BUGGY CODE ###

def make_divisors(n):
	divisors = [1]
	for i in range(2, 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()))
num = 0
ans = []
for i in range(N):
	list = make_divisors(N - i)
	if a[N - 1 - i] % 2 == 1:
		num += 1
		ans.append(N - i)
		for j in list:
			a[j - 1] += 1
print(num)
Ans = [str(x) for x in ans]
print(' '.join(Ans))

### FIXED CODE ###

N = int(input())
a = [0] + list(map(int, input().split()))
ans = [0] * (N + 1)
an = []
for i in range(N, 0, -1):
	if sum(ans[i * 2 :: i]) % 2 != a[i]:
		ans[i] = 1
		an.append(i)
print(len(an))
Ans = [str(x) for x in an]
print(' '.join(Ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

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

    for i in range(N):
        for j in range(0,T):
            if j >= A[i]: ##今回の商品がjよりも小さい
                if dp[i][j-A[i]][0]+B[i]>=dp[i][j][0]: ## 選ぶ
                    dp[i+1][j][0] = dp[i][j-A[i]][0]+B[i]
                    dp[i+1][j][1] = dp[i][j-A[i]][1] + [i]
                else:
                    dp[i+1][j][0] = dp[i][j][0]
                    dp[i+1][j][1] = dp[i][j][1]
            else: ## 選ばない
                dp[i+1][j][0] = dp[i][j][0]
                dp[i+1][j][1] = dp[i][j][1]
    
    index = list(range(0,N))
    a = list(set(index)- set(dp[N][T-1][1]))
    
    max_add = 0
    for i in a:
        max_add = max(max_add,B[i]) 

    print(dp[N][T-1][0]+max_add)
    return


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
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

    dp  = [[0 for _ in range(T)] for _ in range(N+1)]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][T-1]+B[i])

        for j in range(0,T):

            if j >= A[i]: ##今回の商品がjよりも小さい
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


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
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

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

import sys

rl = sys.stdin.readline

def a():
    n, k = map(int, rl().split())

    li = list(map(int, rl().split()))

    dp = [1<<60]*n

    dp[0] = 0
    dp[1] = abs(li[0] - li[1])

    if k < n:    
        for i in range(2, k):
            for j in range(i):
                a = dp[j] + abs(li[j] - li[i])
                if dp[i] > a:
                    dp[i] = a
        for i in range(k, n):
            for j in range(i-k, i):
                a = dp[j] + abs(li[j] - li[i])
                if dp[i] > a:
                    dp[i] = a
    else:
        for i in range(n):
            for j in range(i):
                a = dp[j] + abs(li[j] - li[i])
                if dp[i] > a:
                    dp[i] = a

    print(int(dp[-1]))
a()



### FIXED CODE ###

import sys

rl = sys.stdin.readline

n, k = map(int, rl().split())

li = list(map(int, rl().split()))

dp = [1<<60]*n

dp[0] = 0
dp[1] = abs(li[0] - li[1])

if k < n:    
    for i in range(2, k):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
    for i in range(k, n):
        for j in range(i-k, i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
else:
    for i in range(n):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
        
print(int(dp[-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int,input().split())
S = input()
for _ in range(Q):
  l, r = map(int,input().split())
  print(S[l-1:r].count('AC'))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N, Q = map(int,input().split())
S = input()
nums = [0] * (N + 1)
for i in range(N):
  nums[i+1] = nums[i] + (1 if S[i:i+2]=='AC' else 0)
    
for j in range(Q):
  l, r = map(int,input().split())
  print(nums[r-1] - nums[l-1])
### BUGGY CODE ###

import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []

for i in range(N-3):
    BC = A[0 : i + 2]
    s = 0
    for j in range(i + 2):
        s += BC[j]
        if s + BC[j + 1] > sum(BC) / 2:
            if BC[j + 1] / 2 >= sum(BC) / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
            break
    DE = A[i + 2 : N + 1]
    s = 0
    for j in range(N - i - 3):
        s += DE[j]
        if j == N - i - 2:
            D = DE[0 : j + 1]
            D = DE[0 : j + 1]
            E = DE[j + 1 : N - i]
            break
        elif s + DE[j + 1] > sum(DE) / 2:
            if DE[j + 1] / 2 >= sum(DE) / 2 - s:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
            else:
                D = DE[0 : j + 2]
                E = DE[j + 2 : N - i]
            break
    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

### FIXED CODE ###

import statistics
import math

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


ureshimi = []
k = 0
l = 2

B = 0
C = 0
D = 0
E = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(2, N - 1):
    for j in range(k, i):
        if j == i - 1:
            k = j
            C = sumBC - B
            break
        elif B + A[j] >= sumBC / 2:
            if sumBC / 2 - B  > A[j] / 2:
                B += A[j]
                k = j + 1
                C = sumBC - B
                break
            else:
                k = j
                C = sumBC - B
                break
        B += A[j]
    for j in range(l, N):
        if j == N - 1:
            l = j
            E = sumDE - D
            break
        elif D + A[j] >= sumDE / 2:
            if sumDE / 2 - D > A[j] / 2:
                D += A[j]
                l = j + 1
                E = sumDE - D
                break
            else:
                l = j
                E = sumDE - D
                break
        D += A[j]
    ureshimi.append(max([B, C, D, E]) - min([B, C, D, E]))
    sumBC += A[i]
    sumDE -= A[i]
    D -= A[i]
        

print(min(ureshimi))
### BUGGY CODE ###

s = input()
n = len(s)
cnts = [0]*2019
cnts[0] = 1
ans = 0
for i in range(n):
    cnts[int(s[i:])%2019] += 1

for cnt in cnts:
    if cnt >= 2:
        ans += cnt * (cnt-1) //2
print(ans)


### FIXED CODE ###

s = input()[::-1]
a = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
for c in s:
    a += int(c) * d
    a %= 2019
    d *= 10
    d %= 2019
    cnt[a] += 1

#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

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

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

from collections import deque
dA = deque(A)
ans=[]
for i in range(N):
  Nans = 0
  for itr, val in enumerate(dA):
    if itr % 2 == 0:
      Nans += val
    else:
      Nans -= val
  ans.append(Nans)
  aa = dA.popleft()
  dA.append(aa)
print(' '.join(map(str, ans)))

### FIXED CODE ###

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

from collections import deque
dA = deque(A)
ans= deque([])
Nans = 0
for itr, val in enumerate(dA):
  if itr % 2 == 0:
    Nans += val
  else:
    Nans -= val
ans.append(Nans)

for i in A:
  Nans = 2*i - Nans
  ans.append(Nans)
ans.pop()
print(' '.join(map(str, ans)))
### BUGGY CODE ###

N,Q = map(int, input().split())
S = str(input())

ans = ''
for q in range(Q):
    l,r = map(int, input().split())
    s = S[l-1:r]
    ans += str(len(s.split('AC'))-1)+'\n'

print(ans.rstrip())

### FIXED CODE ###

N,Q = map(int, input().split())
S = str(input())

before = ''
i = 0
num = 0
data_list = {}
for s in S:
    if before == 'A' and s == 'C':
        num += 1
    before = s
    data_list[i] = num
    i += 1

ans = ''
for q in range(Q):
    r,l = map(int, input().split())
    ans += str(data_list[l-1]-data_list[r-1])+'\n'

print(ans.rstrip())
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    tmp = list(map(str,input().split()))
    if tmp[0] == '2':
        if tmp[1] == '1':
            s = tmp[2] + s
        else:
            s = s + tmp[2]
    else:
        s = s[::-1]
print(s)

### FIXED CODE ###

S = input()
Q = int(input())
A = [input().split() for i in range(Q)]

tmp = 0
s = S
t = ''

for li in A:
#     print(s,t,tmp)
    if li[0] == '1':
        tmp = (tmp+1)%2
    else:
        if (tmp+int(li[1]))%2 == 1:
            t += li[2]
        else:
            s += li[2]
            
if tmp == 0:
    print(t[::-1]+s)
else:
    print(s[::-1]+t)
### BUGGY CODE ###

N = int(input())
funcionarios = list(map(int,input().split()))
lista = [0 for i in range(N)]
a = 1
for x in lista:
    x += funcionarios.count(a)
    a += 1
    print(x)


### FIXED CODE ###

N = int(input())
funcionarios = list(map(int,input().split()))
frequencia = [0 for i in range(N)]

for i in funcionarios:
    frequencia[i-1] += 1

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

n = int(input())
s = input()
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)

def func(a,b,c):
    ans = 0
    for i in a:
        for j in [num1 for num1 in b if num1 >i]:
            for k in [num2 for num2 in c if num2 > j]:
                if j-i != k-j:
                    ans += 1
    return ans
print(func(r,g,b) + func(r,b,g) + func(g,r,b) + func(g,b,r) + func(b,g,r) + func(b,r,g))

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')
for i in range(n-2):
    for j in range(i+1, n-1):
        if 2*j - i >= n:
            break
        elif s[i] != s[j] and s[j] != s[(2*j-i)] and s[(2*j-i)] != s[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
L = [[0 for i in range(N)] for j in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0
for i in range(N):
    tmp = format(As[i], 'b').zfill(60)
    for j in range(60):
        L[j][i] = (int(tmp[j]))

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i+1)]
    a = sum(L[i]) % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)


### FIXED CODE ###

N = int(input())
L = [0 for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0

for A in As:
    for i in range(60):
        if A >> i & 1 == 1:
            L[i] += 1

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[i]
    a = L[i] % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)
### BUGGY CODE ###

Q = 998244353
def modpower(a,b,Q):#a^b mod Q
    if b == 0:
        return 1
    if b%2 == 0:
        d = modpower(a,b//2,Q)
        return d*d%Q
    if b%2 == 1:
        return (a*modpower(a,b-1,Q))%Q
def factorials(n,Q):#n以下の階乗のリストと階乗の逆元のmodQでのリスト
    F = [1]*(n+1)
    R = [1]*(n+1)
    for i in range(n):
        F[i+1] = F[i]*(i+1)%Q
        R[i+1] = R[i]*modpower(i+1,Q-2,Q)
    return F, R

N, A, B, K = map( int, input().split())
ans = 0
F, R = factorials(N,Q)

for i in range( min(K//A, N)+1):
    if (K-A*i)%B == 0:
        j = (K-A*i)//B
        ans = (ans + F[N]*R[j]%Q*R[N-j]%Q*F[N]*R[i]%Q*R[N-i]%Q)%Q
print(ans)

### FIXED CODE ###

Q = 998244353
def getInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

N, A, B, K = map( int, input().split())
ans = 0
invs = getInv(N)
nCk = [1]*(N+1)
for i in range(1,N+1):
    nCk[i] = (nCk[i-1]*(N-i+1)*invs[i])%Q
for i in range(N+1):
    j = (K-A*i)//B
    if A*i + B*j == K and j <= N and 0 <= j:
        j = (K-A*i)//B
        ans = (ans + nCk[i]*nCk[j])%Q
print(ans)
### BUGGY CODE ###

n,m,q = map(int, input().split())
List1 = [[0 for i in range(n)] for j in range(n)]
List2 = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
  l,r = map(int, input().split())
  List1[l - 1][r - 1] += 1

for i in range(n):
  for j in range(i, n):
    for k in range(i, j + 1):
      for l in range(k, j + 1):
        List2[i][j] += List1[k][l]


for i in range(q):
  a, b = map(int, input().split())
  print(List2[a - 1][b - 1])

### FIXED CODE ###

n,m,q = map(int, input().split())
List1 = [[0 for i in range(n+1)] for j in range(n+1)]
List2 = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
  l,r = map(int, input().split())
  List1[l - 1][r - 1] += 1


for i in range(n):
  for j in range(n - i):
    List2[j][j + i] = List2[j + 1][j + i] + List2[j][j + i - 1] - List2[j + 1][j + i - 1] + List1[j][j + i]


for i in range(q):
  a, b = map(int, input().split())
  print(List2[a - 1][b - 1])
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
        else:
            for l in range(ma-k):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]

for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()
### BUGGY CODE ###

#動的計画法
H, N = map(int, input().split())

A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, input().split())

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  min_power = min([DP[max(hp-A[i],0)]+B[i] for i in range(N)])
  return magic+min_power

DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')

### FIXED CODE ###

#動的計画法
import numpy as np
H, N = map(int, input().split())

A=np.empty(N,dtype=int)
B=np.empty(N,dtype=int)
for i in range(N):
    A[i],B[i]=map(int,list(input().split(" ")))

DP=np.empty(H+1,dtype=int)

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  t = hp-A
  t[t<0] = 0
  min_power = min(DP[t]+B)
  return magic+min_power

#DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')
### BUGGY CODE ###

from collections import defaultdict
from math import sqrt, floor
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def factorize(n):
    fct = defaultdict(int)
    m = floor(sqrt(n))+1
    for b in range(2,m):
        e = 0
        while n%b == 0:
            n = n // b
            e += 1
        if e > 0:
            fct[b] = e
    if n > 1:
        fct[n] = 1
    return fct
dct = defaultdict(int)
dctT = [0]*N
for i,a in enumerate(A):
    dctT[i] = factorize(a)
    for key in dct.keys() | dctT[i].keys():
        dct[key] = max(dct[key],dctT[i][key])
ans = 0
for i in range(N):
    t = 1
    for k,v in dct.items():
        t *= pow(k,v-dctT[i][k],M)
    ans += t%M
print(ans%M)

### FIXED CODE ###

from fractions import gcd
def lcm(a,b):
    return a*b // gcd(a,b)

N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
l = 1
for a in A:
    l = lcm(l,a)
ans = 0
for a in A:
    ans += l//a
print(ans%M)