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

def solve_panasonic2020_e():
    from itertools import islice, permutations, zip_longest

    def cv2num(c):
        return -1 if c == '?' else ord(c)

    *a, = map(cv2num, input())
    *b, = map(cv2num, input())
    *c, = map(cv2num, input())

    abc = a, b, c

    ret = sum(map(len, abc))
    for perm in permutations(abc):
        first, second, third = perm

        cands = [first + second]
        for i in range(len(first)):
            # first[i:]とsecondが一致するか見る
            # 一致なら候補に残す
            # すべてダメならfirst+secondだけ候補になる(重なりなし)
            cand = []
            for fc, sc in zip_longest(islice(first, i, len(first)), second, fillvalue=0):
                if not (fc and sc):
                    cand.append(fc + sc)
                elif fc == sc or sc == -1:
                    cand.append(fc)
                elif fc == -1:
                    cand.append(sc)
                else:
                    break
            else:
                cand = first[:i] + cand
                cands.append(cand)

        for cand in cands:
            for i in range(len(cand)):
                t = i
                for cc, tc in zip_longest(islice(cand, i, len(cand)), third, fillvalue=0):
                    t += 1
                    if not (cc and tc):
                        continue
                    if not (cc == tc or cc == -1 or tc == -1):
                        break

                else:
                    ret = min(ret, t)

    print(ret)


if __name__ == '__main__':
    solve_panasonic2020_e()


### FIXED CODE ###

# 解説の写経

def solve_panasonic2020_e():
    def unmatched(c1: str, c2: str) -> bool:
        """c1,c2がマッチしない"""
        return not (c1 == '?' or c2 == '?' or c1 == c2)

    A = input()
    B = input()
    C = input()

    MX = max(map(len, [A, B, C]))

    # 相対位置ごとの文字列マッチングの可否を調べる
    # ab/ac/bc[index差]:=その相対位置でマッチしないときTrue
    # [-MX,MX]
    # + : 左文字より右文字が右にある, a->b
    # - : 右文字より左文字が右にある, b->a
    ab = [False] * (MX * 4 + 1)
    ac = [False] * (MX * 4 + 1)
    bc = [False] * (MX * 4 + 1)

    for i, a in enumerate(A):
        for j, b in enumerate(B):
            ab[i - j] |= unmatched(a, b)

    for i, a in enumerate(A):
        for j, c in enumerate(C):
            ac[i - j] |= unmatched(a, c)

    for i, b in enumerate(B):
        for j, c in enumerate(C):
            bc[i - j] |= unmatched(b, c)

    # Aに対するB,Cの相対位置MX**2で全探索
    ans = sum(map(len, [A, B, C]))
    for i in range(-MX * 2, MX * 2 + 1):  # ACBのようにAB間にMX分空くこともあって、幅2MX
        if ab[i]: continue
        for j in range(-MX * 2, MX * 2 + 1):  # ABCのようにAC間にMX分空くこともあって、幅2MX
            if ac[j]: continue
            if bc[j - i]: continue
            # 添え字で混乱するが
            # ab[i-j]で
            # 添え字i-jは(bの開始)-(aの開始)を意味したことから
            # (i-j>0でa->bの配置から)
            # 今回i,jは(aの開始)を基準にした(b,cの開始位置)で
            # bcの添え字は(cの開始)-(bの開始)なのでj-i

            # [L,R)
            L = min(0, i, j)
            R = max(len(A), i + len(B), j + len(C))
            ans = min(ans, R - L)

    print(ans)
    return


if __name__ == '__main__':
    solve_panasonic2020_e()

# N**3は通らない
# N**2の方針=2本の文字列の捜査
### BUGGY CODE ###

import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    count=np.zeros(2019,dtype=int)
    temp=set([])
    ans=0
    for i in range(len(s)):
        count_t=np.zeros(2019,dtype=int)
        count_t[int(s[i])]+=1
        for k in range(2019):
            t=(k*10+int(s[i]))%2019
            count_t[k]-=count[k]
            count_t[t]+=count[k]
            if t==0:
                ans+=count[k]
        #print(count[0:20])
        #print(count_t[0:20])
        count=count+count_t
    print(ans)
                
if __name__ == '__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    cnt=[0]*2019
    cnt[0]=1
    temp=0
    keta=1
    ans=0
    for i in s[::-1]:
        temp=(temp+int(i)*keta)%2019
        keta=(keta*10)%2019
        cnt[temp]+=1
    for i in cnt:
        ans+=(i*(i-1))//2
    print(ans)
    
    
if __name__ == '__main__':
    do()
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_left(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


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

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

#!/usr/bin/env python3

def solve(n,k,q,a):
    l = [(k+a.count(i+1)-q)>0 for i in range(n)] 
    return l


def main():
    N,K,Q = map(int,input().split())
    a = [int(input()) for _ in range(Q)]
    L = solve(N,K,Q,a)
    for i in range(N):
        print("Yes" if L[i] else "No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter


def main():
    N,K,Q = map(int,input().split())
    a = [int(input()) for _ in range(Q)]
    d = Counter(a)
    L = [(K+d[i+1]-Q)>0 for i in range(N)] 
    for i in range(N):
        print("Yes" if L[i] else "No")

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

import numpy as np

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

while len(C) > 0:
  tmp_max = np.argmax(np.array(C))
  takahashi += A[tmp_max]
  A.pop(tmp_max)
  B.pop(tmp_max)
  C.pop(tmp_max)

  if len(C)>0 :
    tmp_max = np.argmax(np.array(C))
    aoki += B[tmp_max]
    A.pop(tmp_max)
    B.pop(tmp_max)
    C.pop(tmp_max)

print(takahashi-aoki)

### FIXED CODE ###

#%%
import time

import numpy as np

N = int(input())
A = [0] * N
B = [0] * N
C = [[] for _ in range(N) ]
takahashi = []
aoki = []

start = time.time()

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


D = np.array(A) + np.array(B)
for i in range(N):
  C[i] = [i, D[i]]


elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
start = time.time()

C = sorted(C, key=lambda x:x[1])


elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
start = time.time()


if N %2 == 0 :
  for i in range(1,N,2):
    tmp_max = C[-i][0]
    takahashi.append(A[tmp_max])
    tmp_max = C[-i-1][0]
    aoki.append(B[tmp_max])

elif N %2 != 0 :
  for i in range(1,N-1,2):
    tmp_max = C[-i][0]
    takahashi.append(A[tmp_max])
    tmp_max = C[-i-1][0]
    aoki.append(B[tmp_max])
  tmp_max = C[-N][0]
  takahashi.append(A[tmp_max])

print(sum(takahashi)-sum(aoki))

elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
### BUGGY CODE ###

def Lucas(L):
    if L == 0:
        return 2
    elif L == 1:
        return 1
    else: return Lucas(L-1)+ Lucas(L-2)

N = int(input())
print(Lucas(N))

### FIXED CODE ###

ans = [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,\
       15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, \
       4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324, 228826127, \
       370248451, 599074578, 969323029, 1568397607, 2537720636, 4106118243, 6643838879, 10749957122, \
       17393796001, 28143753123, 45537549124, 73681302247, 119218851371, 192900153618, 312119004989, \
       505019158607, 817138163596, 1322157322203, 2139295485799, 3461452808002, 5600748293801, \
       9062201101803, 14662949395604, 23725150497407, 38388099893011, 62113250390418, 100501350283429, \
       162614600673847, 263115950957276, 425730551631123, 688846502588399, 1114577054219522, \
       1803423556807921, 2918000611027443, 4721424167835364, 7639424778862807, 12360848946698171, \
       20000273725560978, 32361122672259149, 52361396397820127, 84722519070079276, 137083915467899403, \
       221806434537978679, 358890350005878082, 580696784543856761, 939587134549734843, 1520283919093591604]

N = int(input())
print(ans[N])
### BUGGY CODE ###

L, R = map(int, input().split())
print (min([((i % 2019) * (j % 2019)) % 2019 for i in range(L,R) for j in range(i+1,R+1)]))

### FIXED CODE ###

L, R = map(int, input().split())
if R-L >= 2019:
  print (0)
else:
  print (min([((i % 2019) * (j % 2019)) % 2019 for i in range(L,R) for j in range(i+1,R+1)]))
### BUGGY CODE ###

N = int(input())
S = input()

ans = N

for i in range(N+1):
    whiteprint = S[0:i].count("#")
    blackprint = S[i:N].count(".")

    ans = min(ans,blackprint + whiteprint)

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = S.count(".")

printnum = ans

for c in S:
    if c == ".":
        printnum -= 1
    else:
        printnum += 1
    ans = min(ans,printnum)

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

N = int(input())

def F(A, B):
    return max(len(str(A)), len(str(B)))

ans = 1000000000
for A in range(1, N+1):
    if N%A == 0:
        B = int(N / A)
        if F(A, B) < ans:
            ans = F(A, B)

print(ans)

### FIXED CODE ###

N = int(input())

def F(A, B):
    return max(len(str(A)), len(str(B)))

ans = 1000000000
half = int((N+1)**(1/2) + 1)
for A in range(1, half):
    if N%A == 0:
        B = int(N / A)
        if F(A, B) < ans:
            ans = F(A, B)

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

S=input()
T=input()
X=0
for s in S:
    if ord(s)>96:X+=1;S=S.replace(s,chr(X+47))
Y=0
for t in T:
    if ord(t)>96:Y+=1;T=T.replace(t,chr(Y+47))
print('Yes'if S==T else'No')

### FIXED CODE ###

S=input()
T=input()
X=0
for i in range(len(S)):
    s=S[i]
    if ord(s)>96:
        X+=1
        S=S.replace(s,chr(X+47))
Y=0
for i in range(len(T)):
    t=T[i]
    if ord(t)>96:
        Y+=1
        T=T.replace(t,chr(Y+47))
print('Yes'if S==T else'No')
### BUGGY CODE ###

n , m = map(int, raw_input().split())

ct = 0
ans = 0
while m != 0:
        m -= 1
        ct += 1
        if ct == 2 and n > 0:
                n -= 1
                ans += 1
                ct = 0
        elif ct == 4:
                ans += 1
                ct = 0

print ans

### FIXED CODE ###

n , m = map(int, raw_input().split())

tmp = m - (2 * n)
if tmp < 0:
        ans = m / 2
else:
        ans = 0
        ans += n
        ans += tmp / 4

print ans
### BUGGY CODE ###

# another sol
import heapq

def main():
    n, m = map(int, input().split())
    G = [[] for i in range(n+1)]
    Edge = []
    is_root = [True]*(n+1)
    
    for _ in range(n+m-1):
        x, y = map(int, input().split())
        G[x].append(y)
        Edge.append((x, y))
        is_root[y] = False

    #determine root
    root = -1
    for i in range(1, n+1):
        if is_root[i] == True:
            root = i
            break

    que = [(0, root)]
    heapq.heapify(que)
    #dijkstra
    dis = [0]*(n+1)
    while que:
        cost, node = heapq.heappop(que)
        if dis[node] < cost:continue        
        for c in G[node]:
            if dis[c] > cost - 1:
                dis[c] = cost - 1
                heapq.heappush(que,(cost - 1, c))

    par = [0]*(n+1)

    for x, y in Edge:
        if dis[y] + 1 == dis[x]:
            par[y] = x

    for i in range(1, n+1):
        print(par[i])

    return


if __name__ == "__main__":
    main()




### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# restore the tree


from collections import deque
n, m = map(int, input().split())


in_node = [0 for i in range(n + 1)]

# in_node[x]=xに入るノードの数

parent_node = [0 for i in range(n + 1)]

# parent[i]=ねつき木における頂点iの親を返す

in_graph = {i: [] for i in range(1, n + 1)}

out_graph = {i: [] for i in range(1, n + 1)}

# graph[i]=頂点iに入るノードの集合リスト

# out_graph[i]=頂点iから出るノードの集合リスト

for _ in range(n + m - 1):
    a, b = map(int, input().split())
    in_graph[b].append(a)
    out_graph[a].append(b)
    in_node[b] += 1

root = -1


for i in range(1, n + 1):
    if in_node[i] == 0:
        parent = i
        break



flag = True
d = deque()
d.append(parent)
while d:
    x = d.popleft()
    not_yet = False
    for node in out_graph[x]:
        in_node[node] -= 1
        if in_node[node] == 0 and parent_node[node] == 0:
            parent_node[node] = x
            d.append(node)
            not_yet = True

    if not_yet:
        flag = True
    else:
        flag = False

for i in range(1,n+1):
    print(parent_node[i])
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))
for x in range(Q):
    s_tmp = S[l[x] - 1:r[x]]
    countAC = 0
    flag_A = False
    for y in range(len(s_tmp)):
        if flag_A and s_tmp[y] == 'C':
            countAC += 1
        if s_tmp[y] == 'A':
            flag_A = True
        else:
            flag_A = False
    print(countAC)


### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = input()
l = [0] * Q
r = [0] * Q
for x in range(Q):
    l[x], r[x] = list(map(int, input().split()))

countAC = [0] * len(S)
for x in range(len(S) - 1):
    countAC[x + 1] = countAC[x]
    if S[x] == "A" and S[x + 1] == "C":
        countAC[x + 1] += 1
for x in range(Q):
    print(countAC[r[x] - 1] - countAC[l[x] - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
setA = set()
water = [0]*n
dams = [0]*n
cur = min(a[0],a[-1])
water[0]=2*min(a[0],a[-1])
dams[0]=cur
i = n-1
while(1):
    if i==0:
        if dams[0]+cur== a[0]:
            break
        else:
            water[0]-=2
            dams[0]=water[0]//2
            cur = dams[0]
            i=n-1
    else:
        need = a[i]-cur
        water[i]= need*2
        cur=need
        i-=1
print(*water)






### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
switch =1
s = 0
ans = [0]*n
for v in a:
    s+= 2*v*switch
    switch*=-1
x=s//2
ans[-1]=x//2
for i in range(n-1,0,-1):
    need = (a[i]-ans[i])*2
    ans[i]=need
    ans[i-1]=need//2
ans[0]= x
print(*ans)
### BUGGY CODE ###

x,y,z,k = list(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)
li = []
for i in a:
    for j in b:
        li.append(i + j) 
li.sort(reverse = True)
li = li[:min(k,x*y)]
box = []
for i in li:
    for j in c:
        box.append(i + j)
box.sort(reverse = True)
for i in range(k):
    print(box[i])

### FIXED CODE ###

x,y,z,k = list(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)
li = []
box = []
for i in a:
    for j in b:
        li.append(i + j) 
li.sort(reverse = True)
li = li[:min(k,x*y)]
for i in c:
    for j in li:
        box.append(i + j)
box.sort(reverse = True)
for i in range(k):
    print(box[i])
### BUGGY CODE ###

n,m = map(int,input().split())
stair = []
mod = int(1e9+7)
ans = 1
for i in range(m):
    stair.append(int(input()))
dp = [0] * (n+1)
dp[0] = dp[1] = 1
if 1 in stair:
    dp[1] = 0
if n == 1:
    print(1)
    exit()
for i in range(2, n+1):
    if i in stair:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[-1])





### FIXED CODE ###

n,m = map(int,input().split())
stair = []
mod = int(1e9+7)
ans = 1
for i in range(m):
    stair.append(int(input()))
dp = [0] * (n+1)
dp[0] = dp[1] = 1
stair.append(int(1e10))
if n == 1:
    print(1)
    exit()
k = 0
for i in range(1, n+1):
    if i == stair[k]:
        dp[i] = 0
        k += 1
    elif i == 1:
        dp[1] = 1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[-1])
### BUGGY CODE ###

import numpy as np

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

mod = 998244353

d = np.zeros(K+1)
d[0] = M

for _ in range(N-1):
    d[1:] = (d[:-1] + d[1:] * (M-1)) % mod
    d[0] = (d[0] * (M-1))  % mod

print(int(sum(d) % mod))

### FIXED CODE ###

N, M, K = list(map(int, input().split()))
mod = 998244353

c = 1
answer = 0

for i in range(K+1):
    answer += (M * c  * pow(M-1, N - i - 1, mod)) % mod
    answer %= mod
    c = (c * (N-i-1) * pow(i+1, mod-2, mod)) % mod
    
print(answer)
### BUGGY CODE ###

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

for i in a:
    ans *= i

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if 0 in a:
  	ans = 0
else:
    for i in a:
        ans *= i
        if ans > 10**18:
            ans = -1
            break
  
print(ans)
### BUGGY CODE ###

import numpy as np
inpl = lambda: list(map(int,input().split()))
H, W = inpl()
A = []
new_black = []
for h in range(H):
    line = list(input())
    A.append(line)
    blacks = np.where(np.array(line) == '#')[0]
    for w in blacks:
        new_black.append((h,w))
Nw = H*W - len(new_black)
t = 0
while Nw > 0:
    t += 1
    prev_black = new_black
    new_black = []
    for h, w in prev_black:
        for nh, nw in [(h+1,w), (h-1,w), (h,w+1), (h,w-1)]:
            if 0<=nh<H and 0<=nw<W and A[nh][nw] == '.':
                Nw -= 1
                A[nh][nw] = '#'
                new_black.append((nh,nw))
print(t)

### FIXED CODE ###

inpl = lambda: list(map(int,input().split()))
H, W = inpl()
A = []
new_black = []
Nb = 0
for h in range(H):
    line = input()
    Aline = [0] * W
    for w in range(W):
        if line[w] == '#':
            Aline[w] = 1
            new_black.append((h,w))
            Nb += 1
    A.append(Aline)
Nw = H*W - Nb
t = 0
while Nw > 0:
    t += 1
    prev_black = new_black
    new_black = []
    for h, w in prev_black:
        for nh, nw in [(h+1,w), (h-1,w), (h,w+1), (h,w-1)]:
            if 0<=nh<H and 0<=nw<W and A[nh][nw] == 0:
                Nw -= 1
                A[nh][nw] = 1
                new_black.append((nh,nw))
print(t)
### BUGGY CODE ###

s=input()
p=set()
ans=0
for c in s:
    ci=int(c)
    t=set()
    for i in p:
        i=(i*10+ci)%2019
        if i==0:
            ans+=1
        else:
            t.add(i)
    t.add(ci)
    p=t.copy()
print(ans)

### FIXED CODE ###

S=input()
MOD=2019
dp=[0]*MOD
dp[0]=1
r=0
t=1
for c in reversed(S):
    r+=int(c)*t
    r%=MOD
    t*=10
    t%=MOD
    dp[r]+=1
print(sum(i*(i-1)//2 for i in dp))
### BUGGY CODE ###

n = int(input())
count = 0

for i in range(1,n):
  for j in range(1,n):
    if(i*j < n):
      count += 1
      
print(count)

### FIXED CODE ###

n = int(input())
count = ((n-1) * 2) -1

for i in range(2,n):
  if(i*2 >= n):
    break
  for j in range(2,n):
    if(i*j < n):
      count += 1
    else:
      break
    
print(count)
### BUGGY CODE ###

X,K,D = map(int,input().split())
X = abs(X)
while(X > 0 and K > 0):
    K = K-1
    X = X-D
if K % 2 == 0:
    print(abs(X))
else:
    X = X+D
    print(X)

### FIXED CODE ###

X,K,D = map(int,input().split())
X = abs(X)
N = X//D
if N>K:
    N=K
X = X-N*D
K -= N
if K%2 == 0:
    print(X)
else:
    X -= D
    print(abs(X))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

N, M, Q = map(int, input().split())
L, R = [], []
X = [[0]*N for _ in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)
    X[l-1][r-1] += 1
C =[[0]*(N+1) for _ in range(N)]
for i in range(N):
    for j in range(N):
        C[i][j+1] = C[i][j] + X[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for j in range(p-1, q):
        ans += C[j][q] - C[j][p-1]
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, M, Q = map(int, input().split())
L, R = [], []
X = [[0]*N for _ in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)
    X[l-1][r-1] += 1
C =[[0]*(N+1) for _ in range(N)]
for i in range(N):
    for j in range(N):
        C[i][j+1] = C[i][j] + X[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for j in range(p-1, q):
        ans += C[j][q] - C[j][p-1]
    print(ans)
### BUGGY CODE ###

import itertools
import numpy as np

N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
combi = itertools.permutations(range(N),N)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for a in combi:
        x = sum(ca)[1:]
        fx = np.array([0]*M)
        c = sumcos
        for i in range(len(a)):
            x -= ca[a[i]][1:]
            c -= ca[a[i]][0]
            if sum(x>=X)<M:
                break
            else:
                cost = min(c,cost)
    print(cost)


### FIXED CODE ###

import itertools
import numpy as np
 
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for j in range(1,N+1):
        for a in itertools.combinations(range(1,N+1),j):       
            x = sum(ca)[1:]
            fx = np.array([0]*M)
            c = sumcos
            for i in range(len(a)):
                x -= ca[a[i]-1][1:]
                c -= ca[a[i]-1][0]
                if sum(x>=X)<M:
                    break
                else:
                    cost = min(c,cost)
    print(cost)
### 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())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))


### FIXED 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())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
import math

def gcd(a, b):
    if (a < b) :
        tmp = a
        a = b
        b = tmp
        
    r = a % b
    while (r != 0) :
        a = b
        b = r
        r = a % b
    return b

def lcm(a,b):
    temp = gcd(a,b)
    return temp * (a//temp) * (b//temp)




N = int(input())

A = tuple(map(int,input().split()))



koubai = int(1)
for i in range(N):
    koubai = lcm(koubai, A[i])

ans = int(0)
for i in range(N):
    ans += koubai // A[i]
    
ans %= 1000000007

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

print(ans)