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

N, K, C = map(int, input().split())
S = list(input())
countr = 0
countl = 0
switchr = 0
switchl = 0
left_greedy = [0]*len(S)
right_greedy=[0]*len(S)
#left
for l in range(len(S)):
    i = S[l]
    if switchl ==1:
        if i == 'o':
            if countl >= C:
                left_greedy[l]=1
                
                countl = 0
            else:
                countl+=1
               
        else:
            countl+=1
    else:
        if i == 'o':
            left_greedy[l]=1
            switchl+=1
#right_greedy
    r = len(S)-l-1
    i = S[r]
    if switchr ==1:
        if i == 'o':
            if countr >= C:
                right_greedy[r]=1
                
                countr = 0
            else:
                countr+=1
        else:
            countr+=1
            
    else:
        if i == 'o':
            right_greedy[r]=1
            switchr+=1
for i in range(len(S)):
    if S[i] ==  'o':
        l = left_greedy[0:i].count(1)
        r = right_greedy[i+1:len(S)].count(1)
        x = r+l
        if 1 in left_greedy[0:i][::-1]:
            if 1 in right_greedy[i+1:len(S)-1]:
                if left_greedy[0:i][::-1].index(1)+right_greedy[i+1:len(S)-1][::-1].index(1)+1 < C:
                    x+=-1
        if x < K:
            print(i+1)

### FIXED CODE ###

n,k,c = list(map(int,input().split()));s=[True if i=="o" else False for i in input()]
front=[0]*n;back=[0]*n;count=0
 
day = 0
while day < n:
    if s[day]:
        count += 1
        front[day]= 1
        day += c+1
    else:
        day += 1
    
s = s[::-1]
day = 0
while day < n:
    if s[day]:
        back[day]= 1
        day += c+1
    else:
        day += 1
back = back[::-1]
    
if count ==k:
    for i in range(n):
        if front[i] ==1 and back[i] == 1:
            print(i+1)
### BUGGY CODE ###

count = int(input())
num = list(map(int, input().split()))
ans = 1
breakFlag = False
for i in range(len(num)):
  ans = ans*num[i]
if ans > 1000000000000000000:
  ans = -1
print(ans)

### FIXED CODE ###

count = int(input())
A = list(map(int, input().split()))
ans = 1
for i in A:
  if i==0:
    print(0)
    exit()
    
for i in range(len(A)):
  ans = ans*A[i]
  if ans > 1000000000000000000:
    print(-1)
    exit()
    
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import bisect
q=int(input())
h=[]
l=0 #hの要素数
b=0 #bの和
s=0 #絶対偏差の和
med=0
for _ in range(q):
    Tmp=tuple(map(int,input().split()))
    if Tmp[0]==1:
        b+=Tmp[2]
        if l%2:
            s+=abs(Tmp[1]-med)
        else:
            if l:
                med_next=h[(l-1)//2+1]
                if Tmp[1]<=med:
                    s+=abs(Tmp[1]-med)
                elif Tmp[1]>=med_next:
                    s+=abs(Tmp[1]-med_next)
            else:
                med=Tmp[1]
        l+=1
        bisect.insort(h,Tmp[1])
        med=h[(l-1)//2]
    else:
        print(med,s+b)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from heapq import heappush,heappop
q=int(input())
_,a,b=map(int,input().split())
Small=[-a]; Large=[]
cnt=1
med=a
c=b
s=0
for i in range(q-1):
    query=tuple(map(int,input().split()))
    if query[0]==1:
        _,a,b=query
        c+=b
        if cnt%2:
            s+=abs(a-med)
            if a<-Small[0]:
                heappush(Small,-a)
                heappush(Large,-heappop(Small))
            else:
                heappush(Large,a)
        else:
            if a<=-Small[0]:
                heappush(Small,-a)
                med=-Small[0]
                s+=med-a
            elif a<=Large[0]:
                heappush(Small,-a)
            else:
                heappush(Large,a)
                med=heappop(Large)
                s+=a-med
                heappush(Small,-med)
        cnt+=1
        med=-Small[0]
    else:
        print(med,s+c)
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(int(stdin.readline().rstrip()) for _ in range(n))

for i in range(n-1):
    if max(li) == li[i]:
        print(sorted(li)[-2])
    else:
        print(max(li))
print(max(li[:n]))   

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_m = max(a)
a_i = a.index(a_m)
a.sort()
for i in range(len(a)):
  if i == a_i:
    print(a[-2])
  else:
    print(a_m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j != parent:
            val[j] += val[i]
            dps(j,i)
                
dps(0,0)
for i in val:
    print(i,end=" ")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,readline().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,readline().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)
### BUGGY CODE ###

from collections import deque
import copy
def bfs():
  H, W = map(int, input().split())
  maze = [list(input()) for i in range(H)]
  S = []
  for i in range(H):
    for j in range(W):
      if maze[i][j] == ".":
        maze[i][j] = float("inf")
        S.append([i, j])
      else:
        maze[i][j] = -1
  ans = 0
  for sy, sx in S:
    maze1 = copy.deepcopy(maze)
    maze1[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs()

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

cache={}
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif (n,W) in cache:
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
    else:
      cache[(n,W)]=dp(n-1,W,w,p)
    return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit))

### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
### BUGGY CODE ###

n,m=map(int, input().split())
ab=[]
for _ in range(n):
    tmpa, tmpb=map(int, input().split())
    ab.append((tmpa,tmpb))
    
import heapq
ans=0
h=[]
for d in range(m-1, -1, -1):
    for v in ab:
        if v[0]<=m-d:
            heapq.heappush(h, v[1]*(-1)) 
    ab=[v for v in ab if v[0]>m-d]
    try:
        ans-=heapq.heappop(h)
    except IndexError:
        ans+=0
print(ans)

### FIXED CODE ###

n,m=map(int, input().split())
ab=[]
for _ in range(n):
    tmpa, tmpb=map(int, input().split())
    ab.append((tmpa,tmpb))
ab.sort(reverse=True)
import heapq
h = []
ans = 0
for i in range(1, m+1):
    while ab and ab[-1][0] == i:
        heapq.heappush(h,ab.pop()[1]*(-1))
    if h:
        ans -= heapq.heappop(h)
print(ans)
### BUGGY CODE ###

import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+N0
  lm=(L//(L&-L))>>1
  rm=(R//(R&-R))>>1
  while L<R:
    if R<=rm:
      yield R
    if L<=lm:
      yield L
    L>>=1;R>>=1
  while L:
    yield L
    L>>=1

def propagates(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=10**9+1
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

x=[]
for i in range(n):
  x.append(l[i][0])
  update(i,i+1,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p,p+1)
  update(p,Right[p],-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  p=min(p+1,n-1)
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

data0=[0]*(n+1)
data1=[0]*(n+1)

def _add(data,k,x):
  while k<=n:
    data[k]+=x
    k+=k&-k

def add(l,r,x):
  _add(data0,l,-x*(l-1))
  _add(data0,r,x*(r-1))
  _add(data1,l,x)
  _add(data1,r,-x)

def _get(data,k):
  s=0
  while k:
    s+=data[k]
    k-=k&-k
  return s

def query(l,r):
  return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)

x=[]
for i in range(n):
  x.append(l[i][0])
  add(i+1,i+2,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p+1,p+2)
  add(p+1,Right[p]+1,-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  p=min(p+1,n-1)
  while query(p+1,p+2)<=0:
    p+=1
    if p==n:
      break
print(ans)
### BUGGY CODE ###

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

import numpy as np
a = np.zeros(N)

for _ in range(M):
    l, r = map(int, input().split())
    l-=1
    a[l:r] += 1

print(len(a[a==M]))


### FIXED CODE ###

N, M = map(int, input().split())
 
L, R = 0, N
for _ in range(M):
    l, r = map(int, input().split())
    l-=1
    r-=1
    L = max(l, L)
    R = min(r, R)

print(R-L+1 if R-L>=0 else 0)
### BUGGY CODE ###

import sys

H,W,M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]

hc = [0 for h in range(H)]
wc = [0 for w in range(W)]

for _ in range(M):
    h,w = map(int, input().split())
    h-=1
    w-=1
    grid[h][w] = 1
    hc[h] += 1
    wc[w] += 1

hmax = max(hc)
wmax = max(wc)

htable = []
for h in range(H):
    if hc[h] == hmax:
        htable.append(h)

wtable = []
for w in range(W):
    if wc[w] == wmax:
        wtable.append(w)

# print(uw, uh)
#print(grid)
#print(wc, uw)
#print(hc, uh)

found = False
for h in htable:
    for w in wtable:
        if grid[h][w] == 0:
            print(hmax + wmax)
            sys.exit(0)

print(hmax + wmax - 1)

### FIXED CODE ###

H,W,M = map(int, input().split())
# grid = [[0 for _ in range(W)] for _ in range(H)]
bombs = set()

hc = [0 for h in range(H)]
wc = [0 for w in range(W)]

for _ in range(M):
    h,w = map(int, input().split())
    h-=1
    w-=1
    bombs.add((h, w))
    hc[h] += 1
    wc[w] += 1

hmax = max(hc)
wmax = max(wc)

htable = []
for h in range(H):
    if hc[h] == hmax:
        htable.append(h)

wtable = []
for w in range(W):
    if wc[w] == wmax:
        wtable.append(w)

# print(uw, uh)
#print(grid)
#print(wc, uw)
#print(hc, uh)

found = False
for h in htable:
    for w in wtable:
        if (h,w) not in bombs:
            print(hmax + wmax)
            exit(0)

print(hmax + wmax - 1)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
Q = int(input())
result = 0
for i in a:
    result += i
for j in range(Q):
    b,c = map(int,input().split())
    while b in a:
        a[a.index(b)] = c
        result += c-b
    print(result)



### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
Q = int(input())
cnt = [0]*1000001
result = 0
for i in a:
    cnt[i] += 1
    result += i
for j in range(Q):
    b,c = map(int,input().split())
    cnt[c] += cnt[b]
    n = cnt[b]
    cnt[b] = 0
    result += (c-b)*n
    print(result)
### BUGGY CODE ###

enemy_num, dethblow_num, *enemy_hp = map(int, open(0).read().split())

if enemy_num >= dethblow_num:
    for i in range(dethblow_num):
        enemy_hp.remove(max(enemy_hp))
else:
    enemy_hp.clear()
    enemy_hp = [0]
    
print(sum(enemy_hp))

### FIXED CODE ###

enemy_num, dethblow_num, *enemy_hp = map(int, open(0).read().split())

if enemy_num >= dethblow_num:
    enemy_hp.sort(reverse=True)
    del enemy_hp[:dethblow_num]
else:
    enemy_hp.clear()
    enemy_hp = [0]
    
print(sum(enemy_hp))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        half = N // 2
        for length in range(1, half + 1)[::-1]:
            i = 0
            already = set()
            while i + length < N:
                v = S[i:i + length]
                if v in already:
                    i += 1
                    continue

                if S.count(S[i:i + length]) >= 2:
                    print(length)
                    exit()
                else:
                    already.add(v)
                    i += 1
        print(0)


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
        ans = 0
        for i in range(N)[::-1]:
            for j in range(N)[::-1]:
                if S[i] == S[j]:
                    dp[i][j] = min(dp[i + 1][j + 1] + 1, abs(i - j))
                    ans = max(ans, dp[i][j])
        print(ans)


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

s = input()
t = ''
for i in range(len(s)):
    if s[i]!='x':
        t += s[i]
for i in range(len(t)):
    if t[i]!=t[-1-i]:
        print(-1)
        break
else:
    ans = 0
    L = []
    R = []
    prevl = -1
    prevr = len(s)
    for i in range(len(s)):
        if s[i]!='x':
            L.append(i-prevl-1)
            prevl = i
        if s[-1-i]!='x':
            R.append(prevr-(len(s)-1-i)-1)
            prevr = len(s)-1-i
    L.append(len(s)-prevl-1)
    R.append(prevr)
    for i in range(len(L)):
        ans += abs(L[i]-R[i])
    print(ans//2)

### FIXED CODE ###

s = input()
t = ''
for i in range(len(s)):
    if s[i]!='x':
        t += s[i]
for i in range(len(t)):
    if t[i]!=t[-1-i]:
        print(-1)
        break
else:
    ans = 0
    L = []
    R = []
    prevl = -1
    prevr = len(s)
    for i in range(len(s)):
        if s[i]!='x':
            L.append(i-prevl-1)
            prevl = i
        if s[-1-i]!='x':
            R.append(prevr-(len(s)-1-i)-1)
            prevr = len(s)-1-i
    L.append(len(s)-prevl-1)
    R.append(prevr)
    for i in range(len(L)):
        ans += abs(L[i]-R[i])
    print(ans//2)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[0]*w for i in range(h)]
cnt,b=0,[]
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      b.append(deque([(i,j)]))
      visited[i][j]=1
    else:
      cnt+=1
ans=0
while cnt>0:
    ok=False
    for i in range(len(b)):
      if b[i]:
        c=[]
        while b[i]:
          x,y=b[i].popleft()
          c.append((x,y))
        for l,m in c:
          for j,k in ((0,1),(1,0),(-1,0),(0,-1)):
            newx,newy=l+j,m+k
            if 0<=newx<h and 0<=newy<w:
              if maze[newx][newy]!='#' and visited[newx][newy]!=1:
                visited[newx][newy]=1
                b[i].append((newx,newy))
                cnt-=1
                ok=True
    if ok:
      ans+=1
print(ans)

### FIXED CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

def lcm_base(x, y):
    return x // gcd(x, y) * y

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(N):
        ans += D // A[i]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce


def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    D %= MOD
    for a in A:
        ans += D * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


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

n=int(input())
s=[*input()]
q=int(input())
# BIT
B={chr(97+i):[0]*(n+1) for i in range(26)}
def bsum(c,i):
  s=0
  while i:
    s+=B[c][i]
    i-=i&-i
  return s
def badd(c,i,x):
  while i<=n:
    B[c][i]+=x
    i+=i&-i
for i,c in enumerate(s):
  badd(c,i+1,1)
for _ in range(q):
  x,y,z=input().split()
  y=int(y)-1
  if x=='1':
    badd(s[y],y+1,-1)
    s[y]=z
    badd(z,y+1,1)
  else:
    print(sum(bsum(c,int(z))-bsum(c,y)>0 for c in B))

### FIXED CODE ###

n=int(input())
l=list(input())
q=int(input())
bit=[[0]*(n+1) for i in range(26)]
def bit_sum(o,i):
  s=0
  while i:
    s+=bit[o][i]
    i-=i&-i
  return s
def bit_add(o,i,x):
  while i<=n:
    bit[o][i] += x
    i+=i&-i
for i in range(n):
  bit_add(ord(l[i])-97,i+1,1)
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    bit_add(ord(l[b])-97,b+1,-1)
    l[b]=c
    bit_add(ord(c)-97,b+1,1)
  else:
    c=int(c)
    print(sum(1 for o in range(26) if bit_sum(o,c)-bit_sum(o,b)))
### BUGGY CODE ###

import sys

def isprime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True

for line in sys.stdin:
	N = int(line)
	count = 0
	for x in range(2, N + 1):
		if isprime(x):
			count += 1
	print count

### FIXED CODE ###

import itertools
import sys

N = 999999
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] 
primeb = [0 for i in range(N+1)]
 
for i in primes:
  primeb[i] = 1
 
def isprime(n):
  for p in primes:
    if (n % p == 0):
      return True
    if (n < p*p):
      return False 
S = primes[-1]
for i in range(S, N):
  if isprime(i):
    pass 
  else: 
    primes.append(i)
    primeb[i] = 1

for line in sys.stdin:
  n = int(line)
  print sum(primeb[:n+1])
### BUGGY CODE ###

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

ok = a[-1]
ng = 0
while abs(ok - ng)>1:
    X = (ok + ng)//2
    
    cnt = 0
    for i in range(n):
        temp = a[-(i + 1)]
        if temp <= X:break
        temp_cnt = (temp + X - 1)//X - 1
        cnt += temp_cnt
    
    if cnt <= k:ok = X
    else:ng = X
    
print(ok)

### FIXED CODE ###

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

ok = a[-1]
ng = 0
while abs(ok - ng)>1:
    X = (ok + ng)//2
    
    cnt = 0
    for i in range(n):
        temp = a[-(i + 1)]
        if temp <= X:break
        temp_cnt = (temp + X - 1)//X - 1
        cnt += temp_cnt
    
    if cnt <= k:ok = X
    else:ng = X
    
print(ok)
### BUGGY CODE ###

import itertools

ans=0
n=int(input())
li=list(map(int,input().split()))
for i in range(1,n):
    k=list(itertools.accumulate(li[:i]))[-1]
    ans+=k*li[i]
print(ans%(10**9+7))

### FIXED CODE ###

import itertools
ans=0
n=int(input())
li=list(map(int,input().split()))
L=list(itertools.accumulate(li))
for i in range(1,n):
    ans+=L[i-1]*li[i]
print(ans%(10**9+7))