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

N,Q=[int(s) for s in input().split()]
edge=[set() for _ in range(N)]
value=[0 for _ in range(N)]
for i in range(N-1):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1)
  edge[y-1].add(x-1)
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  value[x-1]+=y
stack=[0]
while stack:
  vrt=stack.pop(0)
  for to in edge[vrt].copy():
    stack.append(to)
    value[to]+=value[vrt]
    edge[vrt].discard(to)
    edge[to].discard(vrt)
print(*value)

### FIXED CODE ###

N,Q=[int(s) for s in input().split()]
#辺でつながれた場所をすべてリストアップ
con_list=[set() for s in range(N+1)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  con_list[a].add(b)
  con_list[b].add(a)

v_list=[0 for s in range(N+1)]
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  v_list[x]+=y

position=1 #現在位置
counter=v_list[1] #カウンター
ans_list=[0 for s in range(N+1)] #答え
ans_list[1]=counter 
vertex_num=1 #訪れた場所の数
oya_list=[-1 for s in range(N+1)] #親に戻るためのリスト

while vertex_num<N:
  #まだ行っていない子があるか？
  if len(con_list[position])>0:
    x=con_list[position].pop()
    con_list[x].remove(position) #xの行先から親を消す
    oya_list[x]=position
    position=x
    counter+=v_list[position] #カウンターの更新
    ans_list[position]=counter
    vertex_num+=1
  else: #行き先がないなら戻る
    position=oya_list[position]
    counter=ans_list[position] #カウンターを戻す
print(*ans_list[1:])
### BUGGY CODE ###

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)


def divisor(n):
    l = []
    i = 1
    while True:
        if n % i == 0:
            l.append(i)
            if i * i != n:
                l.append(n / i)
        if i * i >= n:
            break
        i += 1
    return sorted(l)


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

gcd_of_all = gcd(a[0], a[1])
for i in range(2, n):
    gcd_of_all = gcd(gcd_of_all, a[i])

if gcd_of_all != 1:
    print("not coprime")
    exit()

s = set()

for i in range(n):
    l = divisor(a[i])
    for j in range(len(l)):
        if l[j] == 1:
            continue
        if l[j] in s:
            print("setwise coprime")
            exit()
        else:
            s.add(l[j])

print("pairwise coprime")
exit()


### FIXED CODE ###

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)


def divisor(n):
    l = []
    i = 1
    while True:
        if n % i == 0:
            l.append(i)
            if i * i != n:
                l.append(n / i)
        i += 1
        if i * i >= n:
            break
    return sorted(l)


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

gcd_of_all = gcd(a[0], a[1])
for i in range(2, n):
    gcd_of_all = gcd(gcd_of_all, a[i])

if gcd_of_all != 1:
    print("not coprime")
    exit()

s = set()

for i in range(n):
    l = divisor(a[i])
    for j in range(len(l)):
        if l[j] == 1:
            continue
        if l[j] in s:
            print("setwise coprime")
            exit()
        else:
            s.add(l[j])

print("pairwise coprime")
### BUGGY CODE ###


n, k = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]

last = 1
for i in range(k):
    last = last * arr[i]

for i in range(k, len(arr)):
    curr = (last*arr[i])//arr[i-k]
    if curr>last:
        print('Yes')
    else:
        print('No')
    last= curr
    
    

### FIXED CODE ###

import math
n, k = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
arr = [math.log10(x) for x in arr]


last = 0
for i in range(k):
    last += arr[i]

for i in range(k, len(arr)):
    curr = (last + arr[i]) - arr[i-k]
    if curr>last:
        print('Yes')
    else:
        print('No')
    last= curr
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
s = sorted(x)
for i in range(n):
    k = x.pop(0)
    if s.index(k) < n//2:
        print(s[n//2])
    else:
        print(s[n//2-1])

### FIXED CODE ###

from math import *

n = int(input())

a = [int(x) for x in input().split()]

a_sort = sorted(a)

median_right = a_sort[floor(len(a_sort) / 2)]
median_left = a_sort[floor(len(a_sort) / 2) - 1]

for i in range(len(a)):
	if a[i] > median_left:
		print(median_left)
	else:
		print(median_right)
### BUGGY CODE ###

def function(n):
  string = str(n)
  for i in range(len(string) - 1):
    if abs(int(string[i]) - int(string[i + 1])) > 1:
      return False
  return True

k = int(input())
ans = []
n = 1
while len(ans) < k:
  if function(n):
    ans.append(n)
  n += 1

print(ans[-1])

### FIXED CODE ###

def function(n):
  string = str(n)
  for i in range(len(string) - 1):
    error = int(string[i]) - int(string[i + 1])
    if error > 1:
      return i + 1, error
    elif error < -1:
      return i, abs(error)
  return -1, 0
 
k = int(input())
ans = []
n = 1
while len(ans) < k:
  m, error = function(n)
  if m == -1:
    ans.append(n)
    n += 1
  else:
    n = n + (error - 1) * (10 ** (len(str(n)) - m - 1)) - n % (10 ** (len(str(n)) - m - 1))
print(ans[-1])
### BUGGY CODE ###

n=int(input())
p=1
for i in range(1,n+1):
   p=p*i 
print(p%(10**9+7))


### FIXED CODE ###

n=int(input())
p=1
m=10**9+7
for i in range(1,n+1):
   p=p*i%m
print(p%m)
### BUGGY CODE ###

x, y = map(int, input().split())
if x % y == 0:
    print("-1")
for i in range(x, 1000000000000000000, x):
    if i % y != 0:
        print(i)
        exit()

### FIXED CODE ###

x, y = map(int, input().split())
if x % y == 0:
    print("-1")
    exit()
print(x)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    newA=list(A)
    if i in newA:
        while i in newA:
            newA.remove(i)
        print(N-1-len(newA))
    else:
        print(N-1-len(newA))



### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import collections
new_A=collections.Counter(A)
for i in B:
    print(new_A[i])
### BUGGY CODE ###

a,b,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=[list(map(int,input().split())) for _ in range(m)]
aa=[]

for i in range(m):
  aa.append(a[x[i][0]-1]+b[x[i][1]-1]-x[i][2])
  aa.append(min(a)+min(b))

print(min(aa))

### FIXED CODE ###

import sys
input = sys.stdin.readline

a,b,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=[list(map(int,input().split())) for _ in range(m)]

ans=min(a)+min(b)
for i in range(m):
  ans=min(ans,(a[x[i][0]-1]+b[x[i][1]-1]-x[i][2]))

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

def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    i = 0
    for i in range(K):
        # まず進む
        now = A[now]-1
        # 道順登録
        if now not in set(history): # ここが線形探索なのが遅い
            history.append(now)
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()


### FIXED CODE ###

def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    isVisited = [False for i in range(N)]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        #if now not in history:
        if isVisited[now] == False:
            history.append(now)
            isVisited[now] = True
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()
### BUGGY CODE ###

import sys
import numpy as np
N,M = map(int , sys.stdin.readline().split())
A=[map(int , input().split()) for _ in range(M)]
data = np.zeros(N)
for L,R in A:
	data[L-1:R] +=1
print(np.sum(data == M)) 

### FIXED CODE ###

N,M = map(int , input().split())
A=[map(int , input().split()) for _ in range(M)]
L_min = 0
R_max = N
for L,R in A:
	L_min = max(L_min , L)
	R_max = min(R_max , R)

if R_max - L_min+1 >=0:
	print(R_max - L_min+1)
else:
	print(0)
### BUGGY CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

x = INT()
flag = [False]

def dfs(cur):
    if cur==x:
        flag[0] = True
        return 0
    if cur>x:
        return 0
    dfs(cur+100)
    dfs(cur+101)
    dfs(cur+102)
    dfs(cur+103)
    dfs(cur+104)
    dfs(cur+105)

dfs(0)
if flag[0]:
    print(1)
else:
    print(0)

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**9)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

x = INT()

for i in range(1,10**6+1):
    if i*100<=x<=i*105:
        print(1)
        exit()
print(0)
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]

chk=True

for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//gcd(lcm,A[i])
  if lcm>10**100000:
    chk=False
    break

if chk:
  ans=0
  for i in range(n):
    ans=(ans+lcm//A[i])%mod
  print(ans)
else:
  ans=0
  mult=1
  for a in A:
    mult=(mult*a)%mod
  for a in A:
    ans=(ans+mult*pow(a,mod-2,mod))%mod
  print(ans)

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]

chk=True

for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//gcd(lcm,A[i])
  if lcm>10**50000:
    chk=False
    break

if chk:
  ans=0
  for i in range(n):
    ans=(ans+lcm//A[i])%mod
  print(ans)
else:
  ans=0
  mult=1
  for a in A:
    mult=(mult*a)%mod
  for a in A:
    ans=(ans+mult*pow(a,mod-2,mod))%mod
  print(ans)
### BUGGY CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,10**4+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])


### FIXED CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])
### BUGGY CODE ###

n = int(input())
l = []
l[:] = map(int,input().split())
l.sort()

c = 0
for i in range(0,n-2):
    for j in range(i+1, n-1):
        ab = l[i]+l[j]
        k=n-1
        while (k>=j+1):
            if(ab<=l[k]):
                k-=1
            else:
                break
        c+=(k-j)
print(c)


### FIXED CODE ###

from bisect import bisect_right

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # bisect_left(a, x): x を a に挿入できる点を返す
        # cの最大値は a+b-1
        k = bisect_right(l, ab-1, j+1, n)
        count += k-(j+1)
print(count)
### BUGGY CODE ###

N = int(input())
mod_list = [i for i in range(1, N)]
output = (N - 1) / 2 * (1 + N - 1)

print(int(output))

### FIXED CODE ###

N = int(input())
output = ((N - 1) * N) // 2
 
print(int(output))
### BUGGY CODE ###

"""
注意点：ACしていないWAはペナルティ数とはカウントされない
      また、ACの後にペナルティしたものはカウントされない
データ構造：
  WA:dict形式でカウントアップ
  AC:配列で末尾に挿入
一通り舐めた後AD配列をforで回してペナルティ数合計するか？
"""

N,M = list(map(lambda x: int(x), input().split()))
results = []
for n in range(M):
  results.append(input().split())


l = [(str(n + 1) , 0) for n in range(N)]
wa_count = dict(l)
ac_list = []
answer = 0

for p, s in results:
  if s == 'WA':
    wa_count[p] += 1
  else:
    if p not in ac_list:
      answer += wa_count[p]
      ac_list.append(p)
    

print(len(ac_list), answer)


### FIXED CODE ###

"""
注意点：ACしていないWAはペナルティ数とはカウントされない
      また、ACの後にペナルティしたものはカウントされない
データ構造：
  WA:dict形式でカウントアップ
  AC:配列で末尾に挿入
一通り舐めた後AD配列をforで回してペナルティ数合計するか？
"""

N,M = list(map(lambda x: int(x), input().split()))
wa_count = [0] * N
ac_list = [False] * N
answer = 0

for _ in range(M):
  p,s = input().split()
  p = int(p)
  if s == 'WA':
    wa_count[p-1] += 1
  if s == 'AC' and ac_list[p-1] == False:
    answer += wa_count[p-1]
    ac_list[p-1] = True

ac_count = ac_list.count(True)

print(ac_count, answer)
### BUGGY CODE ###


import copy

h, w = map(int , input().split() )

board = [input() for _ in range(h)]

left = [ [0]*w for _ in range(h)] 
right = copy.deepcopy(left )        #いくつ右のマスを照らせるか
down = copy.deepcopy(left)
up = copy.deepcopy(left)



for hi in range(h):
    for wi in range(w):

        if board[hi][wi] == '.':
            left[hi][wi] = 1
            up[hi][wi] = 1

            if 1 <= wi:
                left[hi][wi] += left[hi][wi-1]

            if 1 <= hi:
                up[hi][wi] += up[hi-1][wi]


        if board[hi][w-wi-1] =='.':
            right[hi][w-wi-1] = 1

            if 1<=wi:
                right[hi][w-wi-1] += right[hi][w-wi] 

        if board[h-hi-1][wi] == '.':
            down[h-hi-1][wi] = 1

            if 1 <= hi:
                down[h-hi-1][wi] += down[h-hi][wi]


def dbcheck():
    print()
    tag = ["r","l","d","u"]
    for t,x in zip(tag,[right,left,down,up]):
        print(t)
        for row in x:
            print(row)
        print()


#dbcheck()

ans = 0
for i in range(h):
    for j in range(w):
        t = right[i][j]
        t += left[i][j]
        t += up  [i][j]
        t += down[i][j]
        t -= 3
        ans = max(ans,t)

print(ans)

### FIXED CODE ###


import copy

h, w = map(int , input().split() )

board = [input() for _ in range(h)]

left = [ [0]*w for _ in range(h)] 
right = copy.deepcopy(left )        #いくつ右のマスを照らせるか
down = copy.deepcopy(left)
up = copy.deepcopy(left)



for hi in range(h):
    for wi in range(w):

        if board[hi][wi] == '.':
            left[hi][wi] = 1
            up[hi][wi] = 1

            if 1 <= wi:
                left[hi][wi] += left[hi][wi-1]

            if 1 <= hi:
                up[hi][wi] += up[hi-1][wi]


        if board[hi][w-wi-1] =='.':
            right[hi][w-wi-1] = 1

            if 1<=wi:
                right[hi][w-wi-1] += right[hi][w-wi] 

        if board[h-hi-1][wi] == '.':
            down[h-hi-1][wi] = 1

            if 1 <= hi:
                down[h-hi-1][wi] += down[h-hi][wi]


def dbcheck():
    print()
    tag = ["r","l","d","u"]
    for t,x in zip(tag,[right,left,down,up]):
        print(t)
        for row in x:
            print(row)
        print()


#dbcheck()

ans = 0
for i in range(h):
    for j in range(w):
        t = right[i][j] + left[i][j] + up[i][j] + down[i][j]
        t -= 3
        ans = max(ans,t)

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

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

for j in range(m):
    b, c = map(int, input().split())
    test.extend([c for i in range(b)])
test.sort(reverse=True)
print(sum(test[:n]))

### FIXED CODE ###

from collections import defaultdict

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

test_dict = defaultdict(int)

for j in test:
    test_dict[j] += 1

for k in range(m):
    b, c = map(int, input().split())
    test_dict[c] += b

count = 0
sum_val = 0
for l in sorted(test_dict, reverse=True):
    if n-count>0:
       sum_val += l * min(test_dict[l], n-count)
       count += min(test_dict[l], n-count)
    else:
       break
print(sum_val)
### BUGGY CODE ###

n,k=map(int, input().split())
p = list(map(int, input().split()))
a = []
for i in range(n-k+1):
    a.append(sum(p[i:i+k]))
print((max(a)+k)/2)


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
r=[0]
for i in range(n):
    r.append(r[i]+p[i])
p=0
for i in range(k,n+1):
    p=max(p,r[i]-r[i-k])
print('{:.10f}'.format((p+k)/2))
### BUGGY CODE ###

from bisect import bisect_left
from collections import defaultdict
N = int(input())
points = list(tuple(map(int,input().split())) for _ in range(N))

xty = defaultdict(list)
ytx = defaultdict(list)
for x,y in points:
    xty[x].append(y)
    ytx[y].append(x)

area = 0
X = set()
Y = set()

for x,y in points:
    if x in X or y in Y:
        continue

    stack_x = [x]
    stack_y = [y]

    dx = set()
    dy = set()

    while stack_x or stack_y:

        while stack_x:
            x = stack_x.pop()
            dx.add(x)
            for y in xty[x]:
                if y not in dy:
                    stack_y.append(y)

        while stack_y:
            y = stack_y.pop()
            dy.add(y)
            for x in ytx[y]:
                if x not in dx:
                    stack_x.append(x)
    X |= dx
    Y |= dy
    area += len(dx)*len(dy)

print(area-len(points))

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
points = list(tuple(map(int,input().split())) for _ in range(N))

X = sorted(set(x for x,y in points))
Y = sorted(set(y for x,y in points))

points = set((bisect_left(X, x), bisect_left(Y, y)) for x,y in points)

xty = [list() for _ in range(len(X))]
ytx = [list() for _ in range(len(Y))]
for x,y in points:
    xty[x].append(y)
    ytx[y].append(x)

area = 0
visited = set()

for p in points:
    if p in visited:
        continue

    stack = [p]

    dx = set()
    dy = set()

    while stack:
        x,y = stack.pop()
        visited.add((x,y))
        if x not in dx:
            for yy in xty[x]:
                if yy != y:
                    stack.append((x,yy))
            dx.add(x)
        if y not in dy:
            for xx in ytx[y]:
                if xx != x:
                    stack.append((xx,y))
            dy.add(y)
    area += len(dx)*len(dy)

print(area-len(points))
### BUGGY CODE ###

_ = int(input())
a = list(map(int, input().split()))
tot = 0
for i in set(a):
    if i > a.count(i):
        tot += a.count(i)
    else:
        tot += a.count(i) - i
print(tot)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
for k,v in d.items():
    if k <= v:
        n -= k
print(n)
### BUGGY CODE ###

import sys
INFTY = 1<<30
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and self.a[l] > self.a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and self.a[r] > self.a[largest]:
            largest = r
        if largest != i:
            self.a[i], self.a[largest] = self.a[largest], self.a[i]
            self.maxHeapify(largest)

    def extract(self):
        if self.h < 1:
            return -INFTY
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -INFTY
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [None] * (2000000 + 1)
    x = MaxHeap(a, 0)
    ret = [None] * (2000000 + 1)
    i = 0
    coms = sys.stdin.readlines()
    for com in coms:
        if com[0] == "i":
            k = int(com.split()[1])
            x.insert(k)
        elif com[0:2] == "ex":
            ret[i] = x.extract()
            i += 1
        else:
            sys.stdout.write("\n".join([str(s) for s in ret[:i]]))
            print()


    

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
bc=[map(int, input().split()) for _ in range(Q)]
b,c=[list(i) for i in zip(*bc)]

for i in range(Q):
  A=[c[i] if x==b[i] else x for x in A]
  print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans+=a
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  key=L[B]
  L[C]+=key
  ans+=key*(C-B)
  L[B]=0
  print(ans)
### BUGGY CODE ###

N, K, Q = list(map(int, input().split()))
P_list = [K for _ in range(N)]

for _ in range(Q):
    win = int(input()) -1
    P_list = list(map(lambda x:x-1, P_list))
    P_list[win] += 1


for i in range(N):
    if P_list[i] > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K, Q = list(map(int, input().split()))
P_list = [K for _ in range(N)]

P_list = list(map(lambda x:x-Q, P_list))


for _ in range(Q):
    a = int(input())-1
    P_list[a] += 1

for i in range(N):
    if P_list[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from sys import stdin
import math
from operator import itemgetter
readline = stdin.readline

def main():
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(int(readline()))]
    xy.sort()
    root = int(math.sqrt(len(xy)))
        
    index = [(s[0], t[0]) for s,t in zip(xy[::root], xy[root - 1::root] + [(float('inf'),float('inf'))])]
    
    xy = [sorted(xy[i:i+root], key=itemgetter(1,0)) for i in range(0,len(xy),root)]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i, (s, t) in enumerate(index):
            if sx <= t and s <= tx:
                for xyi in xy[i]:
                    if sy <= xyi[1] <= ty and sx <= xyi[0] <=tx:
                        ret.append(xyi[2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()
main()

### FIXED CODE ###

from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(int(readline()))]
    xy.sort()
    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i+root], key=itemgetter(1)) for i in range(0,len(xy),root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()
main()
### BUGGY CODE ###

n = int(input())
l = sorted(map(int, input().split()))
cnt = 0
for a in range(n - 2):
    for b in range(a + 1, n - 1):
        for c in range(b + 1, n):
            if l[a] + l[b] > l[c]:
                cnt += 1
            else:
                break
print(cnt)

### FIXED CODE ###

from collections import deque
from bisect import bisect_left

n = int(input())
l = sorted(map(int, input().split()))
ld = deque(l)
cnt = 0
for a in range(n - 2):
    l_a = ld.popleft()
    for b in range(a + 1, n - 1):
        cnt += bisect_left(l, l_a + l[b]) - b - 1
print(cnt)