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

n = int(input())

from heapq import heappop, heappush

def main():
    cost = dict()
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        if a - 1 in cost:
            cost[a-1] = cost[a-1] + [(b-1, c)]
        else:
            cost[a-1] = [(b-1, c)]
        if b - 1 in cost:
            cost[b-1] = cost[b-1] + [(a-1, c)]
        else:
            cost[b-1] = [(a-1, c)]

    Q, K = map(int, input().split())

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        if u in cost:
            for v, weight in cost[u]:
                alt = du + weight
                if d[v] > alt:
                    d[v] = alt
                    heappush(q, (alt, v))

    for _ in range(Q):
        goal1, goal2 = map(int, input().split())
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heappop, heappush

def main():
    cost = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

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

s = input()
n = int(input())
for i in range(n):
    qq = list(input().split())
    if qq[0] == '1':
        s = s[::-1]
    else:
        if qq[1] == '1':
            s = qq[2] + s
        else:
            s = s + qq[2]

print(s)

### FIXED CODE ###

s = input()
n = int(input())
b = ''
a = ''
h = 0
for i in range(n):
    qq = list(input().split())
    if qq[0] == '1':
        h += 1
    else:
        if qq[1] == '1':
            if h % 2 ==1:
                a = a + qq[2]
            else:
                b = qq[2] + b
        else:
            if h % 2 ==1:
                b = qq[2] + b
            else:
                a = a + qq[2]

s = b + s + a
if h % 2 ==1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

T=[]
S=input()
Sr=list(reversed(S))
w1=list(reversed('dream'))
w2=list(reversed('dreamer'))
w3=list(reversed('erase'))
w4=list(reversed('eraser'))

while True:
    if Sr[:5]==w1:
        Sr=Sr[5:]
    elif Sr[:5]==w3:
        Sr=Sr[5:]
    elif Sr[:6]==w4:
        Sr=Sr[6:]
    elif Sr[:7]==w2:
        Sr=Sr[7:]
    else:
        break
if Sr==T:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

T=[]
S=input()
Sr=list(reversed(S))
w1=list(reversed('dream'))
w2=list(reversed('dreamer'))
w3=list(reversed('erase'))
w4=list(reversed('eraser'))

while True:
    if Sr[:5]==w1:
        del(Sr[:5])
    elif Sr[:5]==w3:
        del(Sr[:5])
    elif Sr[:6]==w4:
        del(Sr[:6])
    elif Sr[:7]==w2:
        del(Sr[:7])
    else:
        break
if Sr==T:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

K,S = map(int, input().split())
n = 0

for i in range(K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            if i==j and j==k:
                same=1
            elif (i==j and j!=k)or(j==k and i!=j) or(k ==i and i!=j):
                same =3
            else:
                same =6
            if i+j+k ==S:
                n=n+same
            else:
                n =n

print(n)


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline


K,S = map(int, input().split())
n = 0
up = math.floor(K)
for i in range(0,K+1):
    for j in range(0, K+1):
        if(0<= S-i-j <=K):
            n +=1
        else:
                n =n

print(n)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [0]*n
b = [0]*n

for i in range(n) :
    a[i], b[i] = map(int,input().split())

a_order = a.copy()
a_order.sort()

c = m + 0
ans = 0

while c > 0 :
    a_index_now = a.index(a_order[0]) + 0
    b_now = b[a_index_now] + 0
    if c >= b_now :
        ans += a_order[0] * b_now
        c -= b_now
        a.pop(a_index_now)
        b.pop(a_index_now)
        a_order.pop(0)
    else :
        ans += a_order[0] * c
        c = 0

print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ls = [0]*n

for i in range(n) :
    a,b = map(int,input().split())
    ls[i] = [a,b]
    
ls.sort(key=lambda x:x[0])

c = m + 0
ans = 0

while c > 0 :
    if c >= ls[0][1] :
        ans += ls[0][0] * ls[0][1]
        c -= ls[0][1]
        ls.pop(0)
    else :
        ans += ls[0][0] * c
        c = 0

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

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

for i in range(n-1):
    for j in range(i,n): #nC2通りを再現
        if abs(i+1-(j+1)) == a[i] + a[j]: #0スタートであることに注意
            count += 1
            
print(count)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
count = 0
b = []
c = []

for i in range(n):
    b.append(a[i]+i)
    c.append(i-a[i])
t = Counter(c) 
for s in b:
    count += t[s]

print(count)
### BUGGY CODE ###

import itertools
from sys import stdin
N=list(map(int,stdin.readline().strip().split()))[0]
st=list(stdin.readline().strip())
count=0
stt=list(set(st))
stt=list(stt)
num=["0","1","2","3","4","5","6","7","8","9"]
num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    cnt = 0
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break


print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

from collections import deque
import sys
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if not A in C:
        C[A] = []
    C[A].append(B)
for i in C:
    C[i] = deque(sorted(C[i])[::-1])

answer = 0
tmp = deque()

for i in range(1, M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = C[i]
        while len(tmp2) != 0 and len(right) != 0:   # line7
            if tmp2[0] > right[0]:                  # line8
                tmp.append(tmp2.popleft())           # line9
            else:                                   # line10
                tmp.append(right.popleft())          # line11
        if len(tmp2) != 0:                          # line12
            tmp+=tmp2                      # line13
        else:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = []
heapq.heapify(tmp)

for i in range(M+1):
    if i in C:
        right = C[i]
        for j in right:
            heapq.heappush(tmp,-1*j)
        
    if tmp != []:
        answer += -1*heapq.heappop(tmp)
print(answer)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = input()
RLlist = [None]*len(S)
location = []
for i in range(len(S)-1):
    if S[i]=='R' and S[i+1] == 'L':
        RLlist[i] = 'r'
        RLlist[i+1] = 'l'
        location.append(i)

location.sort()
def findhigh(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i]


def findlow(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i-1]
    return ylist[-1]

ans_list = [1 if RLlist[i] != None else 0 for i in range(len(S))]

for i in range(len(S)):
    if S[i] == 'R' and RLlist[i] != 'r':
        high =findhigh(i,location) 
        diff = abs(high-i)
        if diff%2 == 1:
            ans_list[high+1]+=1
        else:
            ans_list[high]+=1
    if S[i] == 'L' and RLlist[i] != 'l':
        low = findlow(i, location)
        diff = abs(low-i)
        if diff%2 == 1:
            ans_list[low+1]+=1
        else:
            ans_list[low]+=1
        

print(*ans_list)

### FIXED CODE ###

'''from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
'''
S = input()
RLlist = [None]*len(S)
location = []
for i in range(len(S)-1):
    if S[i]=='R' and S[i+1] == 'L':
        RLlist[i] = 'r'
        RLlist[i+1] = 'l'
        location.append(i)

location.sort()
def findhigh(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i]


def findlow(x, ylist):
    for i in range(len(ylist)):
        if x < ylist[i]:
            return ylist[i-1]
    return ylist[-1]

ans_list = [1 if RLlist[i] != None else 0 for i in range(len(S))]

for i in range(len(S)):
    if S[i] == 'R' and RLlist[i] != 'r':
        high =findhigh(i,location) 
        diff = abs(high-i)
        if diff%2 == 1:
            ans_list[high+1]+=1
        else:
            ans_list[high]+=1
    if S[i] == 'L' and RLlist[i] != 'l':
        low = findlow(i, location)
        diff = abs(low-i)
        if diff%2 == 1:
            ans_list[low+1]+=1
        else:
            ans_list[low]+=1
        

print(*ans_list)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    for j in range(i,n + 1,i):
        ans += j
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())  # R個の箱, G個の箱, B個の箱
ans = 0
for r in range(N+1):  # 1
    for g in range(N+1):  # 0
        b = N - (r*R + g*G)  # b = 4 - (1*1 + 0*2) = 3
        if b % B == 0 and b >= 0:
            # print(r, g, b)  # 1, 0, 1のパターンが抜けている
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R + 1):
    for g in range((N - (R*r))//G + 1):
        if(N - (R*r) - (G*g)) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

str_line = [i for i in input()]
a_place = []
z_place = []
result = 0
for i, stri in enumerate(str_line):
    if stri == "A":
        a_place.append(i)  
for i, stri in enumerate(str_line):
    if stri == "Z":
        z_place.append(i)   
for i in z_place:
    for j in a_place:
        if i-j+1 >= result:
            result = i-j+1
print(result)        

### FIXED CODE ###

str_line = [i for i in input()]
a_place = []
z_place = []
result1 = 0
result2 = 10000000
for i, stri in enumerate(str_line):
    if stri == "A":
        a_place.append(i)  
for i, stri in enumerate(str_line):
    if stri == "Z":
        z_place.append(i)   
for i in z_place:
    if i >= result1:
        result1 = i
for i in a_place:
    if i <= result2:
        result2 = i
print(result1 - result2 + 1)
### BUGGY CODE ###

N, M = map(int, input().split())
route_list = [[10**9 + 1] * N for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    for j in range(L, R):
        for l in range(j+1, R+1):
            route_list[j-1][l-1] = min(C, route_list[j-1][l-1])
unsearched_nodes = list(range(N))
node_num = N
distance = [10**9] * node_num
previous_nodes = [-1] * node_num  # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0  # 初期のノードの距離は0とする


def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1


while(len(unsearched_nodes) != 0):
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = 10**9
    for node_index in unsearched_nodes:
        if posible_min_distance > distance[node_index]:
            posible_min_distance = distance[node_index]
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes)
    unsearched_nodes.remove(target_min_index)

    target_edge = route_list[target_min_index]
    for index, route_dis in enumerate(target_edge):
        if route_dis <= 10**9:
            if distance[index] > (distance[target_min_index] + route_dis):
                distance[index] = distance[target_min_index] + route_dis
                previous_nodes[index] = target_min_index

if distance[node_num - 1] == 10**9:
	print(-1)
else:
    print(distance[node_num - 1])

### FIXED CODE ###

from heapq import heappop, heappush
N, M = map(int, input().split())
route_list = [[] for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1].append((R-1, C))
for i in range(N-1):
    route_list[i+1].append((i, 0))

distance = [float("inf")] * N
distance[0] = 0  # 初期のノードの距離は0とする
q = [(0, 0)]

while q:
    _, u = heappop(q)
    for des, cost in route_list[u]:
        if distance[des] > distance[u] + cost:
            distance[des] = distance[u] + cost
            heappush(q, (distance[des], des))

print(distance[-1] if distance[-1] != float("inf") else -1)
### BUGGY CODE ###

K = int(input())

a = 7

for i in range(K):
    if(a % K == 0):
        print(i + 1)
        break
    a = a * 10 + 7

else:
    print(-1)

### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())

first = []
for i in range(m):
    if a[i] == 1:
        first.append(b[i])
second = []
ans = 'IMPOSSIBLE'
for i in range(m):
    if a[i] in first:
        second.append(b[i])

for i in second:
    if i == n:
        ans = 'POSSIBLE'
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
first = set()
second = set()
for i in range(m):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        first.add(b[i])
    if b[i] == n:
        second.add(a[i])


ans = 'IMPOSSIBLE'
if first & second:
    ans = 'POSSIBLE'
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
res = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if (x + y + z) == S:
                res += 1
print(res)

### FIXED CODE ###

K, S = map(int, input().split())
res = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S- (x + y)
        if z>=0 and z<=K:
            res += 1
print(res)
### BUGGY CODE ###

N,M=map(int, input().split())
a=[int(i) for i in input().split()]
a.sort()
'''
for i in range(M):
    B,C=map(int, input().split())
    for j in range(B):
        if a[j]<C:
            a[j]=C   
    a.sort()

print(sum(a))
'''
for i in range(M):
    B,C=map(int, input().split())
    j=0
    while j<B:
        if a[j]>=C:
            break
        a[j]=C
        j+=1
    a.sort()
#    print(a)

print(sum(a))


### FIXED CODE ###

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

a.sort()
c2=sorted(c,key=lambda x:(-int(x[1])))

d = []
for i in range(M):
    for j in range(c2[i][0]):
        d.append(c2[i][1])
        if len(d) == N:
            break
    else:
        continue
    break

i = 0
while a[i] < d[i]:
    a[i] = d[i]
    i += 1
    if i == N or i == len(d):
        break

print(sum(a))
### BUGGY CODE ###

from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

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

not_yet = deque([0])
already = [False]*n
yet = [False]*n

parent = [0]*n
already[0] = True

ans = 1
while not_yet:
  key = not_yet.popleft()
  yet[key] = True
  next_count = 1
  for value in tree[key]:
    if not already[value]:
      not_yet.append(value)
      already[value] = True
      parent[value] = key
  for value in tree[parent[key]]:
    if yet[value] and value != key:
      next_count += 1
  
  if key == 0:
    next_count = 0
  ans *= k-next_count
  ans %= inf

print(ans)

### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

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

not_yet = deque(tree[0])
already = [False]*n
already[0] = True
ans = k
key = k-1
for v in tree[0]:
  already[v] = True
  ans *= key
  ans %= inf
  key -= 1

while not_yet:
  key = not_yet.popleft()
  for v in range(k-2, k-1-len(tree[key]), -1):
    ans *= v
    ans %= inf
  
  for value in tree[key]:
    if already[value]:
      continue
    not_yet.append(value)
    already[value] = True

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

import math

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

N = int(input())

g = 0
for i in range(N):
    g += (i+1) * search_divisor_num_1(i+1)
print(g)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
  k = n//i
  ans += i*(k*(k+1))//2
print(ans)
### BUGGY CODE ###

#ABC 098 C Attention

n = int(input())
s = input()
cnt = 0
cnt_list = []

for i in range(n):
    for j in range(i):
        if s[j] == "W":
            cnt += 1
    for k in range(i+1,n):
        if s[k] == "E":
            cnt +=1
    cnt_list.append(cnt)
    cnt = 0
print(min(cnt_list))

### FIXED CODE ###

#ABC 098 C Attention

#いちいち全部数え直さない方がいい説
n = int(input())
s = input()
cnt = 0
cnt_list = []

for i in range(1,n):
    if s[i] == "E":
        cnt += 1
cnt_list.append(cnt)
for j in range(1,n):
    if s[j-1] == "W":
        cnt += 1
    if s[j] == "E":
        cnt -= 1
    cnt_list.append(cnt)

print(min(cnt_list))
### BUGGY CODE ###

n=int(input())
li=[list(map(int,input().split())) for i in range(n-1)]

#色の情報を記録する配列を作る。0が白で、1が黒
col=[-1]*(n+1) #最初は全ての頂点が情報なし。
col[1]=0 #頂点1の色は白。

#2点間の距離の情報を記録する配列を作る
#ついでにグラフも作る
kyori=[[0]*(n+1) for i in range(n+1)]
graph = [[] for _ in range(n+1)]

for x,y,z in li:
  kyori[x][y]=kyori[y][x]=z
  graph[x].append(y)
  graph[y].append(x)

def dfs(v):
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]: #頂点vに接続してる点についての調査
            if dist[w] >= 0: #0以上であれば既に調査済み
                continue
            dist[w] = dw #調査済みでない場合は、distに現在の深さを記録。
            if kyori[v][w]%2:
              col[w]=col[v]^1
            else:
              col[w]=col[v]
            stack.append(w)
    return col
print(*dfs(1)[1:], sep="\n")

### FIXED CODE ###

n=int(input())
li=[list(map(int,input().split())) for i in range(n-1)]

#色の情報を記録する配列を作る。0が白で、1が黒
col=[-1]*(n+1) #最初は全ての頂点が情報なし。
col[1]=0 #頂点1の色は白。

#2点間の距離の情報を記録する配列を作る…と思ったがO(n^2)やわこれ
#ついでにグラフも作る。距離の情報はグラフに入れることにしよう
graph = [[] for _ in range(n+1)]

for x,y,z in li:
  graph[x].append([y,z])
  graph[y].append([x,z])

def dfs(v):
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w,z in graph[v]: #頂点vに接続してる点についての調査
            if dist[w] >= 0: #0以上であれば既に調査済み
                continue
            dist[w] = dw #調査済みでない場合は、distに現在の深さを記録。
            if z%2:
              col[w]=col[v]^1
            else:
              col[w]=col[v]
            stack.append(w)
    return col
print(*dfs(1)[1:], sep="\n")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
nisi = [0 for i in range(60)]
for i in range(n):
    for j in range(60):
        if (a[i] >> j) & 1 == 1:
            nisi[j] += 1
ans = 0
for i in range(n):
    for j in range(60):
        if (a[i] >> j)&1 == 1:
            ans += pow(2,j,mod)*(n-nisi[j])%mod
        else:
            ans += pow(2,j,mod)*nisi[j]%mod
        ans %= mod
ans *= pow(2,mod-2,mod)
ans %= mod
print(ans)

### FIXED CODE ###

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

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

lst.sort(key= lambda x: x[2], reverse=True)
lst.sort(key= lambda x: x[0])

d = [10**18 for i in range(n+1)]
d[1] = 0
for lsti in lst:
    l = lsti[0]
    r = lsti[1]
    c = lsti[2]
    if l == 1:
        for i in range(l+1, r+1):
            d[i] = c
    else:
        for i in range(l+1, r+1):
            d[i] = min(d[i], d[l]+c)

if d[n] == 10**18:
    print(-1)
else:
    print(d[n])

### FIXED CODE ###

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

lst.sort(key= lambda x: x[2], reverse=True)
lst.sort(key= lambda x: x[0])

d = [10**18 for i in range(n+1)]
d[1] = 0
for lsti in lst:
    l = lsti[0]
    r = lsti[1]
    c = lsti[2]
    if l == 1:
        for i in range(l+1, r+1):
            d[i] = c
    else:
        for i in range(l+1, r+1):
            j = l+1+r-i
            if d[l]+c < d[j]:
                d[j] = d[l] + c
            else:
                break

if d[n] == 10**18:
    print(-1)
else:
    print(d[n])
### BUGGY CODE ###

n = int(input())
a_s = list(map(int, input().split()))
sum_a_s = sum(a_s)

for i in range(n):
	tmp_sum = sum(a_s[:i])
	if tmp_sum >= sum_a_s - tmp_sum:
		break

tmp_res1 = abs(sum(a_s[:i - 1]) * 2 - sum_a_s)
tmp_res2 = abs(sum(a_s[:i]) * 2 - sum_a_s)
res = min(tmp_res1, tmp_res2)

print(res)


### FIXED CODE ###

n = int(input())
a_s = list(map(int, input().split()))
sum_a_s = sum(a_s)

tmp_sum = 0
for i in range(n - 1):
	tmp_sum += a_s[i]
	if tmp_sum > sum_a_s - tmp_sum:
		break

tmp_res1 = abs(sum(a_s[:i]) * 2 - sum_a_s)
tmp_res2 = abs(sum(a_s[:i + 1]) * 2 - sum_a_s)
res = min(tmp_res1, tmp_res2)

print(res)