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

import statistics
import sys
input = sys.stdin.readline

Q = int(input())

a = []
a_new = []
b_sum = 0
minima = 0
argmin = 10**10
shift = 0
for i in range(Q):
    ipt = list(map(int, input().split()))
    if len(ipt) == 3:
        a.append(ipt[1])
        argmin_new = statistics.median_low(a)
        if argmin == 10**10:
            argmin = argmin_new
        minima += abs(ipt[1] - argmin_new) + (abs(argmin - argmin_new)) * ((len(a) + 1) % 2)
        b_sum += ipt[2]
        argmin = argmin_new
    else:
        print(argmin, minima + b_sum)

### FIXED CODE ###

def main():
    import sys
    from heapq import heappop, heappush, heappushpop
    input = sys.stdin.readline

    Q = int(input())
    R = [10**9+1]
    L = [10**9+1]
    Rsum = 0
    Lsum = 0
    NL = 0
    NR = 0
    B = 0
    for _ in range(Q):
        query = input().rstrip('\n')
        if query == '2':
            Lmax = -L[0]
            print(Lmax, Lmax * NL - Lsum + Rsum - Lmax * NR + B)
        else:
            _, a, b = query.split()
            a = int(a)
            b = int(b)
            B += b
            if NL != NR:
                Lmax = -L[0]
                Rmin = R[0]
                if a >= Lmax:
                    heappush(R, a)
                    Rsum += a
                    NR += 1
                else:
                    newR = -heappushpop(L, -a)
                    heappush(R, newR)
                    Rsum += newR
                    Lsum += a - newR
                    NR += 1
                    Lmax = -L[0]
            else:
                Rmin = R[0]
                if a <= Rmin:
                    heappush(L, -a)
                    Lsum += a
                    NL += 1
                else:
                    newL = heappushpop(R, a)
                    heappush(L, -newL)
                    Lsum += newL
                    Rsum += a - newL
                    NL += 1


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

n = int(input())

_list = []
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    _list.append([a, b, c])

for i in range(n - 1):
    num = i
    time = 0

    while num < n - 1:
        c, s, f = _list[num]

        if num == i:
            time += s + c
            num += 1
            continue

        while True:
            wait = s - time
            if wait >= 0:
                time += wait + c
                break

            s += f

        num += 1

    print(time)


print(0)


### FIXED CODE ###

n = int(input())

_list = []
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    _list.append([a, b, c])


for i in range(n - 1):
    num = i
    time = 0

    while num < n - 1:
        c, s, f = _list[num]

        if num == i:
            time += s + c
            num += 1
            continue

        while True:
            wait = s - time

            if wait >= 0:
                time += wait + c
                break

            test = (wait * -1) // f
            s += int(f * test)

            if s - time < 0:
                s += f

        num += 1

    print(time)


print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
import sys


n,k = map(int, sys.stdin.readline().rstrip().split())
h = [0] + list(map(int, sys.stdin.readline().rstrip().split()))

dp = [sys.maxsize] * (n+1)
dp[0], dp[1] = [0, 0]
for i in range(1,n):
  for j in range(1,min(k+1, n+1-i)):
    dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[n])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import sys
import numpy as np

n,k = map(int, sys.stdin.readline().rstrip().split())
h = np.array(list(map(int, sys.stdin.readline().rstrip().split())))

dp = np.zeros(n, dtype=np.int)

for i in range(1,n):
  if i < k:
    dp[i] = np.min(dp[:i] + np.abs(h[i]-h[:i]))
  else:
    dp[i] = np.min(dp[i-k:i] + np.abs(h[i]-h[i-k:i]))

print(dp[n-1])
### BUGGY CODE ###

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

[N, K] = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

max_index = 0
max_sum = 0
for i in range(len(P)-(K-1)):
    sum_P = sum(P[i:i+K])
    if sum_P > max_sum:
        max_sum = sum_P
        max_index = i

#print(max_sum)
#print(max_index)

# 隣接したK個のリスト
kk = P[max_index: max_index+K]

# kの期待値を計算
max_kk = max(kk)
dp = [0]
for i in range(1, max_kk+1):
    dp.append(dp[i-1] + i)
#print(dp)

ans = 0
for k in kk:
    ans += dp[k]/k

print(ans)

### FIXED CODE ###

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

#def f(x):
#    if x == 1:
#        return 1
#    else:
#        return f(x-1) + x

[N, K] = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

max_index = 0
now_sum = sum(P[:K])
max_sum = now_sum
for i in range(1, len(P)-(K-1)):
    now_sum -= P[i-1]
    now_sum += P[i+K-1]
    #sum_P = sum(P[i:i+K])
    if now_sum > max_sum:
        max_sum = now_sum
        max_index = i

#print(max_sum)
#print(max_index)

# 隣接したK個のリスト
kk = P[max_index:max_index+K]

# kの期待値を計算
max_kk = max(kk)
dp = [0]
for i in range(1, max_kk+1):
    dp.append(dp[i-1] + i)
#print(dp)

ans = 0
for k in kk:
    ans += dp[k]/k

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

from collections import defaultdict

def make_divisors(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)
    
    divisors.sort()
    return divisors

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

div1 = set(make_divisors(a[0]))
div2 = set(make_divisors(a[1]))
common = div1 | div2

cnt = defaultdict(int)
for i in range(n):
    for j in common:
        if a[i] % j == 0:
            cnt[j] += 1

for k, v in sorted(cnt.items(), reverse=True):
    if v == n or v == n-1:
        print(k)
        exit()


### FIXED CODE ###

from collections import defaultdict

def make_divisors(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)
    
    divisors.sort()
    return divisors

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

div1 = set(make_divisors(a[0]))
div2 = set(make_divisors(a[1]))
common = div1 | div2

cnt = defaultdict(int)
for i in range(n):
    for j in common:
        if a[i] % j == 0:
            cnt[j] += 1

for k, v in sorted(cnt.items(), reverse=True):
    if v == n or v == n-1:
        print(k)
        exit()
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

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

L,R = list(map(int, input().split()))


MOD=[0] * (2019*2019)

def myidx(i,j):
    return i * 2019 + j

for i in range(2019):
    for j in range(2019):
        idx = myidx(i,j)
        MOD[idx] = (i*j) % 2019

for i in range(2019):
    idx = myidx(i,i)
    MOD[idx] = 2019

MMM = []
Lmod = L % 2019
Rmod = R % 2019

if L+2019 <= R:
    for i in range(2019):
        for j in range(i+1,2019):
            idx = myidx(i,j)
            MMM.append(MOD[idx])
elif Lmod <= Rmod:
    for i in range(Lmod, Rmod+1):
        for j in range(i+1, Rmod+1):
            idx = myidx(i,j)
            MMM.append(MOD[idx])

elif Lmod > Rmod:
    for i in list(range(0,Rmod+1)) + list(range(Lmod, 2019)):
        for j in list(range(i+1,Rmod+1)) + list(range(max(Lmod,i+1), 2019)):
            idx = myidx(i,j)
            MMM.append(MOD[idx])

MMM=list(set(MMM))
MMM.sort()
print(MMM.pop(0))


### FIXED CODE ###

L,R = list(map(int, input().split()))

MOD=[0] * (2019*2019)

def myidx(i,j):
    return i * 2019 + j

for i in range(2019):
    for j in range(i+1,2019):
        idx = myidx(i,j)
        MOD[idx] = (i*j) % 2019

#for i in range(2019):
#    idx = myidx(i,i)
#    MOD[idx] = 2019

MMM = []
MIN = 2019
Lmod = L % 2019
Rmod = R % 2019

if L+2019 <= R:
    for i in range(2019):
        for j in range(i+1,2019):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])
elif Lmod <= Rmod:
    for i in range(Lmod, Rmod+1):
        for j in range(i+1, Rmod+1):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])

elif Lmod > Rmod:
    for i in list(range(0,Rmod+1)) + list(range(Lmod, 2019)):
        for j in list(range(i+1,Rmod+1)) + list(range(max(Lmod,i+1), 2019)):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])

#MMM=list(set(MMM))
#MMM.sort()
#print(MMM.pop(0))
print(MIN)
### BUGGY CODE ###

# 2019/07/23

input=open(0).readline
n,k=map(int,input().split())
res=[]
for i in range(n):
    a,b=map(int,input().split())
    res+=[a]*b
res.sort()
print(res[k-1])

### FIXED CODE ###

from heapq import heappop,heappush

input=open(0).readline
n,k=map(int,input().split())
res={}
for i in range(n):
    a,b=map(int,input().split())
    res[a]=res.get(a,0)+b

que=[]
for key,val in res.items():
    heappush(que,(key,val))

while k:
    key,val=heappop(que)
    if val>=k:
        print(key)
        exit()
    k-=val
### BUGGY CODE ###

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

A=[S]*K
if S==10**9:
    A=A+[1]*(N-K)
else:
    A=A+[S+1]*(N-K)
s=""
for i in range(N):
    s=s+str(A[i])+" "
print(s)

### FIXED CODE ###

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

A=[S]*K
if S==10**9:
    A=A+[1]*(N-K)
else:
    A=A+[S+1]*(N-K)

print(*A)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
B = [0] * M
C = [0] * M

X = []
for i in range(M):
    B[i], C[i] = map(int, input().split())
    Y = [C[i]] * B[i]
    X.extend(Y)

Z = A + X
Z.sort(reverse=True)
print(sum(Z[:N]))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
CB = []
for i in range(M):
    B, C = list(map(int, input().split()))
    CB.append([C, B])
 
A.sort()
A.reverse()
CB.sort()
CB.reverse()
 
ans = 0
a_index = 0
cb_index = 0
f = 0
 
while True:
    if f == 1 or A[a_index] >= CB[cb_index][0]:
        ans += A[a_index]
        a_index += 1
        N -= 1
        if N == 0:
            break
    else:
        if N <= CB[cb_index][1]:
            ans += CB[cb_index][0] * N
            break
        else:
            ans += CB[cb_index][0] * CB[cb_index][1]
            N -= CB[cb_index][1]
            cb_index += 1
            if len(CB) == cb_index:
              f = 1
 
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
cnt = 0
while True:
    s = [l for l in s if l != s[0]]
    cnt += 1
    if len(s) == 0:
        break

print(cnt)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
s.sort()
cnt = 1

for i in range(1, n):
    if s[i] != s[i-1]:
        cnt += 1
    
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-float("inf")
for i in range(n):
  count=0
  start=i+1
  for j in range(k):
    count+=c[p[start-1]-1]
    start=p[start-1]
    ans=max(ans,count)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ttl=[]
cnt=[]
count=0
for i in range(n):
  nxt=i+1
  grp=[]
  count=0
  pnt=[]
  pnt.append(0)
  for j in range(n):
    nxt=p[nxt-1]
    pnt.append(pnt[j]+c[nxt-1])
    count+=1
    if nxt==i+1:
      del pnt[0]
      ttl.append(pnt)
      cnt.append(count)
      break
ans=[]
for i in range(n):
  peak=ttl[i].index(max(ttl[i]))
  if k<=cnt[i]:
    ans.append(max(ttl[i][:k]))
  else:
    if ttl[i][-1]<0:
      ans.append(ttl[i][peak])
    else:
      if k%cnt[i]==0:
        ans.append(((k-peak-1)//cnt[i])*ttl[i][-1]+ttl[i][peak])
      else:
        ans.append(max((k//cnt[i])*ttl[i][-1]+max(ttl[i][0:k%cnt[i]]),((k-peak-1)//cnt[i])*ttl[i][-1]+ttl[i][peak]))
print(max(ans))
### BUGGY CODE ###

def xor(hoge):
    res = hoge[0]
    for i in range(1,len(hoge)):
        res = res ^ hoge[i]
    return res

# O(n^2) 解法
def debug():
    N = int(input())
    A = list(map(int,input().split()))
    cnt = 0
    note = []
    for i in range(N):
        for j in range(i+1,N+1):
            part = A[i:j]
            res = xor(part)
            if res == sum(part):
                print(i,j)
                cnt += 1
                part_bin = [format(e,"b") for e in part]
                note.append(part_bin)
    print(cnt)

#---------メインコード----------#

# 2次元リストのsetをとる関数を用意
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    import sys
    sys.setrecursionlimit(10**9)
    N = int(input())
    A = list(map(int,input().split()))
    def syakutori(l=0,r=0,res=0,sum_=0,ans=[]):
        if l == N and r == N:
            return len(get_unique_list(ans))
        note = r
        for i in range(r,N):
            if res ^ A[i] == sum_ + A[i]:
                r += 1
                res += A[i]
                sum_ += A[i]
            else:
                break
        length = r - l
        f = note == r
        if f is False:
            for i in range(l,r+1):
                for j in range(i+1,r+1):
                    ans.append([i,j])
        #print(l,r)
        if length == 0:
            r += 1
        else:
            res -= A[l]
            sum_ -= A[l]
        return syakutori(l+1,r,res,sum_,ans)
    ans = syakutori()
    print(ans)

main()

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
r = 0; sum_ = 0; res = 0; ans = 0
for l in range(N+1):
    for i in range(r,N):
        if res ^ A[i] == sum_ + A[i]:
            r += 1
            res += A[i]
            sum_ += A[i]
        else:
            break
    length = r - l
    ans += length
    if length == 0:
        r += 1
    else:
        res -= A[l]
        sum_ -= A[l]

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

n = int(input())

l = []

for i in range(n):
  l.append(int(input()))

m = max(l)
  
for i in range(n):
  tmp = l.pop(i)
  
  if tmp != m:
    print(m)
    l.insert(i,tmp)
    continue
  
  print(max(l))
  l.insert(i,tmp)
  

### FIXED CODE ###

n = int(input())

l = []

for i in range(n):
  l.append(int(input()))

m = max(l)

if l.count(m) >= 2:
  for i in range(n):
    print(m)
  exit()

index = l.index(m)  

l.pop(index)

for i in range(n):
  if i == index:
  	print(max(l))
  else:
    print(m)
### BUGGY CODE ###

import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
c=collections.Counter(a)
if len(c)<k:
    print(ans)
    exit()

for i in range(1,-k+len(c)+1):
    ans+=c.most_common()[-i][1]
print(ans)


### FIXED CODE ###

import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
c=collections.Counter(a)
if len(c)<k:
    print(ans)
    exit()
l=c.most_common()
for i in range(1,-k+len(c)+1):
    ans+=l[-i][1]
print(ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
P = inpl()

ave = []
for p in P:
    ave.append((p+1)/2)

ans = 0
for i in range(n-k+1):
    tmp = 0
    for j in range(k):
        tmp += ave[i+j]
    ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
P = inpl()

ave = []
for p in P:
    ave.append((p+1)/2)
    
pre = sum(ave[:k])
ans = pre
for i in range(1,n-k+1):
    now = pre - ave[i - 1] + ave[i + k - 1]
    pre = now
    ans = max(ans,now)

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

H, W, D = map(int, input().split())
mp = {}

def ipt():
    for x in range(H):
        A = list(map(int, input().split()))
        for y in range(W):
            mp[A[y]] = (x, y)


ipt()
Q = int(input())

def get_dist(prev, x):
    dx = mp[x][0] - mp[prev][0]
    dy = mp[x][1] - mp[prev][1]
    return abs(dx) + abs(dy)


for i in range(Q):
    L, R = map(int, input().split())
    ans = 0
    for x in range(L, R, D):
        ans += get_dist(x, x+D)
    print(ans)

### FIXED CODE ###

H, W, D = map(int, input().split())
mp = {}

def ipt():
    for x in range(H):
        A = list(map(int, input().split()))
        for y in range(W):
            mp[A[y]] = (x, y)


ipt()
Q = int(input())

def get_dist(prev, x):
    dx = mp[x][0] - mp[prev][0]
    dy = mp[x][1] - mp[prev][1]
    return abs(dx) + abs(dy)


dist = [0 for i in range(H*W+1)]
for i in range(0, D):
    tmp = 0
    for x in range(1+i, H*W-D+1, D):
        tmp += get_dist(x, x+D)
        dist[x+D] = tmp


for i in range(Q):
    L, R = map(int, input().split())
    print(dist[R]-dist[L])
### BUGGY CODE ###

#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict
answer = 0
#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")
class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()


def DFS(G, visit, W, Wlist, node, K):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, visit, W, Wlist, i, K)
			Wlist[node].append(W[i] + 1)

	val = 0
	for i in Wlist[node]:
		if i == K and node != 0:
			global answer
			answer += 1
		else:
			val = max(val, i)
	W[node] = val

#処理内容
def main():
	N, K = getlist()
	a = getlist()
	G = Graph()
	for i in range(1, N):
		G.add_edge(i, a[i] - 1)
		G.add_edge(a[i] - 1, i)
	ans = 0
	if a[0] != 1:
		ans += 1
	if K == 1:
		for i in range(1, N):
			if a[i] != 1:
				ans += 1
		print(ans)
		return

	#DFS
	W = [0] * N
	Wlist = [[] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	
	DFS(G, visit, W, Wlist, 0, K)
	print(ans + answer)


if __name__ == '__main__':
	main()

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict
answer = 0
#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")
class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()


def DFS(G, visit, W, Wlist, node, K):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, visit, W, Wlist, i, K)
			Wlist[node].append(W[i] + 1)

	val = 0
	for i in Wlist[node]:
		if i == K and node != 0:
			global answer
			answer += 1
		else:
			val = max(val, i)
	W[node] = val

#処理内容
def main():
	N, K = getlist()
	a = getlist()
	G = Graph()
	for i in range(1, N):
		G.add_edge(i, a[i] - 1)
		G.add_edge(a[i] - 1, i)
	ans = 0
	if a[0] != 1:
		ans += 1
	if K == 1:
		for i in range(1, N):
			if a[i] != 1:
				ans += 1
		print(ans)
		return

	#DFS
	W = [0] * N
	Wlist = [[] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	
	DFS(G, visit, W, Wlist, 0, K)
	print(ans + answer)


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

# D
# Multiple of 2019

s = input()

d = len(s)

ans = 0

for j in range(d):
    for i in range(j):
        _tmp = int(s[i:j+1])
        if _tmp % 2019 == 0:
            ans +=1

print(ans)

### FIXED CODE ###

# D
# Multiple of 2019
import itertools

s = input()[::-1]

d = len(s)

# _list = [None]*d
_map = [0]*2019
_map[0] = 1

ans = 0
j,_ = 1,0

for i in s:
    _ += int(i) * j
    _tmp = _ % 2019
    j = (j*10)%2019
    _map[_tmp] += 1
    
for _l in _map:
    ans += _l * (_l - 1) / 2
    
print(int(ans))
### BUGGY CODE ###

import math
X= int(input())
 
Bp = -1*math.floor(X**0.2)
Bn = 0
while True:
    Bp += 1
    A = (X+Bp**5)**0.2
    if A == int(A):
        print(int(A),Bp)
        exit()

### FIXED CODE ###

import math

X= int(input())

for A in range(-120,121):
    for B in range(-120,A+1):
        if A**5-B**5  == X:
            print(A,B)
            exit()
### BUGGY CODE ###

from fractions import *

K = int(input())

ans = 0
for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if i == j and j == k and k == i:
                ans += i
            elif i != j and j != k and k != i:
                ans += gcd(gcd(i, j), gcd(j, k)) * 6
            else:
                ans += gcd(gcd(i, j), gcd(j, k)) * 3

print(ans)

### FIXED CODE ###

from math import *

K = int(input())

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        tmp = gcd(i, j)
        for k in range(1, K+1):
            ans += gcd(tmp, k)

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

import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  global ts
  visited[node-1] = True
  first_order[node-1] = ts
  ts += 1
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    dfs(next_node)
  
  last_order[node-1] = ts
  ts += 1

N, Q = map(int, input().split())
tree = dd(list)
operation = []
counter = [0] * N
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))

for p, x in operation:
  visited = [False] * N
  first_order = [0] * N
  last_order = [0] * N
  ts = 0
  dfs(1)
  for i in range(N):
    if first_order[p-1] <= first_order[i-1] and last_order[i-1] <= last_order[p-1]:
      counter[i-1] += x
print(*counter)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
sys.setrecursionlimit(4100000)

def dfs(node):
  visited[node-1] = True
  
  for next_node in tree[node]:
    if visited[next_node-1]:
      continue
    counter[next_node-1] += counter[node-1]
    dfs(next_node)

N, Q = map(int, input().split())
tree = dd(list)
visited = [False] * N
counter = [0] * N
operation = []
for _ in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b) 
  tree[b].append(a) 
for _ in range(Q):
  operation.append(tuple(map(int, input().split())))
  
for p, x in operation:
  counter[p-1] += x
dfs(1)
print(*counter)