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

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count * count > N : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

a, b, c = map(int, input().rstrip().split())
from decimal import *
getcontext().prec = 100000
if (Decimal(a).sqrt() + Decimal(b).sqrt()) < Decimal(c).sqrt():
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a, b, c = map(int, input().rstrip().split())
from decimal import *
getcontext().prec = 500
if (Decimal(a).sqrt() + Decimal(b).sqrt()) < Decimal(c).sqrt():
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import math

n, a, b = map(int, input().split(" "))

h = []
for i in range(n):
    h.append(int(input()))

h.sort(reverse=True)


def check(count_target, h, a, b):
    count = 0

    for i in h:
        if i >= count_target * b:
            count += math.ceil((i - count_target * b) / (a-b))
    return count_target - count


count = 1
while check(count, h, a, b) < 0:
    count *= 2

count /= 2
basis_count = count

while basis_count >= 1:

    if check(count + basis_count - 1, h, a, b) < 0:
        count += basis_count
    basis_count /= 2


while check(count,h,a,b) < 0:

    count += 1

print(int(count))


### FIXED CODE ###

import math

n, a, b = map(int, input().split(" "))

h = []
for i in range(n):
    h.append(int(input()))

h.sort(reverse=True)


def check(count_target, h, a, b):
    count = 0

    for i in h:
        if i >= count_target * b:
            count += math.ceil((i - count_target * b) / (a - b))
    return count_target - count


l = 1
r = math.ceil(h[0] / b)


while r - l > 1:
    mid = math.floor(l + (r - l) / 2)

    if check(mid, h, a, b) < 0:
        l = mid
    else:
        r = mid


if check(l, h, a, b) < 0:
    print(int(r))
else:
    print(int(l))
### BUGGY CODE ###

li = list(map(int,input().split()))
num = li[0]
want = li[1]
cost = []
max_num = []
total_num = 0
total_cost = 0
for i in range(num):
	a = list(map(int,input().split()))
	cost.append(a[0])
	max_num.append(a[1])
while want > total_num:
	min_cost = min(cost)
	m = cost.index(min_cost)
	if total_num + max_num[m] > want:
		total_cost += (want - total_num) * cost[m]
		total_num = want
	else:
		total_cost += max_num[m] * cost[m]
		total_num += max_num[m]
		cost.remove(cost[m])
		max_num.remove(max_num[m])
print(total_cost)

### FIXED CODE ###

n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(n)]
li = sorted(li, key=lambda x:x[0])
cnt = 0
coin = 0
for a,b in li:
    c_cnt = cnt + b
    if c_cnt < m:
        cnt += b
        coin += a*b
    else:
        cnt += b-(c_cnt - m)
        coin += a*(b-(c_cnt-m))
        break
print(coin)
### BUGGY CODE ###

n=int(input())
ans=n-1
for i in range(2,n):
  if n%i:continue
  j=n//i
  if j<i:break
  ans=j+i-2
print(ans)


### FIXED CODE ###

n=int(input())
a=n-1
for i in range(1,int(n**0.5)+1):
  if n%i:continue
  j,k=i,n//i
  a=min(a,j+k-2)
print(a)
### BUGGY CODE ###

N,K = list(map(int,input().strip().split()))
ans = int(10e10)

hlist = [int(input()) for i in range(N)] 

hlist.sort()

for i in range(N-K+1):
    low = min(hlist[i:i+K])
    high = max(hlist[i:i+K])
    ans = min(ans,(high-low))

print(ans)

### FIXED CODE ###

N,K = list(map(int,input().strip().split()))
ans = int(10e10)

hlist = [int(input()) for i in range(N)] 

hlist.sort()

for i in range(N-K+1):
    low = hlist[i]
    high = hlist[i+K-1]
    ans = min(ans,(high-low))

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

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = [sum(d[i:b + i]) for i in range(a - b + 1)]
print(max(e))

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    flag = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            flag = False
            break

    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

# new = [key for key, val in Counter(a).most_common() if val == 1]
prime = [1] * 1000010

for i in set(a):
    # if prime[i]:
    for j in range(i + i, 1000001, i):
        prime[j] = 0

c = Counter(a)
ans = 0
for i in a:
    if prime[i] and c[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
S=list(set(A))

ans=0
for i in S:
    if A.count(i)%2==1:
        ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
c=1
ans=0

for i in range(1,N):
    if A[i]!=A[i-1]:
        if c%2==1:
            ans+=1
        c=1
    else:
        c+=1

if c%2==1:
    ans+=1

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

LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)
for i in range(X):
    Y_i=Y[:i]+str(abs(int(Y[i])-1))+Y[i+1:]
    if Y_i[i]=="1":
        b=d
        f=e+2**(X-1-i)
    else:
        b=c
        f=e-2**(X-1-i)
    if f==0:
        print(0)
    else:
        print(M[f%b]+1)

### FIXED CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Z = []
for i in range(N):
    a = A.copy()
    answeri = 0
    del a[i]
    for k in range(0, len(a)):
        for j in range(k + 1, len(a)):
            if a[k] == 0:
                continue
            elif a[k] == a[j]:
                answeri += 1
    Z.append(answeri)
for x in Z:
    print(x)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = tuple(map(int, input().split()))
A_count = Counter(A)
ans = 0
for i, j in A_count.items():
    ans += j * (j - 1) // 2
for k in range(1, N+1):
    n = A_count[A[k-1]]
    ans_ = ans - (n - 1)
    print(ans_)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B=[0]
c=0
for i in range(0,N):
    B.append(B[i]+A[i])
for k in range(N+1):
    for j in range(k):
        if (B[k]-B[j])%K==(k-j):
            c+=1
print(c)

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
shukei = defaultdict(int)
# AiからAjまでの和→SA[j]-SA[i-1]
# SA[j]-SA[i-1]=j-(i-1)
# 今回はkで割ったあまりなのでaccumulateは使わず自力
S = [0] * (n + 1)
T = [0] * (n + 1)
for i in range(1, n + 1):
    S[i] = S[i - 1] + A[i - 1]
    S[i] %= k
    T[i] = S[i] - i
    T[i] %= k
# i>=1, i<jで同じ値になっている組み合わせを探せば良い。
# kで割ったあまりなので、要素数j−(i-1)がkより小さくないといけない
ans = 0
if k > n + 1:
    for i in range(n + 1):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
else:
    shukei = defaultdict(int)
    for i in range(k):
        shukei[T[i]] += 1
    for key, num in shukei.items():
        ans += num * (num - 1) // 2
    for i in range(k, n + 1):
        j = i - k
        shukei[T[j]] -= 1
        temp = T[i]
        num = shukei[temp]
        ans += num
        shukei[temp] += 1
print(ans)
### BUGGY CODE ###

n=int(input())
word={}

for i in range(n):
    tmpword=input()
    if tmpword in word:
        word[tmpword] = word[tmpword]+1
    else:
        word[tmpword] = 1


#ans.append(max(word.items(),key=lambda x:x[1])[0])
ans=[k for k, v in word.items() if v == max(word.values())]
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

from collections import Counter
import heapq

n=int(input())
word=[]
for i in range(n):
    word.append(input())

word_count=Counter(word)
ma=max(word_count.values())

ans=[k for k, v in word_count.items() if v == ma]
cnt=len(ans)
heapq.heapify(ans)
for i in range(cnt):
    print(heapq.heappop(ans))
### BUGGY CODE ###

s = list(map(int,input()))
t = len(s)
mod = 2019

import numpy as np
arr = [0] * t
arr = np.array(arr)
arr[0] = s[0]
for i in range(1,t):
    arr[i] = (arr[i-1] * 10 + s[i]) % mod

powarr = [1] * t
for i in range(1,t):
    powarr[i] = powarr[i-1]*10 % mod

ans = list(arr).count(0)
for i in range(1,t):
    tmp = (arr[i:] - powarr[i]*arr[:t-i]) % mod
    ans += list(tmp).count(0)

print(ans)

### FIXED CODE ###

s = list(map(int,input()))
s.reverse()
t = len(s)
mod = 2019

arr = [0] * (t+1)
arr[-2] = s[0]
for i in range(1,t):
    arr[t-i-1] = (arr[t-i] + s[i]*pow(10,i,mod)) % mod

from collections import Counter
arr = Counter(arr)

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

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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = min(n, 1 << 10)
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i>>1][j]
        else:
            dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)


for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    cnt = 0
    tmp = v
    v_ = []
    w_ = []
    while tmp > m:
        v_.append(V[tmp-1])
        w_.append(W[tmp-1])
        tmp >>= 1
        cnt += 1
    ret = dp[tmp][L]
    for j in range(1, 1 << cnt):
        weight_sum = 0
        value_sum = 0
        for v, w in zip(v_, w_):
            if j & 1:
                weight_sum += w
                value_sum += v
                if weight_sum > L:
                    break
            j >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

from bisect import bisect_left
def main():
    n = int(input())
    D = sorted(map(int, input().split()))
    m = int(input())
    T = sorted(map(int, input().split()))
    ind = 0
    length = len(D)
    for t in T:
        if ind == length:
            print('NO')
            return
        else:
            index = bisect_left(D[ind:], t)
            if D[ind:][index] != t:
                print('NO')
                return
            else:
                ind += index + 1
    print('YES')
main()

### FIXED CODE ###

from collections import Counter
def main():
    n = int(input())
    D = sorted(map(int, input().split()))
    m = int(input())
    T = sorted(map(int, input().split()))
    CD = Counter(D)
    CT = Counter(T).items()
    for i, c in CT:
        if CD[i] < c:
            print('NO')
            return
    print('YES')
main()
### BUGGY CODE ###

import numpy as np
import re
prog = re.compile('AC')
N, Q = [int(x) for x in input().split()]
S = input()
result = prog.finditer(S)
pos = np.array([res.start()+1 for res in result])

for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  print(len(pos[np.logical_and(pos>=l, pos<=r-1)]))


### FIXED CODE ###

import numpy as np
def find_AC(S):
  ret = [0]*len(S)
  for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
      ret[i+1] = 1
  return ret

N, Q = [int(x) for x in input().split()]
S = input()

cum = np.cumsum(find_AC(S))

for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  ans = cum[r-1] - cum[l-1]
  print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

if 0 == M:
	print(-1)
	exit()

s, t = S - 1, T - 1

graph = [[] for _ in range(N)]
for u, v in UV:
	graph[u - 1] += [v - 1]

INF = 10 ** 12
cost = [[INF, INF, INF] for _ in range(N)]
def print_cost(cost):
	for line in cost:
		for cell in line:
			print("  INF" if cell == INF else " {:4d}".format(cell), end="")
		print()
	print()

def dfs(graph, cost, c, d):
	if cost[c][d % 3] <= d:
		return
	cost[c][d % 3] = d
	#print_cost(cost)
	for n in graph[c]:
		dfs(graph, cost, n, d + 1)

dfs(graph, cost, s, 0)

if INF == cost[t][0]:
	print(-1)
else:
	print(cost[t][0] // 3)


### FIXED CODE ###

N, M = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

if 0 == M:
	print(-1)
	exit()

graph = [set() for _ in range(N)]
for u, v in UV:
	graph[u - 1] |= {v - 1}

INF = 10 ** 12
depths = [[INF, INF, INF] for _ in range(N)]

def bfs(start, end):
	depth = 0
	nodes = {start}
	while nodes:
		if (0 == depth % 3) and (end in nodes):
			return depth // 3
		next_nodes = set()
		for node in nodes:
			if depths[node][depth % 3] <= depth:
				continue
			depths[node][depth % 3] = depth
			next_nodes |= graph[node]
		nodes = next_nodes
		depth += 1
	return -1

print(bfs(S - 1, T - 1))
### BUGGY CODE ###

l, r = list(map(int, input().split()))
count = 0
amari_list = []

for i in range(l, r+1):
    count_j = 0
    for j in range(i+1, r+1):
        amari_list.append(i * j % 2019)
        if count == 2019:
            break
        count_j += 1

    if count == 2019:
        break
    count += 1

ans = min(amari_list)
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc133/tasks/abc133_c
# C - Remainder Minimization 2019

l, r = list(map(int, input().split()))
count = 0
amari_list = []

for i in range(l, r+1):
    count_j = 0
    for j in range(i+1, r+1):
        amari_list.append(i * j % 2019)
        if count_j == 2019:
            break
        count_j += 1

    if count == 2019:
        break
    count += 1

ans = min(amari_list)
print(ans)
### BUGGY CODE ###

N,A=map(int, input().split())
x=list(map(int, input().split()))
dp=[[[0]*(sum(x)+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    for k in range(1, N+1):
        for s in range(1, sum(x)+1):
            if s<x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]

ans=0
for k in range(1,N+1):
    if k*A<=sum(x):
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

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

answer = []
for i in range(N):
  if i + K > N:
    break
  Y = X[i:i+K]
  if Y[0] > 0:
    answer.append(Y[-1])
  elif Y[-1] < 0:
    answer.append(-Y[0])
  else:
    answer.append(min(Y[0]*(-2)+Y[-1], Y[-1]*2-Y[0]))

print(min(answer))

### FIXED CODE ###

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

tmp=10**10
for i in range(N-K+1):
  if x[i]*x[i+K-1]<0:
    tmp=min(tmp,min(abs(x[i]),abs(x[i+K-1]))*2+max(abs(x[i]),abs(x[i+K-1])))
  else:
    tmp=min(tmp,max(abs(x[i]),abs(x[i+K-1])))
print(tmp)
### BUGGY CODE ###

s=[str(x) for x in input()]

sum=0
for i in range(len(s)-4):
    for j in range(i+4,len(s)):
        t=''.join(s[i:j+1])
        if int(t)%2019==0:
            sum+=1
print(sum)

### FIXED CODE ###

from collections import deque
s=input()[::-1]
l=[0]*2019
ten=1
sm=0
cnt=0
l[0]=1
for i in range(len(s)):
    sm += int(s[i])*ten
    sm %= 2019
    cnt += l[sm]
    l[sm] += 1
    ten = ten *10 %2019
print(cnt)
### BUGGY CODE ###

xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[[xs,ys,0]]+[list(map(int,input().split())) for i in range(N)]+[[xt,yt,0]]
inf=10**20
c=[[max(0,((XYR[i][0]-XYR[j][0])**2+(XYR[i][1]-XYR[j][1])**2)**.5-XYR[i][2]-XYR[j][2]) for j in range(N+2)] for i in range(N+2)]
from heapq import heappop,heappush
def dij(c,N,s):
    d=[inf]*N
    d[s]=0
    q=[]
    heappush(q,(0,s))
    while q:
        i=heappop(q)[1]
        for j,w in enumerate(c[i]):
            temp=d[i]+w
            if d[j]>temp:
                d[j]=temp
                heappush(q,(d[j],j))
    return d
print(dij(c,N+2,0)[-1])

### FIXED CODE ###

xs,ys,xt,yt=map(int,input().split())
N=int(input())
import numpy as np
XYR=np.empty((N+2,3),dtype=np.float64)
XYR[1:-1,:]=np.array([input().split() for i in range(N)])
XYR[0,:]=xs,ys,0
XYR[-1,:]=xt,yt,0
X,Y,R=XYR.T
c=np.maximum(0,np.sqrt(np.square(X[None,:]-X[:,None])+np.square(Y[None,:]-Y[:,None]))-R[None,:]-R[:,None])
c[range(N+2),range(N+2)]=-1
from scipy.sparse import*
g=csgraph.csgraph_from_dense(c,null_value=-1)
print(csgraph.dijkstra(g,indices=0)[-1])
### BUGGY CODE ###

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

### 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])
### BUGGY CODE ###

import fractions
n, m = map(int, input().split())
listS = list(input())
listT = list(input())
listX = []


l= n*m // fractions.gcd(n, m)
a=l//n
b=l//m

if listS[0]!=listT[0]:
    print(-1)
else:
    index =0
    index2=0
    while index < l:
        while index2 < n:
            if index == index2*a:
                listX.append(listS[index2])
                index2+=1
                index+=1
            else:
                listX.append(0)
                index+=1
        index+=1
    index4=0
    flag=0
    while index4 < min(m, l//b):
        if listX[index4*b] == listT[index4] or listX[index4*b] == 0:
            index4+=1
        else:
            print(-1)
            flag=1
            break
    if flag!=1:
        print(l)

### FIXED CODE ###

n, m = map(int, input().split())
listS= list(input())
listT = list(input())


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


l = n*m // gcd(n, m)
a = l//n
b = l//m

if listS[0]!=listT[0]:
    print(-1)
else:
    checkI = a*b // gcd(a, b)
    if checkI > l:
        print(l)
    else:
        index=0
        flag=0
        while index < l//min(a, b):
            if index*checkI//a > len(listS)-1 or index*checkI//b > len(listT)-1:
                break
            elif listS[index*checkI//a] != listT[index*checkI//b]:
                print(-1)
                flag=1
                break
            else:
                index+=1
        if flag==0:
            print(l)
### BUGGY CODE ###

mod=1000000007
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=(x[i]%mod*x[j]%mod)%mod
print((ans)%mod)


### FIXED CODE ###

mod=1000000007
n=int(input())
x=list(map(int,input().split()))
cl=[1]
for i in range(1,n):
    cl.append(cl[i-1]+x[i])
sum=0
for i in range(n-1):
    sum+= x[i]*(cl[n-1]-cl[i])
    sum%=mod

print(sum)
### BUGGY CODE ###

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

for _ in range(k):
  max_num = max(data)
  max_index = data.index(max_num)
  data[max_index] = 0

print(sum(data))


### FIXED CODE ###

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

data.sort()

for _ in range(k):
  if data.__len__() > 0:
    data.pop()
  else:
    break

print(sum(data))