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

from itertools import combinations

N = int(input())
answer_list = set(['M', 'A', 'R', 'C', 'H'])
name_count = []

for i in range(N):
    name = input()

    if name[0] in answer_list:
        name_count.append(name[0])

result = list([1 for x in combinations(
    name_count, 3) if len(set(x)) == len(x)])
print(sum(result))


### FIXED CODE ###

from itertools import combinations

N = int(input())
name_count = {'M': 0,
              'A': 0,
              'R': 0,
              'C': 0,
              'H': 0, }
for i in range(N):
    name = input()

    if name[0] in name_count:
        name_count[name[0]] += 1


def comb(n, r):
    up = 1
    down = 1
    for i in range(r):
        up *= n - i
        down *= i + 1
    return up // down


all_sum = sum(name_count.values())
total = comb(all_sum, 3)

for i in name_count.values():
    if i >= 2:
        total -= comb(i, 2) * (all_sum - i)

    if i >= 3:
        total -= comb(i, 3)

print(total)
### BUGGY CODE ###

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

lst = []
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            mojiretu = s[i] + s[j] + s[k]
            if mojiretu not in lst:
                cnt += 1
                lst.append(mojiretu)

print(cnt)

### FIXED CODE ###

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

lst = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            moji1 = lst[i]
            moji2 = lst[j]
            moji3 = lst[k]
            cnt = 0
            kuraberu = [moji1, moji2, moji3]
            for moji in s:
                if moji == kuraberu[cnt]:
                    cnt += 1
                if cnt == 3:
                    ans += 1
                    break

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
for i in range(n - 1):
    for j in range(i,n):
        ans += a[i]^a[j]

print(ans%MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
for i in range(60):
    tmp0 = 0
    tmp1 = 0
    for j in range(n):
        if a[j]>>i&1 == 0: tmp0 += 1
        else: tmp1 += 1
    ans += (tmp0*tmp1%MOD)*(2**i%MOD)
print(ans%MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

# print(N)
# print(A)
# print(Q)
# print(B)
# print(C)

ans = []

for i in range(Q):
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]

    ans_item = sum(A)
    ans.append(ans_item)


# print(ans)
for item in ans:
    print(item)


### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

l = [0] * (10**5 + 1)
# print(l)
# print(len(l))
c = collections.Counter(A)
# print(c)
for key in c:
    l[key] = c[key]
# print(l)
ans = 0
for item in c:
    ans += item * c[item]

# print(ans)  # i=0

for i in range(Q):
    if B[i] in c:
        # print(c)
        ans = ans - B[i] * c[B[i]] + C[i] * c[B[i]]
        c[C[i]] += c[B[i]]
        c.pop(B[i])
    print(ans)
### BUGGY CODE ###

import sys
import numpy as np
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = np.array(readline().split(), np.int64)
    A_cum = np.cumsum(A)
    counter = Counter(A_cum)

    fact = [1] * (N + 1)
    for r in range(2, N + 1):
        fact[r] = fact[r - 1] * r

    def cmb(n, r):
        return fact[n] // (fact[r] * fact[n - r])

    ans = 0
    for key, value in counter.items():
        if value >= 2:
            ans += cmb(value, 2)
        if key == 0:
            ans += value
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import numpy as np
from collections import Counter
import math

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = np.array(readline().split(), np.int64)
    A_cum = np.cumsum(A)
    counter = Counter(A_cum)

    def cmb(n, r):
        return math.factorial(n) // (math.factorial(r)*math.factorial(n-r))

    ans = 0
    for key, value in counter.items():
        if value >= 2:
            ans += cmb(value, 2)
        if key == 0:
            ans += value
    print(ans)


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

N = int(input())
count = 0
for X in range(1,N):
  for i in range(1, int(X**0.5)+1):
    if X % i == 0:
      count += 1
      if i != X // i:
         count += 1
print(count)
  

### FIXED CODE ###

N = int(input())
ans = 0
for A in range(1,N):
  ans += (N-1) // A
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
jobs = [[] for i in range(100001)]
for i in range(n):
    a1,b1 = map(int,input().split())
    jobs[a1 - 1].append(b1)
result = 0
for i in range(m):
    jobs_1 = 0
    jobs_2 = 0
    reward = 0
    for j in range(i+1):
        if len(jobs[j]) != 0:
            reward = max(reward,max(jobs[j]))
            jobs_1 = j
            jobs_2 = jobs[j].index(max(jobs[j]))
    if reward != 0:
        result += reward
        del jobs[jobs_1][jobs_2]
print(result)

### FIXED CODE ###

from heapq import heappush, heappop
n,m = map(int,input().split())
jobs = [[] for i in range(100001)]
for i in range(n):
    a1,b1 = map(int,input().split())
    jobs[a1].append(b1)

reward = 0
heapsort = []
for daysLeft in range(1,m+1):
    if len(jobs[daysLeft]) != 0:
        for i in jobs[daysLeft]:
            heappush(heapsort,-i)
    if len(heapsort) > 0:
        reward += -heappop(heapsort)
print(reward)
### BUGGY CODE ###

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


while K < N:
    if A[K]*A[K-1]*A[K-2]>A[K-1]*A[K-3]*A[K-3]:
        print("Yes")

### FIXED CODE ###

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

a = 0
while K < N:
    if A[a] < A[K]:
        print("Yes")
    else:print("No")
    K += 1
    a += 1
### BUGGY CODE ###

N = int(input())

target_list = map(int, input().split())
result = []

for i in range(int(input())):
    B, C = map(int, input().split())
    target_list = [C if i == B else i for i in target_list]
    result.append(sum(target_list))

for i in result:
    print(i)


### FIXED CODE ###

from collections import Counter

N = int(input())

target_list = list(map(int, input().split()))
check = Counter(target_list)
result = sum(target_list)


for index in range(int(input())):
    B, C = map(int, input().split())
    if B in check:
        result = result + (check[B]) * (C - B)
        if C in check:
            check[C] = check[C] + check[B]
        else:
            check[C] = check[B]
        check[B] = 0
    print(result)
### BUGGY CODE ###

import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans=Ans+[a]
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))


### FIXED CODE ###

import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))
### BUGGY CODE ###

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

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

def waribiki(X,Y):
    return X//(2**Y)

if len(A)==1:
    while M>0:
        A.sort(reverse=True)
        A[0] = waribiki(A[0],1)
        M -= 1
    
else:
    while M>0:
        A.sort(reverse=True)
        m=1
        while waribiki(A[0],m) > A[1]:
            m+=1
        else:
            A[0] = waribiki(A[0],m)
        M -= m

print(sum(A))


### FIXED CODE ###

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

def intm(x):
    return int(x)*-1
A = list(map(intm, input().split()))

import heapq

heapq.heapify(A)
while M>0:
    a = -heapq.heappop(A) // 2
    heapq.heappush(A,-a)
    M -= 1
   

print(-sum(A))
### BUGGY CODE ###

wfwfe=input()

b=input().split()



count=1
for i in b:
    count=count*int(i)
    
if count>10**18:
    print (-1)
else:
    print (count)


### FIXED CODE ###

wfwfe=input()
check=0
b=input().split()
if "0" in b:
    print (0)
else:
    
    count=1
    for i in b:
        count=count*int(i)
        
        if count>10**18:
            print (-1)
            check=1
            break
    if check==0:
        print (count)
### BUGGY CODE ###

x = int(input())

if x == 2:
    print(2)
    quit()
li = [2]
for i in range(3, 10 ** 6, 2):
    for j in li:
        if i % j == 0:
            break
    else:
        if i >= x:
            print(i)
            quit()
        li.append(i)

### FIXED CODE ###

x = int(input())

if x == 2:
    print(2)
    quit()
li = [2]
for i in range(3, 10**6, 2):
    for j in li:
        if i % j == 0:
            break
    else:
        if i >= x:
            print(i)
            quit()
        li.append(i)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(1,N):
    ans+=i
print(ans)

### FIXED CODE ###

N=int(input())

print((N-1)*N//2)
### BUGGY CODE ###

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

N, K = map(int, input().split(" "))
c = 0

if K == 0:
    print(N*N)
else:
    for b in range(K+1, N+1):
        for a in range(K, b):
            n = (N-a)//b + 1
            c += n
            
    print(c)

### FIXED CODE ###

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

N, K = map(int, input().split(" "))
c = 0
 
if K != 0:
    for b in range(K+1, N+1):
        s = N % b
        t = N - s
        p = t // b * (b - K)
        q = max(0, s - (K - 1))
        c += (p + q)
        
else:
    c = N ** 2

print(c)
### BUGGY CODE ###

S = input()
Q = int(input())
queries = list(list(input().split()) for _ in range(Q))

reverse = 0
for query in queries:
    if len(query) == 1:
        reverse = 1 - reverse

    else:
        is_append_left = (reverse + int(query[1])) % 2
        if is_append_left:
            S = query[2] + S
        else:
            S += query[2]

if reverse:  # reverse処理は重い．実際，最後の一回で良い．
    S = S[::-1]

print(S)


### FIXED CODE ###

import sys
from collections import deque
S = deque(input())
Q = int(input())
# queries = list(list(input().split()) for _ in range(Q))  # 後でroop回し直すのは2度手間

reverse = 0
# for query in queries:
for query in sys.stdin:
    if query[0] == '1':  # len(query)は改行記号の有無で変わるのでダメ
        reverse = 1 - reverse

    else:
        _, f, c = query.split()
        is_append_left = (reverse + int(f)) % 2
        if is_append_left:
            S.appendleft(c)  # listだとO(n)だが，dequeではO(1)
        else:
            S.append(c)

if reverse:  # reverse処理は重い．実際，最後の一回で良い．
    S.reverse()

print(''.join(S))
### BUGGY CODE ###

K = int(input())

if K%2 == 0 or K%2 ==0:
    print("-1")
    exit(0)

count = 0
an = 0
while True:
  an = (10*an + 7) % K
  count +=1
  if an == 0:
    break
print(count)

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, M = list(map(int,input().split()))
LRC = [list(map(int,input().split())) for i in range(M)]
LRC.sort()

INF = 100100100100100100
dist = [INF]*N
dist[0] = 0

for li, ri, ci in LRC:
	for i in range(li,ri):
		dist[i] = min(dist[i], dist[li-1]+ci)

ans = dist[-1]
if ans==INF: ans = -1

print(ans)

### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline

N, M = list(map(int,input().split()))
LRC = [list(map(int,input().split())) for i in range(M)]
LRC.sort()

INF = 100100100100100100
dist = [INF]*N
dist[0] = 0

for li, ri, ci in LRC:
	td = dist[li-1]+ci
	ti = bisect.bisect(dist,dist[li-1]+ci)
	ti = min(ti,ri+1)
	for i in range(ti,ri):
		dist[i] = td

ans = dist[-1]
if ans==INF: ans = -1

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

#abc139d
N = int(input())

if N>2:
    ans=0

    add = [i for i in range(2,N,1)]
    print(ans+sum(add)+1)
elif N==2:
    print("1")
elif N==1:
    print("0")

### FIXED CODE ###

#139D

#ここから試験用コード
'''
import itertools

for N in range(1,13):
    l = [i for i in range(1,N+1)]

    ans = 0
    ans_permutation = list()

    for permutation in itertools.permutations(l, N):
        temp_ans = 0
        permutation = [0] + list(permutation)
        for i in range(1,N+1):
            temp_ans += i%permutation[i]

        if ans <= temp_ans:
            if ans < temp_ans:
                ans_permutation = list()
            ans = temp_ans    
            ans_permutation.append(list(permutation)[1:])

    print(N,ans,ans_permutation)
    
#試験用コードの結果
# 1  0 [[1]]
# 2  1 [[2, 1]]
# 3  3 [[1, 3, 2], [2, 3, 1]]
# 4  6 [[2, 3, 4, 1]]
# 5 10 [[1, 3, 4, 5, 2], [2, 1, 4, 5, 3], [2, 3, 4, 5, 1]]
# 6 15 [[2, 3, 4, 5, 6, 1]]
# 7 21 [[1, 3, 2, 5, 6, 7, 4], [1, 3, 4, 5, 6, 7, 2], [2, 3, 1, 5, 6, 7, 4], [2, 3, 4, 5, 6, 7, 1]]
# 8 28 [[2, 1, 4, 5, 6, 7, 8, 3], [2, 3, 4, 5, 6, 7, 8, 1]]
# 9 36 [[1, 3, 4, 5, 6, 7, 8, 9, 2], [2, 3, 4, 1, 6, 7, 8, 9, 5], [2, 3, 4, 5, 6, 7, 8, 9, 1]]
#10 45 [[2, 3, 4, 5, 6, 7, 8, 9, 10, 1]]

#いずれにも最初は2,3...、最後は1となるパターンがある
#上記パターン時は ((N-1)+1)*(N-1)/2 が答え。
'''
N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = sorted(list(map(int,input().split())))
ans = []

for n in range(N):
  ans+=[np.gcd.reduce(np.delete(A,n))]

print(max(ans))

### FIXED CODE ###

from fractions import *
from itertools import *
N = int(input())
A = list(map(int,input().split()))
B = list(accumulate([0]+A,gcd))
C = list(accumulate([0]+A[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(B,C[::-1][1:])))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

A.sort()
for i in range(M):
  cnt = 0
  for j in range(N):
    if cnt >= BC[i][0]:
      break
    if BC[i][1] > A[j]:
      A[j] = BC[i][1]
      cnt += 1
  if i != M-1:
    A.sort()
print(sum(A))

    


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

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


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

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

m = list(set(n))



c = 0
if len(m) <= b:
    print(0)
else:
    dic = {}
    for i in range(len(m)):
        dic[str(m[i])] = n.count(m[i])

    dic = sorted(dic.items(), key = lambda x:x[1])
    for i in range(len(m) - b):
        c += dic[i][1]
    print(c)


### FIXED CODE ###

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

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

l = {}
for a in n:
    l[a] = l.get(a, 0) + 1
print(sum(sorted(l.values())[:-b]))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for ii in range(k):
    if a > 0:
        a -= 1
    else:
        if b > 0:
            b -= 1
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())
if a >= k:
    a -= k
    print(a, b)
elif a < k:
    if b >= (k-a):
        b = b - (k - a)
        print(0, b)
    elif b < (k-a):
        print(0, 0)
### BUGGY CODE ###

a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
for i in A:
    for j in B:
        ans=min(ans,i+j)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)

### FIXED CODE ###

a,b,m=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

ans=99999999999
ans=min(A)+min(B)
for i in range(m):
    x,y,c=map(int,input().split())
    ans=min(ans,A[x-1]+B[y-1]-c)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
g=[[] for _ in range(n)]

for i in range(n-1): # 行列の作成
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

costs = [0]*n # 答えの格納

for i in range(q): # コスト初期値の入力
    p, x = map(int, input().split())
    costs[p-1]+=x

visited = [0]*n # 訪問スタンプ

def dfs(idx):
    visited[idx]=1
    for i in g[idx]:
        if visited[i]==1:
            continue
        costs[i]+=costs[idx] # 累積和をとる
        dfs(i) # 再帰処理
    return

dfs(0)
print(*costs)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
g=[[] for _ in range(n)]

for i in range(n-1): # 行列の作成
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

costs = [0]*n # 答えの格納

for i in range(q): # コスト初期値の入力
    p, x = map(int, input().split())
    costs[p-1]+=x

visited = [0]*n # 訪問スタンプ

def dfs(idx):
    visited[idx]=1
    for i in g[idx]:
        if visited[i]==1:
            continue
        costs[i]+=costs[idx] # 累積和をとる
        dfs(i) # 再帰処理
    return

dfs(0)
print(*costs)
### BUGGY CODE ###

n, m=map(int, input().split())
grid = []
for i in range(m):
    array = list(map(int, input().strip().split()))
    grid.append(array)

x=[]
for i in range(m):
    for j in range(grid[i][1]-grid[i][0]+1):
        x.append(grid[i][0]+j)

ans = [i for i in set(x) if x.count(i) == m]

print(len(ans))

### FIXED CODE ###

n, m=map(int, input().split())
grid = []
for i in range(m):
    array = list(map(int, input().strip().split()))
    grid.append(array)


maxa,mina=grid[0]
for i in range(1,m):
    if maxa<grid[i][0]:
        maxa=grid[i][0]
    if mina>grid[i][1]:
        mina=grid[i][1]

v=mina-maxa+1
if v>0:
    print(v)
else:
    print(0)
### BUGGY CODE ###

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


### FIXED CODE ###

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

N = int(input())
X = int(str(input()), 2)

def F(n:int)->int:
    res = 0
    while 0 < n:
        pop = bin(n).count('1')
        n %= pop
        res += 1
    return res

for i in range(N-1, -1, -1):
    mask = 2**i
    ans = F(X ^ mask)
    print(ans)

### FIXED CODE ###

N = int(input())
X = str(input())
F = [0] * N

def calc_f(n:int)->int:
    global F
    x = n
    res = 0
    while 0 < x:
        if F[x] != 0:
            res += F[x]
            break
        pop = bin(n).count('1')
        x %= pop
        res += 1
    F[n] = res

# 前処理 N以下のF値テーブル
for i in range(1, N):
    calc_f(i)

# ビット反転すると初期の1の個数に対して+1または-1どちらか
pop_ini = X.count('1')
pp = pop_ini + 1  # pop_plus
pm = pop_ini - 1  # pop_minus

# 2進の各桁をppとpmで割った値のテーブル
ap = [0] * N  # arr_plus
am = [0] * N  # arr_minus
for i in range(N):
    ap[i] = pow(2, N-1-i, pp)
    if 0 < pm:
        am[i] = pow(2, N-1-i, pm)

# 所与のXで計算、ベースになる値
fp = 0  # f_plus
fm = 0  # f_minus
for i in range(N):
    if X[i] == '1':
        fp = (fp + ap[i]) % pp
        if 0 < pm:
            fm = (fm + am[i]) % pm

# 各桁を反転した場合では差分更新のみ
for i in range(N):
    ans = 1
    if X[i] == '1':
        if 0 < pm:
            v = (fm + pm - am[i]) % pm
        else:
            ans = 0
            v = 0
    else:
        v = (fp + ap[i]) % pp
    if 0 < v:
        ans += F[v]
    print(ans)
### BUGGY CODE ###

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

max_num = 0

for a in range(N+1):
    for b in range(M+1):
        if sum(A[:a])+sum(B[:b]) <= K:
            if max_num < a+b:
                max_num = a+b
        else:
            break

print(int(max_num))


### FIXED CODE ###

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

a = [0]*(N+1)
b = [0]*(M+1)

for i in range(N):
    a[i+1] = a[i] + A[i]
for j in range(M):
    b[j+1] = b[j] + B[j]

n_b = M
best = 0

for n_a in range(N+1):
    if K < a[n_a]:
        break

    while  K < a[n_a] + b[n_b]:
        n_b -= 1

    best = max(n_a + n_b,best)

print(int(best))
### BUGGY CODE ###

from itertools import chain
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
t=[]
for i in range(min(n,m)):
    for k in range(bc[i][0]):
        t.append(bc[i][1])

ans=sum(a)
j=0
while j<len(t) and j<n and t[j]>a[j]:
    ans+=t[j]-a[j]
    j+=1
#for i in range(n):
#   if i<len(t):
#       ans+=max(a[i],t[i])
#   else:
#       ans+=a[i]
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
t=[]

for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

a, b,c,K = map(int, input().split())
ans = 0

for i in range(K):
    if a > 0:
        ans += 1
        a -= 1
        continue   
    if b > 0:
        b -= 1
        continue         
    if c > 0:
        b -= 1
        ans -= 1
        continue     


print(ans)

### FIXED CODE ###

a, b,c,K = map(int, input().split())
ans = 0

if a >= K:
    ans = K
    
    
elif a+b >= K :
    ans = a
    

else:
    ans = a - (K-a-b)
    

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
uvw = [LIST() for _ in range(N-1)]
uvw.sort(key=lambda x:(x[0], x[1]))
color = [0]*N  # -1で白 1で黒を表す
searched = [0]*N  # 探索した場所に1をいれる
color[0] = -1  # 0番目のノードを白で初期化
searched[0] = 1  # 0 番目のノードは探索済み
for u, v, w in uvw:
	if searched[u-1] == 0 and searched[v-1] == 0:
		uvw.append([u, v, w])
		continue
	if searched[v-1] == 1:
		u, v = v, u
	if w % 2 == 0:
		color[v-1] = color[u-1]
		searched[v-1] = 1
	else:
		color[v-1] = color[u-1] * (-1)
		searched[v-1] = 1
	# print(searched)
# print(color)
for i in color:
	if i == -1:
		print('0')
	else:
		print('1')


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
uvw = [LIST() for _ in range(N-1)]

link_dic = defaultdict(list)

for u, v, w in uvw:
	link_dic[u-1].append((v-1, w))
	link_dic[v-1].append((u-1, w))
# print(link_dic)
searched = [0]*N
color = [0]*N
color[0] = 1
def dfs(i):
	# print(i)
	for node, w in link_dic[i]:
		if searched[node] == 1:
			continue
		else:
			if w % 2 == 0:
				color[node] = color[i]
			else:
				color[node] = color[i] * (-1)
			searched[node] = 1
			dfs(node)

dfs(0)
for i in color:
	if i == -1:
		print('0')
	else:
		print('1')