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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N,D,A = map(int,readline().split())
m = map(int,read().split())
XH = np.array(list(zip(m,m)), np.int64)
sortlist = np.argsort(XH[:,0])
XH = XH[sortlist]

ans = 0
while True:
	place = np.where(XH[:,1] > 0)
	if len(place[0]) == 0:
		break
	ind_cp = place[0][0]
	cp = XH[ind_cp,0]
	R = cp + (2*D)
	ind = np.searchsorted(XH[:,0],R, side='right')
	attack = -(-XH[ind_cp,1]//A)
	ans += attack
	XH[ind_cp:ind,1] -= attack*A

print(ans)


### FIXED CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

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

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

if P == 2 or P == 5:
    cnt = 0

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = ''
    for s in S[::-1]:
        num = s + num
        r = int(num) % P

        cnt += r_lst[r]

        r_lst[r] += 1


print(cnt)


### FIXED CODE ###

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

if P == 2 or P == 5:
    cnt = 0

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = 0

    for i, s in enumerate(S[::-1]):
        num  = (num + int(s) * pow(10, i, P)) % P
        cnt += r_lst[num]

        r_lst[num] += 1


print(cnt)
### BUGGY CODE ###


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

sumt = 0
cnt = 0
for i in range(N+M):
    sumt += ALLB.pop(0)
    if sumt > K:
        print(cnt)
        exit(0)
    cnt += 1

print(N+M)



### FIXED CODE ###

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

SumA = [0]
SumB = [0]
cnt = 0
for i in range(N):
    SumA.append(SumA[i] + A[i])
for i in range(M):
    SumB.append(SumB[i] + B[i])

for i in range(N+1):
    if SumA[i] > K:
        break
    tmpcnt = bisect.bisect_right(SumB, K - SumA[i]) - 1
    #print([SumA,SumB])
    #print(SumA[i])
    #print(K - SumA[i])
    #print(tmpcnt)
    #print([i,tmpcnt])
    cnt = max(cnt, i + tmpcnt)
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0

for i in range(n):
    p[i] = (p[i] + 1)/2
for j in range(n - k + 1):
    ev = sum(p[j:j + k])
    ans = max(ans,ev)
print(ans)



    


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(n):
    p[i] = (p[i] + 1)/2
ev = sum(p[:k])
if n == k:
    print(sum(p))
    exit()
for i in range(n - k):
    ev += (p[i + k] - p[i])
    ans = max(ans,ev)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
allsum = 0
sums_list = []
sums = 0
for i in range(N-1, 0, -1):
  sums = (sums + A[i]) % (10**9 + 7)
  sums_list.insert(0, sums)
for i in range(N-1):
  allsum = (allsum + A[i] * sums_list[i]) % (10**9 + 7)
print(allsum)

### FIXED CODE ###

from collections import deque

N = int(input())
A = list(map(int,input().split()))
allsum = 0
sums_list = deque()
sums = 0
for i in range(N-1, 0, -1):
  sums = (sums + A[i]) % (10**9 + 7)
  sums_list.appendleft(sums)
for i in range(N-1):
  allsum = (allsum + A[i] * sums_list[i]) % (10**9 + 7)
print(allsum)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]
    for i, ti in enumerate(t):
        for j, sj in enumerate(s):
            if sj == ti:
                dp[i + 1][j + 1] = 1 + dp[i][j]
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(selected))


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())
### BUGGY CODE ###

from statistics import median
N = int(input())
AList = list(map(int, input().split()))

L = []
m = 0
for j in range(1, N+1):
    L.append(AList[j-1] - j)
    m = median(L)

p = 0
for j in range(1, N+1):
    p += abs(AList[j-1] - j - m)

print(int(p))


### FIXED CODE ###

from statistics import median
N = int(input())
AList = list(map(int, input().split()))
 
L = []
m = 0
for j in range(1, N+1):
    L.append(AList[j-1] - j)
m = median(L)
 
p = 0
for j in range(1, N+1):
    p += abs(AList[j-1] - j - m)
 
print(int(p))
### BUGGY CODE ###

from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for i, (dy, dx) in enumerate(zip(ddy, ddx)):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque, defaultdict
import sys
input=sys.stdin.readline


def solve():
    H, W, K = map(int, input().split())
    y1, x1, y2, x2 = map(int, input().split())
    l = [[1 if s=="@" else 0 for s in input()] for _ in range(H)]
    INF = 10**12

    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    ddy = [0, 0, -1, 1]
    ddx = [-1, 1, 0, 0]

    dist = defaultdict(lambda :INF)
    dist[(y1, x1)] = 0
    q = deque([(y1, x1)])

    while q:
        y, x = q.popleft()
        for dy, dx in zip(ddy, ddx):
            for j in range(1, K+1):
                if not (0<=y+dy*j<H and 0<=x+dx*j<W):
                    break
                if l[y+dy*j][x+dx*j]:
                    break

                if dist[(y+dy*j, x+dx*j)] > dist[(y, x)] + 1:
                    dist[(y+dy*j, x+dx*j)] = dist[(y, x)] + 1
                    q.append((y+dy*j, x+dx*j))
                elif dist[(y+dy*j, x+dx*j)] == dist[(y, x)] + 1:
                    continue
                else:
                    break


    ans = dist[(y2, x2)]
    print(ans if ans!=INF else -1)


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

n,q=map(int,input().split())
S=input()
L = []
for i in range(n-1):
    if S[i:i+2]=='AC':
        L.append(i)

for j in range(q):
    c=0
    s,e=map(int,input().split())
    for n in L:
        if s-1<=n<=e-2:
            c+=1
    print(c)

### FIXED CODE ###

n,q=map(int,input().split())
S=input()
L=[0]
c=0
for i in range(n-1):
    if S[i:i+2]=='AC':
        c+=1    
    L.append(c)
for j in range(q):
    s,e=map(int,input().split())
    print(L[e-1]-L[s-1])
### BUGGY CODE ###

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

buff = []
a = []
for i in range(N):
    _a, _b = list(map(int, input().split()))
    buff += [_a]*_b


buff = sorted(buff)
print(buff[K-1])



### FIXED CODE ###

amax = 100000
cnt = [0 for i in range(amax+1)]


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

for i in range(N):
    a, b = list(map(int, input().split()))
    cnt[a] += b


for ans in range(1, amax+1):
    if K <= cnt[ans]:
        print(ans)
        break
    K -= cnt[ans]
### BUGGY CODE ###

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


def prime_factorize(n):
    r = set()
    if n % 2 == 0:
        r.add(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return collections.Counter(r)


a1 = collections.Counter([])
a2 = collections.Counter(prime_factorize(A[0]))
for a in A:
    tmp = prime_factorize(a)
    a1 += tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif a1.most_common()[0][1] >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')

### FIXED CODE ###

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


def prime_factorize(n):
    r = set()
    while n % 2 == 0:
        r.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return r


j = 0
a1 = set()
a2 = prime_factorize(A[0])
for a in A[1:]:
    tmp = prime_factorize(a)
    if a1 & tmp:
        j = 1
    a1 |= tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif j:
    print('setwise coprime')
else:
    print('pairwise coprime')
### 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()))


scores = []
for a in A:
    for b in B:
        for c in C:
            score = a + b + c
            scores.append(score)

scores.sort(reverse=True)

for i in range(K):
    print(scores[i])


### FIXED CODE ###

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


scores = []
for a in range(len(A)):
    for b in range(len(B)):
        if (a + 1) * (b + 1) > K:
            break
        for c in range(len(C)):
            if (a + 1) * (b + 1) * (c + 1) > K:
                break
            score = A[a] + B[b] + C[c]
            scores.append(score)

scores.sort(reverse=True)

for i in range(K):
    print(scores[i])
### BUGGY CODE ###

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

ans=0
for i in set(a):
	x = a.count(i)
	if x-i>=0:
		ans += x-i
	else:
		ans += x
print(ans)


### FIXED CODE ###

N = int(input())
a = map(int,input().split())
dic={}

ans=0
for i in a:
	dic.setdefault(i,0)
	dic[i]+=1
for a,b in dic.items():	
	if b-a>=0:
		ans += b-a
	else:
		ans += b
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
count = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if  (h + w) % 2 == 0: 
            count += 1
print(count)

### FIXED CODE ###

H, W = map(int, input().split())
count = H * W // 2
if H % 2 == 1 and W % 2 == 1 :
    count +=1
if H == 1 or W == 1:
    count = 1
print(count)
### BUGGY CODE ###

import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(_) for _ in comb]  
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

N = int(input())

a = [i for i in range(1, N+1)]
p = a.copy()
p = p[1:] + [p[0]]

print(sum([ai%pi for ai, pi in zip(a, p)]))


### FIXED CODE ###

N = int(input())

print((N-1) * N // 2)
### BUGGY CODE ###

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

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


dp   = [0]*(N+1)
dp[0] = 1

for i in range(0, N, 1):

    if i+1 == 1 and not (i+1) in A:
        dp[i+1] = dp[i]
    elif not (i+1 in A) and not(i in A) and not(i-1 in A):
        dp[i+1] = dp[i] + dp[i-1] 
    elif not(i+1 in A) and not (i in A) and (i-1 in A):
        dp[i+1] = dp[i]
    elif not(i+1 in A) and (i in A) and not(i-1 in A):
        dp[i+1] = dp[i-1] 

print(dp[N]%1000000007)


### FIXED CODE ###

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

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

dp = [0]*(N+3)



for i in range(N+1):

    if i==0:
        if not (i+1) in A:
            dp[i+1] = 1 + dp[i]
        if not (i+2) in A:
            dp[i+2] = 1 + dp[i]
        continue 
    if not i+1 in A:
        dp[i+1] = dp[i] + dp[i+1]
    if not i+2 in A:
        dp[i+2] = dp[i] + dp[i+2]

print(dp[N]%(1000000007))
### BUGGY CODE ###

length = list(map(int,input().split()))	
string = input()
l_r = [list(map(int,input().split())) for i in range(length[1])]
answer = []

for i in range(length[1]):
  part_str = list(string[(l_r[i][0]-1):l_r[i][1]])
  for n in range(len(part_str)):
    answer.append(0)
    if part_str[n]=='A':
      if n != (len(part_str)-1):
        if part_str[n+1]=='C':
          answer[i] += 1
  print(answer[i])
          

### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
ans = ''
a = [0]
count = 0
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    ans += '1'
  else:
    ans += '0'
  if i == N - 2:
    ans += '0'
else:
  for i in range(N):
    if ans[i] == '1':
      count += 1
      a.append(count)
    else:
      a.append(count)
  else:
    for i in range(Q):
      l = lr[i][0]
      r = lr[i][1]
      print(a[r-1]-a[l-1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
lr=[]
for _ in range(q):
  l,r=map(int,input().split())
  lr.append([l,r])
  
loc=[0]*n
for i in range(n-1):
  if s[i]=='A' and s[i+1]=='C':
    loc[i]=1
for i in range(q):
  l=lr[i][0]
  r=lr[i][1]
  print(sum(loc[l-1:r-1]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[]
for _ in range(q):
  l,r=map(int,input().split())
  lr.append([l,r])

t=[0]*n
for i in range(n-1):
  if s[i:i+2]=='AC':
    t[i+1]=t[i]+1
  else:
    t[i+1]=t[i]
for i in range(q):
  l=lr[i][0]
  r=lr[i][1]
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    if dfs(K):
        print('First')
    else:
        print('Second')
@lru_cache(maxsize=None)
def dfs(n):
    if n < a[0]:
        return False
    for i in a:
        if not dfs(n-i):
            return True
    return False

main()


### FIXED CODE ###

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

def main():
    l = [False] * (K+1)
    for i in range(a[0] -1, K+1):
        l[i] = any(not l[i-j] if i >= j else False for j in a)
    if l[-1]:
        print('First')
    else:
        print('Second')


main()
### BUGGY CODE ###

N = int(input())
s = [''.join(sorted(list(input()))) for _ in range(N)]
flag = [False] * N
ans = 0
for i in range(N - 1):
    if flag[i]:
        continue
    flag[i] = True
    cnt = 0
    for j in range(i + 1, N):
        if s[i] == s[j]:
            flag[j] = True
            cnt += 1
    ans += sum([n for n in range(cnt, 0, -1)])

print(ans)
    

### FIXED CODE ###

N = int(input())
cnt_dict = dict()

for _ in range(N):
    s = ''.join(sorted(list(input())))
    if s in cnt_dict:
        cnt_dict[s] += 1
    else:
        cnt_dict[s] = 1

ans = 0
for cnt in cnt_dict.values():
    ans += cnt * (cnt - 1) // 2

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

def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y
 
N, M, X = map(int, input().split())
price = -1
 
L = []
a = []
c = []
suit =[]
for i in range(M+1):
    a.append(0)
    
for i in range(N):
    text = input().split()
    L.append(intlist(text))
 
def buy(x,y):
    
    if x + y <= N:
        
        for i in range(0,M+1):
            
            a[i] += L[x+y-1][i]
            
       
        if x + y == N:
            score = a[1:len(a)]
            
            if min(score) >= X:
                suit.append(a.copy())
                
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
           
            notbuy(x,y+1)
 
 
def notbuy(x,y):
   
    if x + y <= N:
        
        if x + y == N:
            score = a[1:len(a)]
            if min(score) >= X:
                suit.append(a.copy())
                    
             
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
            notbuy(x,y+1)    
 
def textbook(x,y):
    buy(x+1,y)
    for i in range(0,M+1):
        a[i] -= L[x+y][i]
    notbuy(x,y+1)
 
textbook(0,0)
 
b = []
 
if suit != []:
    for i in range(len(suit)):
        for j in range(len(suit)-1):
            if suit[j] > suit[j+1]:
                b = suit[j]
                suit[j] = suit[j+1]
                suit[j+1] = b
    price = suit[0][0]
 

print(price)


### FIXED CODE ###

def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y
 
N, M, X = map(int, input().split())
price = -1
 
L = []
a = []
c = []
suit =[]
for i in range(M+1):
    a.append(0)
    
for i in range(N):
    text = input().split()
    L.append(intlist(text))
 
def buy(x,y):
    
    if x + y <= N:
        
        for i in range(0,M+1):
            
            a[i] += L[x+y-1][i]
            
       
        if x + y == N:
            score = a[1:len(a)]
            
            if min(score) >= X:
                suit.append(a.copy())
                
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
           
            notbuy(x,y+1)
 
 
def notbuy(x,y):
   
    if x + y <= N:
        
        if x + y == N:
            score = a[1:len(a)]
            if min(score) >= X:
                suit.append(a.copy())
                    
             
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
            notbuy(x,y+1)    
 
def textbook(x,y):
    buy(x+1,y)
    for i in range(0,M+1):
        a[i] -= L[x+y][i]
    notbuy(x,y+1)
 
textbook(0,0)
 



if suit != []:
    if len(suit) >= 2:
    
        cheaper = suit[0][0]
        for i in range(len(suit)):
            if cheaper > suit[i][0]:
                cheaper = suit[i][0]
        price = cheaper
    elif len(suit) == 1:
        price = suit[0][0]
 


print(price)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(0, len(s)-3):
  for j in range(i+3, len(s)):
    if int(s[i:j+1]) % 2019 == 0:
      ans += 1
      j += 3
print(ans)

### FIXED CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
answer = 1
for _ in A:
    answer = answer * _

if answer > 1000000000000000000:
    print('-1') 
else:
    print(answer)

### FIXED CODE ###

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

if A.count(0) >= 1:
    print(0)
    exit()

answer = 1
for _ in A:
    answer *= _
    if answer > 1000000000000000000:
        print('-1') 
        exit()

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

N=input()
s=input()

N=int(N)
score=[]
bn=[]
a=0

if(s[N-1]=="."):
    a+=1
    bn.insert(0,a)
else:
    bn.insert(0,0)

for i in range(1,N):
    j=N-1-i
    if(s[j]=="."):
        a+=1
    bn.insert(0,a)
bn.append(0)
#print(bn)

#score算出
a=0
for i in range(N):
    now=bn[i]
    now+=a
    score.append(now)
    if(s[i]=="#"):
        a+=1
score.append(a)

score.sort()
print(score[0])

### FIXED CODE ###

N=input()
s=input()

N=int(N)
wn=[]
bn=[]
a=0
b=0

#各行間よりも前と後ろに何個白（黒）があるかをカウント
wn.append(0)
for i in range(N):
    j=N-(i+1)
    if(s[j]=="."):
        a+=1
    if(s[i]=="#"):
        b+=1
    bn.append(a)
    wn.append(b)

bn.reverse()
bn.append(0)
#print(bn)
#print(wn)

#各行間のscore算出
min=1000000
for i in range(N+1):
    score=bn[i]+wn[i]
    if(score<min):
        min=score

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

N = int(input())
min = 10**12
for i in range(1,N+1,1):
    for j in range(i,N+1,1):
        ans = i * j
        if ans > N:
            break
        else:
            if ans == N:
                if min >= (i + j - 2):
                    min = i + j - 2
print(min)  

### FIXED CODE ###

N = int(input())
lst = []

for i in range(1,int(N**0.5)+1,1):
  if N % i == 0:
    lst.append(int(i + N/i - 2))
print(min(lst))
### BUGGY CODE ###

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

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
T = [0]*(N+1)
for i in range(N):
    T[i+1] = T[i]+ (1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(T[r-1]-T[l-1])