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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappop, heappush

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

q = []
push = lambda x,i: heappush(q, (-x<<30)+i)
for i,x in enumerate(B):
    push(x,i)

answer = 0
mask = (1<<30)-1
while q:
    i = heappop(q)&mask
    x = B[i]
    dx = x-A[i]
    if dx < 0:
        answer = -1
        break
    if dx == 0:
        continue
    left = i-1 if i >= 1 else N-1
    right = i+1 if i < N-1 else 0
    nbd = B[left] + B[right]
    t = dx // nbd
    if t == 0:
        answer = -1
        break
    B[i] -= nbd * t
    answer += t
    push(B[i],i)

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappop, heappush

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

q = []
push = lambda x,i: heappush(q, (-x,i))
for i,x in enumerate(B):
    push(x,i)

answer = 0
while q:
    x,i = heappop(q)
    x = -x
    if x < A[i]:
        answer = -1
        break
    dx = x-A[i]
    nbd = B[(i-1)%N] + B[(i+1)%N]
    t = dx // nbd
    if t == 0:
        if x == A[i]:
            continue
        answer = -1
        break
    B[i] -= nbd * t
    answer += t
    push(B[i],i)

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

n = int(input())

l = [2,1]
i = 2
while True:
    l.append(l[i-1] + l[i-2])
    if i == n:
        print(l[i])
        exit()
    else:
        i += 1

### FIXED CODE ###

n = int(input())

l = [2,1]
i = 2
while True:
    l.append(l[i-1] + l[i-2])
    if i == n:
        print(l[i])
        exit()
    elif n == 0:
        print(2)
        exit()
    elif n == 1:
        print(1)
        exit()
    else:
        i += 1
### BUGGY CODE ###

def index(x):
    y = x//2
    return y

n = int(input())
a = list(map(int, input().split()))
count = 0
b = 1
while b >= 1:
    for i in a:
        if i % 2 != 0:
            b = 0
            break
    else:
        a = map(index, a)
        count += 1
print(count)


### FIXED CODE ###

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

while all(i % 2 == 0 for i in a):
    a = [j/2 for j in a]
    count += 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_right

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

aN.sort()
# 単体で条件を満たすものは必要確定なので除く
aN2 = aN[:bisect_right(aN, K)]
aN2.reverse()

need = [False] * len(aN2)
for i in range(1 << len(aN2)):
    # 全部合わせても足りないようじゃ論外
    if sum(aN2) < K:
        break
    sm = 0
    for j in range(len(aN2)):
        if 1 & i>>j == 1:
            sm += aN2[j]
        # 複数で条件を満たせば、それに含まれるものは必要
        if sm >= K:
            for k in range(j+1):
                if 1 & i>>k == 1:
                    need[k] = True
            break
print(need.count(False))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY 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)

ans = []
for ai in range(len(a)):
    for bi in range(len(b)):
        if (ai+1)*(bi+1) > k:
            continue
        for ci in range(len(c)):
            if (ai+1)*(bi+1)*(ci+1) >k:
                continue
            ans.append(a[ai] + b[bi] +c[ci])

ans = sorted(ans, reverse=True)
for i in range(k):
    print(ans[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)

sumAB = sorted([ai + bi for ai in a for bi in b],reverse=True)[:k]
final_ans = sorted([ci + abi for ci in c for abi in sumAB],reverse = True)[:k]

for i in range(k):
    print(final_ans[i])
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]

ans = 0

for a_index in range(N+1):
    left = K - A[a_index]
    if left < 0: continue

    b_index = M
    while left - B[b_index] < 0:
        b_index -= 1

    ans = max(ans, a_index + b_index)

print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]

ans = 0

b_index = M

for a_index in range(N+1):
    left = K - A[a_index]
    if left < 0: continue

    while left - B[b_index] < 0:
        b_index -= 1

    ans = max(ans, a_index + b_index)

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

import sys

input = sys.stdin.readline

def main():
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for pi in P:
		if pi[2]<=L:
			neighbor[pi[0]-1].append((pi[1]-1,pi[2]))
			neighbor[pi[1]-1].append((pi[0]-1,pi[2]))

	start = 0
	end = 2

	fuellist = [0]*N
	def bfs(start, end):
		fuel = [[10000000,L+1] for i in range(N)]
		fuel[start][0] = 0
		fuel[start][1] = L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			for i in queue:				# target node
				oc, om = fuel[i]
				for j, d in neighbor[i]:	# next node
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if (nc<fuel[j][0]) or (nc==fuel[j][0] and nm>fuel[j][1]):
						fuel[j][0], fuel[j][1] = nc, nm
						nq.append(j)

			queue = nq					# update target node

		ans = fuel[end][0]
		if fuel[end][0]==10000000: ans = -1

		fuellist[start] = fuel

		print(ans)

	for s, t in st:
		start, end = s-1, t-1
		if fuellist[start]==0:
			bfs(start,end)
		else:
			ans = fuellist[start][end][0]
			if ans==10000000: ans = -1
			print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys


def main():
	input = sys.stdin.readline
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for s,e,d in P:
		if d<=L:
			neighbor[s-1].append((e-1,d))
			neighbor[e-1].append((s-1,d))
		# if d<=L:
		# 	neighbor[s-1][e-1] = neighbor[e-1][s-1] = d

	# print(neighbor)
	# start, end = 2,1

	fuellist = [0]*N
	def bfs(start, end):
		# fuel = [[10000000,L+1] for i in range(N)]
		fuelc, fuelm = [10000000]*N, [L+1]*N
		# fuel[start][0] = 0
		# fuel[start][1] = L
		fuelc[start], fuelm[start] = 0, L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			nq_append = nq.append
			for i in queue:				# target node
				oc, om = fuelc[i], fuelm[i]
				for j, d in neighbor[i]:
				# for j, d in enumerate(neighbor[i]):	# next node
					# if d==10**10: continue
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if nc<fuelc[j]:
						fuelc[j], fuelm[j] = nc, nm
						nq_append(j)
					elif nc==fuelc[j] and nm>fuelm[j]:
						fuelm[j] = nm
						nq_append(j)

			queue = nq					# update target node

		# ans = fuel[end][0]
		ans = fuelc[end]
		if ans==10000000: ans = -1

		fuellist[start] = fuelc

		print(ans)

	for s, t in st:
		start, end = s-1, t-1

		if fuellist[start]!=0:
			ans = fuellist[start][end]
			if ans==10000000: ans = -1
			print(ans)
		elif fuellist[end]!=0:
			ans = fuellist[end][start]
			if ans==10000000: ans = -1
			print(ans)
		else:
			bfs(start,end)


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

# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


def solve(N, A):
    # 階乗N!を求める
    fact = [1] * N
    for i in range(1, N):
        fact[i] = fact[i - 1] * (i + 1)

    # 1/N!の逆元を求める
    fact_inv = [1] * N
    fact_inv[-1] = pow_mod(fact[-1], MOD - 2)
    for i in range(N - 1, 0, -1):
        tmp = fact_inv[i] * (i + 1)
        tmp %= MOD
        fact_inv[i - 1] = tmp

    # 1/kを求める
    inv = [1]
    for i in range(1, N):
        inv.append((fact[i - 1] * fact_inv[i]) % MOD)

    # 1/kの累積和を求める
    inv_sum = [1]
    for i in range(1, N):
        inv_sum.append((inv_sum[-1] + inv[i]) % MOD)

    # 累積和の結果を係数としてAiに掛けて、加算する
    ans = 0
    for i in range(N):
        ans += A[i] * (inv_sum[i] + inv_sum[N - 1 - i] - 1)
        ans %= MOD

    # ansにN!を掛けたものを返す
    return ans * fact[-1] % MOD


N = int(input())
A = inpl()
print(solve(N, A))


### FIXED CODE ###

# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


def solve(N, A):
    # 1/1 + 1/2 + 1/3 + ... + 1/Nの累積和を求めておく
    inv_sum = [0]
    for i in range(N):
        inv_sum.append((inv_sum[-1] + pow_mod(i + 1, MOD - 2)) % MOD)
    del inv_sum[0]

    # 各iについて、Σ(j=1, N) 1/(|j - i| + 1)を求めて、
    # それらを係数としてA[i]に掛け、加算する
    ans = 0
    for i in range(N):
        ans += + A[i] * (inv_sum[N - 1 - i] + inv_sum[i] - 1)
        ans %= MOD

    # ansにN!を掛ける
    for i in range(N):
        ans *= (i + 1)
        ans %= MOD
    return ans


N = int(input())
A = inpl()
print(solve(N, A))
### BUGGY CODE ###

from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
lst=[0]*n
for i in a:
  lst[i-1]+=1
lst_=list(map(lambda x:x*(x-1)//2,lst))
for i in range(n):
  ans=sum(lst_)
  p=a.popleft()
  if lst_[p-1]==0:
    print(ans)
  else:
    print(ans-(lst_[p-1]-(lst[p-1]-1)*(lst[p-1]-2)//2))
  a.append(p)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
lst1=[0]*(n+1)
lst2=[0]*(n+1)
for i in a:
  lst1[i]+=1
for i in range(n+1):
  if lst1[i]>0:
    lst2[i]=lst1[i]-1
lst3=list(map(lambda x:x*(x-1)//2,lst1))
lst4=list(map(lambda x:x*(x-1)//2,lst2))
ans=sum(lst3)
for i in a:
  print(ans-(lst3[i]-lst4[i]))
### BUGGY CODE ###

# 2019-11-11 18:30:26(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, k, *h = (int(x) for x in sys.stdin.read().split())
    h.sort()
    min_diff = h[-1] - h[0] # default value
    for i in range(n - k + 1):
        heights = h[i:i+k]
        diff = heights[-1] - heights[0]
        min_diff = min(min_diff, diff)
    print(min_diff)



if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-11 18:30:26(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, k, *h = (int(x) for x in sys.stdin.read().split())
    h.sort()
    min_diff = h[-1] - h[0] # default value
    for i in range(n - k + 1):
        diff = h[i+k-1] - h[i]
        min_diff = min(min_diff, diff)
    print(min_diff)

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

a,b,c,k = map(int,input().split())
if a == b == c:
    print(0)
    exit()
for i in range(k):
    a_o = a
    b_o = b
    c_o = c
    a = b_o + c_o
    b = a_o + c_o
    c = a_o + b_o
    if abs(a-b) > 10**18:
        print("Unfair")
        break
print(a-b)


### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = a - b
if k % 2 == 0:
    print(ans)
else:
    print(-ans)
### BUGGY CODE ###

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

countdic = {}
mod = 2019

for i in range(1,n+1):
    num = s%(pow(10,i))
    remainder = num%mod
    if remainder in countdic:
        countdic[remainder] += 1
    if remainder not in countdic:
        countdic[remainder] = 1

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

if 0 in countdic:
    ans += countdic[0]

print(ans)

### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

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

if 0 in countdic:
    ans += countdic[0]

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

N,A,B = [int(x) for x in input().split()]
n = 0
blue = 0
if A == 0:
    print(0)
else:
    for i in range(10**18):
        n = n + A
        blue = blue + A
        if n >= N:
            blue = blue - (n-N)
            break
        else:
            n = n + B
            if n >= N:
                break
    print(blue)

### FIXED CODE ###

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

a = N//(A+B)*A

if N%(A+B) <= A:
    print(a + N%(A+B))
else:
    print(a + A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

S = input().strip()
#-----
num = 0
cnt_mod = {}
mod = 2019

for i in range(len(S)):
    digit = int( S[len(S)-1-i] )
    
    num += digit * (10**i % mod)
    num %= mod
    
    remainder = num % mod
    
    cnt_mod.setdefault(remainder, 0)
    cnt_mod[remainder] += 1


ans = 0

for r,c in cnt_mod.items():
    # r: remainder
    # c: count
    if r == 0:
        ans += c
    elif c >= 2:
        ans += c*(c-1)//2

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

S = input().strip()
#-----
num = 0
cnt_mod = {0:1}  # type {int: int} , contents {remainder : count}
mod = 2019
base_pow = 1

for i in range(len(S)):
    digit = int( S[len(S)-1-i] )
    
    num += (digit * base_pow) % mod
    num %= mod
    
    base_pow = (base_pow * 10) % mod
    
    cnt_mod.setdefault(num, 0)
    cnt_mod[num] += 1


ans = 0

for r,c in cnt_mod.items():
    # r: remainder
    # c: count
    if c >= 2:
        ans += c*(c-1)//2

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

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

exmax=0

for i in range(n-k+1):
	ex=0
	for j in range(k):
		ex+=plist[i+j]
	if (ex+k)/2 > exmax:
		exmax=(ex+k)/2

print(exmax)


### FIXED CODE ###

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

summax=sum(plist[:k])


for i in range(n-k+1):
	if i == 0:
		temp=summax
	else:
		temp=temp+plist[i+k-1]-plist[i-1]
		if temp>summax:
			summax=temp

print((summax+k)/2)
### BUGGY CODE ###

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

div = True
for i in range(n):
    q = input().split(' ')
    if q[0] == '1':
        div = not div
    elif (q[1] == '1' and div) or (q[1] == '2' and not div):
        s = q[2] + s
    else:
        s = s + q[2]


if div:
    print(s)
else:
    s = ''.join(list(reversed(s)))
    print(s)


### FIXED CODE ###

from collections import deque

s = input()
n = int(input())
ans = deque(s)

div = True
for i in range(n):
    q = input().split(' ')
    if q[0] == '1':
        div = not div
    elif (q[1] == '1' and div) or (q[1] == '2' and not div):
        ans.appendleft(q[2])
    else:
        ans.append(q[2])

if div:
    print(''.join(ans))
else:
    print(''.join(reversed(ans)))
### BUGGY CODE ###

def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t,ans={},{}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    for i in t:
        o,p=t[i]
        if i+d in t: ans[i]=abs(o-t[i+d][0])+abs(p-t[i+d][1])
    q=int(input())
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        for j in range(300):
            if l==r: break
            chk+=ans[l]
            l+=d
        print(chk)

if __name__=="__main__":
    sol()

### FIXED CODE ###

def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t={}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    ans=[0]*(h*w+1)
    for i in range(h*w,d,-1):
        o,p=t[i]
        ans[i-d]=ans[i]+abs(o-t[i-d][0])+abs(p-t[i-d][1])
    q=int(input())
    for i in range(q):
        l,r=map(int,input().split())
        print(ans[l]-ans[r])

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

import numpy as np
from itertools import permutations

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = 0 
    for (x1,y1),(x2,y2) in zip(a,a[1:]):
        dis += ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))**0.5
    re.append(dis)

print(np.average(re))


### FIXED CODE ###

import numpy as np
from itertools import permutations
from math import hypot

n = int(input())

li = []
for _ in range(n):
    i, j = map(int, input().split())
    li.append(np.array([i, j]))

li2 = permutations(li)

re = []
for a in li2:
    dis = 0 
    for (x1,y1),(x2,y2) in zip(a,a[1:]):
        dis += hypot(x1-x2, y1-y2)
    re.append(dis)

print(np.average(re))
### BUGGY CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg)
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=0
    for v in A_pos:
        if v**2<x:
            tmp+=1
    for v in A_neg2:
        if v**2<x:
            tmp+=1

    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
### BUGGY CODE ###

N,K=map(int,input().split())
A=[]
R=abs(N-K)
for i in range(abs(N-K)+1):
    N=abs(N-K)
    R=min(R,N)
print(R)


### FIXED CODE ###

N,K=map(int,input().split())
R=N%K
print(min(abs(K-R),abs(R)))
### BUGGY CODE ###

S = input()
x, y = map(int, input().split())

a = []
t = 0
for s in S:
    if s == "F":
        t += 1
    else:
        a.append(t)
        t = 0
a.append(t)

if a == []:
    if x == y == 0:
        print("Yes")
        exit(0)
    else:
        print("No")
        exit(0)

d = [[a[0],0]]
for k in range(1,len(a)):
    n = []
    if k%2 == 1:
        for e in d:
            n.append([e[0],e[1]+a[k]])
            n.append([e[0],e[1]-a[k]])
    else:
        for e in d:
            n.append([e[0]+a[k],e[1]])
            n.append([e[0]-a[k],e[1]])
    d = n

print("Yes" if [x,y] in d else "No")

### FIXED CODE ###

S = input()
x, y = map(int, input().split())

a = []
t = 0
for s in S:
    if s == "F":
        t += 1
    else:
        a.append(t)
        t = 0
a.append(t)

if a == []:
    if x == y == 0:
        print("Yes")
        exit(0)
    else:
        print("No")
        exit(0)

X = [a[0]]
Y = [0]

for k in range(1,len(a)):
    if k%2 == 0:
        nx = []
        for e in X:
            nx.append(e+a[k])
            nx.append(e-a[k])
        X = list(set(nx))
    else:
        ny = []
        for e in Y:
            ny.append(e+a[k])
            ny.append(e-a[k])
        Y = list(set(ny))

print("Yes" if x in X and y in Y else "No")
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

c = cmb(N*M-2,K-2)

ans = c * (M**2 * (N**2 * (N+1)//2 - N*(N+1)*(2*N+1)//6) + N**2 * (M**2 * (M+1)//2 - M*(M+1)*(2*M+1)//6)) % 1000000007

print(ans)

### FIXED CODE ###

mod = 10**9 + 7
 
 
def comb(n, k):
    x, y = 1, 1
    k = min(k, n - k)
    for i in range(k):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod

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

c = comb(N*M-2,K-2)

ans = c * (M**2 * (N**2 * (N+1)//2 - N*(N+1)*(2*N+1)//6) + N**2 * (M**2 * (M+1)//2 - M*(M+1)*(2*M+1)//6)) % mod

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

import numpy as np


N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
for k in range(K):
    B_acc = np.zeros(N + 1, dtype=int)
    for i in range(N):
        a = A[i]
        B_acc[max(0, i - a)] += 1
        B_acc[min(N, i + a + 1)] -= 1
    B_acc = np.cumsum(B_acc)
    A = B_acc[:-1]
    if all(a == N for a in A):
        break
print(' '.join(map(str, A)))

### FIXED CODE ###

import numpy as np
from numba import njit


@njit
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))