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

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

n += 5

sa = set(a)
sb = set(b)

count = [0] * n
counta = [0] * n
countb = [0] * n
for v in a:
    count[v] += 1
    counta[v] += 1
for v in b:
    count[v] += 1
    countb[v] += 1

outA = dict()
for v in a:
    outA[v] = []

import heapq
q = []
for v in range(n):
    if count[v]:
        heapq.heappush(q,(-count[v],v))
    
while q[0][0] < 0:
    c, v = heapq.heappop(q)
    if count[v] + c:
        heapq.heappush(q,(-count[v],v))
        continue
    if counta[v]:
        for v2 in sb:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v].append(v2)
        count[v] -= 1
        count[v2] -= 1
        counta[v] -= 1
        countb[v2] -= 1
        if counta[v] == 0:
            sa.remove(v)
        if countb[v2] == 0:
            sb.remove(v2)
    else:
        for v2 in sa:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v2].append(v)
        count[v] -= 1
        count[v2] -= 1
        counta[v2] -= 1
        countb[v] -= 1
        if counta[v2] == 0:
            sa.remove(v2)
        if countb[v] == 0:
            sb.remove(v)
    if count[v]:
        heapq.heappush(q, (-count[v], v))

out = []
for v in a:
    out.append(outA[v].pop())
print('Yes')
print(' '.join(map(str,out)))


### FIXED CODE ###

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

sa = set(a)
sb = set(b)

count = [0] * (n + 1)
counta = [0] * (n + 1)
countb = [0] * (n + 1)

for v in a:
    count[v] += 1
    counta[v] += 1
for v in b:
    count[v] += 1
    countb[v] += 1

for v in count:
    if v > n:
        print('No')
        exit()

outA = dict()
for v in a:
    outA[v] = []

import heapq
q = []
for v in range(n + 1):
    if count[v]:
        heapq.heappush(q,(-count[v],v))
    
while q[0][0] < 0:
    c, v = heapq.heappop(q)
    if count[v] + c:
        heapq.heappush(q,(-count[v],v))
        continue
    if counta[v]:
        for v2 in sb:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v].append(v2)
        count[v] -= 1
        count[v2] -= 1
        counta[v] -= 1
        countb[v2] -= 1
        if counta[v] == 0:
            sa.remove(v)
        if countb[v2] == 0:
            sb.remove(v2)
    else:
        for v2 in sa:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v2].append(v)
        count[v] -= 1
        count[v2] -= 1
        counta[v2] -= 1
        countb[v] -= 1
        if counta[v2] == 0:
            sa.remove(v2)
        if countb[v] == 0:
            sb.remove(v)
    if count[v]:
        heapq.heappush(q, (-count[v], v))

out = []
for v in a:
    out.append(outA[v].pop())
print('Yes')
print(' '.join(map(str,out)))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def price(x):
    return x // 2

while m > 0:
    a[0] = price(a[0])
    a.sort(reverse=True)
    m -= 1

print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
price = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(price)
for _ in range(m):
    max_price = -heapq.heappop(price)
    heapq.heappush(price, -(max_price//2))

ans = -sum(price)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

r = []
g = []
b = []

for i, c in enumerate(s):
    if c == "R":
        r.append(i)
    elif c == "G":
        g.append(i)
    else:
        b.append(i)


ans = 0
for ri in r:
    for gi in g:
        for bi in b:
            if abs(ri - gi) == abs(gi - bi) or abs(ri - bi) == abs(gi - bi) or abs(ri - bi) == abs(ri - gi):
                pass
            else:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")


ans = r * g * b

for i in range(n):
    for j in range(i + 1, n):
        if 2 * j - i > n - 1:
            continue
        if s[i] == s[j] or s[i] == s[2 * j - i] or s[j] == s[2 * j - i]:
            pass
        else:
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
x = P.pop(0)
m = x
ans = 1
for i in range(N-1):
    x = P.pop(0)
    if x <= m:
        ans += 1
        m = x
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
x = P[0]
m = x
ans = 1
for i in range(1,N):
    x = P[i]
    if x <= m:
        ans += 1
        m = x
print(ans)
### BUGGY CODE ###

S = input()
a = len(S)
L = [0]
for i in range(a):
    L.append(int(S[:i+1])%2019)
k = 0
M = []
for j in range(a+1):
  M.append(10**j % 2019)
#x文字目からy文字目
for x in range(1,a+1):
    for y in range(x,a+1):
        if (L[x-1]*M[y-x+1] - L[y]) % 2019 == 0:
            k += 1
print(k)

### FIXED CODE ###

S = input()
a = len(S)
mod = 0
ten = 1
L = [0]*2019 #余りの列
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(ten)+mod) %2019
    L[mod] += 1
    ten = (ten*10)%2019
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n) + 1
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(3, floor(n/c) + 1):
            l[c * k -1] = 0
        c = l[:c].index(1) + c
    return sum(l)
for n in stdin:
    n = int(n)
    print(cntPrime(n))

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

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

ans = [0] * N

for i in range(10 ** 9 + 1):
    ans[0] = i
    bit = 0
    for i in range(1, N):
        ans[i] = a[i - 1] ^ a[i] ^ ans[i - 1]
        bit ^= ans[i]
    if bit == a[0]:
        break

print(' '.join(map(str, ans)))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
S = 0
for i in range(N):
    S ^= a[i]

ans = [0] * N

for i in range(N):
    ans[i] = S ^ a[i]

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def linput():
    return [int(x) for x in input().split()]

n = int(input())
s = input().rstrip()

r = []
g = []
b = []

for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)

import bisect
from copy import deepcopy
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        ng = j + (j - i)
        if s[i] == "R" and s[j] == "G":
            l = deepcopy(b)
        elif s[i] == "R" and s[j] == "B":
            l = deepcopy(g)
        elif s[i] == "G" and s[j] == "R":
            l = deepcopy(b)
        elif s[i] == "G" and s[j] == "B":
            l = deepcopy(r)
        elif s[i] == "B" and s[j] == "R":
            l = deepcopy(g)
        elif s[i] == "B" and s[j] == "G":
            l = deepcopy(r)
        ans += bisect.bisect_left(l, j + (j - i)) - bisect.bisect_right(l, j)
        ans += len(l) - bisect.bisect_right(l, j + (j - i))

print(ans)






### FIXED CODE ###

import sys
input = sys.stdin.readline

def linput():
    return [int(x) for x in input().split()]

n = int(input())
s = input().rstrip()

from collections import Counter

r = [0] * (n + 1)
g = [0] * (n + 1)
b = [0] * (n + 1)



for i in range(1, n + 1):
    if s[i - 1] == "R":
        r[i] = r[i - 1] + 1
    else:
        r[i] = r[i - 1]
    if s[i - 1] == "G":
        g[i] = g[i - 1] + 1
    else:
        g[i] = g[i - 1]
    if s[i - 1] == "B":
        b[i] = b[i - 1] + 1
    else:
        b[i] = b[i - 1]

ans = 0
for i in range(n):
    for j in range(i + 1, n - 1):
        if s[i] == s[j]:
            continue
        ng = j + (j - i) + 1
        if s[i] == "R" and s[j] == "G":
            l = b
        elif s[i] == "R" and s[j] == "B":
            l = g
            #c = cg
        elif s[i] == "G" and s[j] == "R":
            l = b
            #c = cb
        elif s[i] == "G" and s[j] == "B":
            l = r
            #c = cr
        elif s[i] == "B" and s[j] == "R":
            l = g
            #c = cg
        elif s[i] == "B" and s[j] == "G":
            l = r
            #c = cr
        ans += l[n] - l[j + 1]
        if ng < n + 1:
            ans -= l[ng] - l[ng - 1]
        #print(ans)

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

import sys

# %%

n, m = list(map(int, sys.stdin.readline().split()))
ary = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
bry = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    ary.append(0)
    bry.append(0)

    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):

        if (num == ary[i]) & (num == bry[j]):
            i += 1
            j += 1

        elif (num == ary[i]) ^ (num == bry[j]):
            if num == ary[i]:
                cnt *= len(bry[:j])
                i += 1
            else:
                cnt *= len(ary[:i])
                j += 1

        else:
            na = len(ary[:i])
            nb = len(bry[:j])
            cnt *= (na * nb - (n * m - num))

        cnt = cnt % mod

    print(cnt % mod)


### FIXED CODE ###

import sys

# %%

n, m = list(map(int, sys.stdin.readline().split()))
ary = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
bry = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    ary.append(0)
    bry.append(0)

    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):

        if (num == ary[i]) and (num == bry[j]):
            i += 1
            j += 1

        elif (num == ary[i]) or (num == bry[j]):
            if num == ary[i]:
                cnt *= len(bry[:j])
                i += 1
            else:
                cnt *= len(ary[:i])
                j += 1

        else:
            # na = len(ary[:i])
            # nb = len(bry[:j])
            cnt *= (i * j - (n * m - num))

        cnt = cnt % mod

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

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

for l in range(N):
  S[l].sort()

ans = 0
for j in range(N-1):
  for k in range(j+1,N):
    p = 0
    x = 1
    while x == 1 and p < 10:
      if S[j][p] != S[k][p]:
        x = 0
        break
      else:
        p += 1
    ans += x

print(ans)


### FIXED CODE ###

from operator import itemgetter
N = int(input())
S = [list(input()) for i in range(N)]

for l in range(N):
  S[l].sort()
  S[l] = ''.join(S[l]) 

S.sort()

X = []
p = 1

for j in range(N-1):
  if S[j] == S[j+1]:
    p +=1
  else:
    X.append(p)
    p = 1
X.append(p)


def comb(n):
  if n == 2: return 1
  else:
    return int(n*(n-1)/2)

ans = 0

for k in range(len(X)):
  ans += comb(X[k])

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

import re
S = input()

count = 0
while True:
    if 'ABCBC' in S:
        s = re.subn('ABCBC','BCABC',S)
        S = s[0]
        count += s[1]
    if 'AABC' in S:
        s = re.subn('AABC','ABCA',S)
        S = s[0]
        count += s[1]
        continue
    if 'ABC' in S:
        s = re.subn('ABC','BCA',S)
        S = s[0]
        count += s[1]
    else:
        break
print(str(count))

### FIXED CODE ###

import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)
 
count = 0
for l in S_li:
    a = sum([i for i,x in enumerate(l) if '1' in x])
    su=sum([x for x in range(l.count('1'))])
    count += (a-su)
print(str(count))
### BUGGY CODE ###

from collections import defaultdict


def main():
    N = int(input())
    S = input()
    counter = defaultdict(int)
    for c in S:
        counter[c] += 1
    ans = 0
    for i in range(N - 1, 0, -1):
        ci = S[i]
        if counter[ci] <= 1:
            continue
        for j in range(i - ans - 1, -1, -1):
            cj = S[j]
            if cj != ci:
                continue
            k = 0
            while k + 1 <= min(j + 1, i - j - 1) and S[i - k - 1] == S[j - k - 1]:
                k += 1
            ans = max(ans, k + 1)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    # flags[n][m]: n 番目の文字と同じ文字がその m 個後にあれば1
    flags = [[0] * N for _ in range(N)]
    for n, c in enumerate(S):
        for m in range(1, N - n):
            if c == S[n + m]:
                flags[n][m] = 1
    ans = 0
    for m in range(1, N):
        from_n = -1
        for to_n in range(N):
            if flags[to_n][m] == 0:
                ans = max(ans, min(m, to_n - from_n - 1))
                from_n = to_n
        if from_n != to_n:
            ans = max(ans, min(m, to_n - from_n - 1))
    print(ans)


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

import bisect
x, n = map(int, input().split())
pN = list(map(int, input().split()))
plus_flag = 1
minus_flag = 1
pN.sort()
key_index = bisect.bisect(pN, x) - 1
plus_index = key_index
minus_index = key_index

if n == 0:
    print(x)
else:
    while(1):
        if minus_index <= 0:
            minus_flag = 0
            
        if minus_flag == 1:
            if pN[minus_index] - 1 != pN[minus_index-1]:
                print(pN[minus_index] - 1)
                break
            else:
                minus_index = minus_index - 1

        

        if plus_index >= n-1:
            plus_flag = 0

        if plus_flag == 1:
            if pN[plus_index] + 1 != pN[plus_index+1]:
                print(pN[plus_index] + 1)
                break
            else:
                plus_index = plus_index + 1


### FIXED CODE ###

import bisect
x, n = map(int, input().split())
pN = list(map(int, input().split()))

pN.sort()

diff = 0

if n == 0:
    print(x)
else:
    while(1):
        if x-diff not in pN:
            print(x-diff)
            exit()
        elif x+diff not in pN:
            print(x+diff)
            exit()
        diff+=1
### BUGGY CODE ###

# coding:utf-8                                                        

N = raw_input()
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

count = 0

for a in A:
    for b in B:
        for c in C:
            if a < b and b < c:
                count += 1

print count


### FIXED CODE ###

# coding:utf-8                                                        

import bisect

N = int(raw_input())
A = sorted(map(int, raw_input().split()))
B = sorted(map(int, raw_input().split()))
C = sorted(map(int, raw_input().split()))

count = 0

for mid in B:
    lower_bound = bisect.bisect_left(A, mid)
    upper_bound = N - bisect.bisect_right(C, mid)
    count += lower_bound * upper_bound

print count
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
if N == K:
    print(0)
else:
    d = {str(i):0 for i in a}
    bucket = sorted([a.count(int(i)) for i in d])
    print(sum(bucket[0:len(bucket) - K:]))

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
a = Counter(list(map(int, input().split())))
if N == K:
    print(0)
else:
    num = list(a.values())
    if len(num) <= K:
        print(0)
    else:
        print(sum(sorted(num)[:-K]))
### BUGGY CODE ###

from collections import deque

H, W, K = map(int, input().split())

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

G = [list(input()) for _ in range(H)]
check = [[-1] * (W) for _ in range(H)]

que = deque()

flag = False
for h in range(H):
    for w in range(W):
        if G[h][w] == 'S':
            que.append((h, w))
            flag = True
            break
    if flag:
        break

x_min = h
x_max = h

y_min = w
y_max = w

check[h][w] = 0
while que:
    tmp = que.popleft()
    
    x = tmp[0]
    y = tmp[1]
    
    now_ = check[x][y]
    if now_ == K:
        continue

    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if G[nx][ny] == '#':
            continue
        if check[nx][ny] == -1:
            check[nx][ny] = now_ + 1
            que.append((nx, ny))
            
            x_min = min(x_min, nx)
            x_max = max(x_max, nx)

            y_min = min(y_min, ny)
            y_max = max(y_max, ny)

ans = 10 ** 18
ans = min(ans, (x_min + K - 1) // K + 1)
ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
ans = min(ans, (y_min + K - 1) // K + 1)
ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)

print (ans)


### FIXED CODE ###

from collections import deque

H, W, K = map(int, input().split())

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

G = [list(input()) for _ in range(H)]
check = [[-1] * (W) for _ in range(H)]

que = deque()

flag = False
for h in range(H):
    for w in range(W):
        if G[h][w] == 'S':
            que.append((h, w))
            flag = True
            break
    if flag:
        break

x_min = h
x_max = h

y_min = w
y_max = w

check[h][w] = 0
while que:
    tmp = que.popleft()
    
    x = tmp[0]
    y = tmp[1]
    
    now_ = check[x][y]
    if now_ == K:
        continue

    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if G[nx][ny] == '#':
            continue
        if check[nx][ny] == -1:
            check[nx][ny] = now_ + 1
            que.append((nx, ny))
            
            x_min = min(x_min, nx)
            x_max = max(x_max, nx)

            y_min = min(y_min, ny)
            y_max = max(y_max, ny)

ans = 10 ** 18
ans = min(ans, (x_min + K - 1) // K + 1)
ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
ans = min(ans, (y_min + K - 1) // K + 1)
ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)

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

s = input()
cnt = 0
while '10' in s:
    ind = s.find('10')
    temp = []
    temp.append(str(s[0:ind]))
    temp.append(str(s[ind + 2:len(s)]))
    #print(s)
    s = "".join(temp)
    cnt = cnt + 2

while '01' in s:
    ind = s.find('01')
    # print(ind)
    temp = []
    temp.append(str(s[0:ind]))
    temp.append(str(s[ind + 2:len(s)]))
    s = "".join(temp)
    #print(s)
    cnt = cnt + 2

print(cnt)

### FIXED CODE ###

s = input()
cnt = 0

l = list(s)
a = l.count('0')
b = l.count('1')

# print(a)
# print(b)

print(min(a,b) * 2)
exit()
while '10' in s:
    ind = s.find('10')
    temp = []
    temp.append(str(s[0:ind]))
    temp.append(str(s[ind + 2:len(s)]))
    #print(s)
    s = "".join(temp)
    cnt = cnt + 2

while '01' in s:
    ind = s.find('01')
    # print(ind)
    temp = []
    temp.append(str(s[0:ind]))
    temp.append(str(s[ind + 2:len(s)]))
    s = "".join(temp)
    #print(s)
    cnt = cnt + 2

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

N,K=map(int,input().split())
if N==0 or K==1:
    print(0)
else:
    for i in range(10**18):
        if N>abs(N-K):
            N=abs(N-K)
        else:
            print(N)  
            break

### FIXED CODE ###

N,K=map(int,input().split())
if N==0 or K==1:
    print(0)
else:
    a=N//K
    N=N-a*K
    for i in range(10**18):
        if N>abs(N-K):
            N=abs(N-K)
        else:
            print(N)  
            break
### BUGGY CODE ###

import fractions
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
    
A,B = map(int,input().split())
Cd = list(set(dv(A))&set(dv(B)))
N = len(Cd)
ans = []
for i in range(N,0,-1):
    for c in itertools.combinations(Cd,i):
        if not c:
            continue
        Flag = 1
        for i in itertools.combinations(c, 2):
            if gcd_list(i) != 1:
                Flag = 0
                break
        if Flag == 1:
           ans.append(len(c))
    if ans:
        print(max(ans))
        exit()

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
import fractions
A,B = map(int,input().split())
ans = factorization(fractions.gcd(A,B))
if ans[0][0] == 1:
    print(len(ans))
else:
    print(len(ans)+1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
out = []
for i in range(n):
    out.append(a.index(n-i)+1)
print(' '.join(list(reversed([str(i) for i in out]))))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
out = [0] * n
for i in range(len(a)): out[a[i] - 1] = i + 1
print(' '.join([str(i) for i in out]))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
alist=[ 0 for i in range(n)]
for _ in a:
    alist[_ - 1] += 1
for j in aset:
    k=a.count(j)
    ans += (k*(k-1)) // 2
for u in a:
    print(ans - alist[u - 1]+1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
al=[0]*200000
for i in a:
    al[i]+=1
for j in aset:
    k=al[j]
    ans+=(k*(k-1))//2
for u in a:
    print(ans-al[u]+1)
### BUGGY CODE ###

def main(n,w,item):
    #dp[i][sum_w]:i-1番目までの品物から重さsum_wを超えないように
    #選択した場合の価値の最大値
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            #選択する場合
            weight, value = item[i]
            if j+weight <= w:
                dp[i+1][j+weight] = max(dp[i+1][j+weight], dp[i][j]+value)
            #選択しない場合
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    return max(dp[-1])

n,w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
print(main(n,w,item))

### FIXED CODE ###

def main(n,w,item):
    #dp[i][sum_w]:i-1番目までの品物から重さsum_wを超えないように
    #選択した場合の価値の最大値
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(w+1):
            #選択する場合
            weight, value = item[i]
            if j+weight <= w:
                dp[i+1][j+weight] = max(dp[i+1][j+weight], dp[i][j]+value)
            #選択しない場合
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    return max(dp[-1])

n,w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
print(main(n,w,item))
### BUGGY CODE ###

N = int(input())
al = list(map(int,input().split()))
sss=0
for i in range(N):
    sss+=al[i]*sum(al[0:i])
    sss%=1000000007
print(sss)

### FIXED CODE ###

N = int(input())
al = list(map(int,input().split()))
sss=0
pss=0
for i in range(1,N):
    pss+=al[i-1]
    sss+=al[i]*pss
print(sss%1000000007)
### BUGGY CODE ###

def kitaichi(a):
    sum = 0
    for i in range(a):
        sum += i+1
    return sum / a

n, k = map(int, input().split())
p = [int(_) for _ in input().split()]

ans = 0
ans_index = 0
for i in range(0, n-k+1):
    val = 0
    for j in range(k):
        val += p[i+j]
    if val > ans:
        ans = val
        ans_index = i

sum = 0
for i in range(ans_index, ans_index+k):
    sum += kitaichi(p[i])

print(sum)

### FIXED CODE ###

def kitaichi(a):
    return ((1+a)*a/2)/a

n, k = map(int, input().split())
p = [int(_) for _ in input().split()]
dp = [0] * n
dp[0] = p[0]
cnt = 1

maxi = 0
idx = 0

for i in range(1, n):
    if cnt < k:
        dp[i] = p[i] + dp[i-1]
        cnt += 1
    else:
        dp[i] = p[i] + dp[i-1] - p[i-k]
    if maxi < dp[i]:
        maxi = dp[i]
        idx = i

ans = 0
for i in range(idx-k+1, idx+1):
    ans += kitaichi(p[i])

print(ans)