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

def main():
    N, u, v = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    d_from_u = [(1 << 63)-1 for i in range(N)]
    d_from_v = [(1 << 63)-1 for i in range(N)]

    def dfs(v, d):
        seen = [False] * N
        todo = []
        seen[v] = True
        d[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]

            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                d[next_v] = d[u] + 1
                todo.append(next_v)
                break
            else:
                todo.pop()

    u, v = u-1, v-1
    dfs(u, d_from_u)
    dfs(v, d_from_v)
    ans = 0
    for du, dv in zip(d_from_u, d_from_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, u, v = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    d_from_u = [-1] * N
    d_from_v = [-1] * N

    def dfs(v, d):
        todo = []
        d[v] = 0
        todo.append(v)
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if 0 <= d[next_v]:
                    continue
                d[next_v] = d[u] + 1
                todo.append(next_v)

    u, v = u-1, v-1
    dfs(u, d_from_u)
    dfs(v, d_from_v)
    ans = 0
    for du, dv in zip(d_from_u, d_from_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


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

N=int(input())
A=[int(i) for i in input().split()]
arr={}
for a in A:
	if a in arr:
		arr[a]+=1
	else:
		arr[a]=1
Q=int(input())
for q in range(Q):
	B,C=[int(i) for i in input().split()]
	if B in arr:
		if C in arr:
			arr[C]+=arr[B]
		else:
			arr[C]=arr[B]
		arr[B]=0
	print(sum([i[0]*i[1] for i in arr.items()]))


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
arr={}
P={}
for a in A:
	if a in arr:
		arr[a]+=1
	else:
		arr[a]=1
for k,v in arr.items():
	P[k]=k*v
S=sum([i for i in P.values()])
Q=int(input())
for q in range(Q):
	B,C=[int(i) for i in input().split()]
	if B in arr:
		if C in arr:
			arr[C]+=arr[B]
			P[C]+=arr[B]*C
		else:
			arr[C]=arr[B]
			P[C]=arr[B]*C
		S-=P[B]
		S+=arr[B]*C
		del arr[B]
		del P[B]
	print(S)
### BUGGY CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * N for j in range(N)]
    for a, b, c in ABC:
        dist[a-1][b-1] = dist[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    field = list(map(int, input().split()))

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        tmpList = []

        for j in range(1, min(K+1, i+1)):
            tmpList = tmpList + [dpList[i - j] + abs(field[i] - field[i - j])]

        dpList[i] = min(tmpList)

    print(dpList[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    field = list(map(int, input().split()))

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        tmpList = []
        minCost = -1

        minS = max(0, i - K)

        for dpJ, fJ in zip(dpList[minS:i], field[minS:i]):
            cost = dpJ + abs(field[i] - fJ)

            if(minCost == -1):
                minCost = cost
            elif minCost > cost:
                minCost = cost

        dpList[i] = minCost

    print(dpList[-1])

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

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

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	x = d[i][1]
	s = bitl.Sum(x)
	lu[i] = i - s
	ld[i] = s
	bitl.PointAdd(x, 1)

for i in range(n-1, -1, -1):
	x = d[i][1]
	s = bitr.Sum(x)
	ru[i] = n-1-i - s
	rd[i] = s
	bitr.PointAdd(x, 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += pow(2, n, MOD)-1
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)


### FIXED CODE ###

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

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)
### BUGGY CODE ###

H,W,M = map(int,input().split())
L=[]
for i in range(M):
    h,w = map(int,input().split())
    L.append([h-1,w-1])

h = dict()
w = dict()

for i in range(M):
    val = L[i][0]
    if val in h:
        h[val] += 1
    else:
        h[val] = 1

for i in range(M):
    val = L[i][1]
    if val in w:
        w[val] += 1
    else:
        w[val] = 1

maxh = []
maxw = []
m=-1
for val in h:
    if h[val]>m:
        m = h[val]

for val in h:
    if m==h[val]:
        maxh.append(val)

ans = m
m=-1
for val in w:
    if w[val]>m:
        m=w[val]

for val in w:
    if m==w[val]:
        maxw.append(val)

ans += m
#print(maxh)
#print(maxw)
for mh in maxh:
    for mw in maxw:
        if [mh,mw] not in L:
            print(ans)
            exit()

print(ans-1)

### FIXED CODE ###

from collections import defaultdict
H,W,M = map(int,input().split())
L=[]
bomb = defaultdict(lambda: 0)
for i in range(M):
    h,w = map(int,input().split())
    L.append([h-1,w-1])
    bomb[(h-1,w-1)] = 1

h = dict()
w = dict()

for i in range(M):
    val = L[i][0]
    if val in h:
        h[val] += 1
    else:
        h[val] = 1

for i in range(M):
    val = L[i][1]
    if val in w:
        w[val] += 1
    else:
        w[val] = 1

maxh = []
maxw = []
m=-1
for val in h:
    if h[val]>m:
        m = h[val]

for val in h:
    if m==h[val]:
        maxh.append(val)

ans = m
m=-1
for val in w:
    if w[val]>m:
        m=w[val]

for val in w:
    if m==w[val]:
        maxw.append(val)

ans += m
#print(maxh)
#print(maxw)
for mh in maxh:
    for mw in maxw:
        if bomb[(mh,mw)]==0:
            print(ans)
            exit()

print(ans-1)
### BUGGY CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n):
    for j in range(1,n-i):
        if i+2*j <= n-1:
            tem = s[i]+s[i+j]+s[i+2*j]
            num_r = tem.count("R")
            num_g = tem.count("G")
            num_b = tem.count("B")
            if num_r == 1 and num_g == 1 and num_b == 1:
                minus += 1
            

print(sum - minus)

### FIXED CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n-2):
    for j in range(2, n-i+1, 2):
        if i+j <= n-1:
            tem = [s[i], s[i+j//2], s[i+j]]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

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

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
k = []
j = 0
na= 0
c = 0
if sum(a)<sum(b):
    print(-1)
else:
    for i in range(n):
        if a[i]<b[i]:
            na +=b[i]-a[i]
            c+=1
        elif a[i] > b[i]:
            k.append(a[i]-b[i])
        k.sort()
        k = k[::-1]
    while na > 0:
        na -=k[j]
        c +=1
        j+=1
    print(c)

### FIXED CODE ###

import sys
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())
a=list(mii())
b=list(mii())
k = []
j = 0
na= 0
c = 0
for i in range(n):
    if a[i]<b[i]:
        na +=b[i]-a[i]
        c+=1
    elif a[i] > b[i]:
        k.append(a[i]-b[i])
k.sort()
while na > 0 and k:
    na -=k[-1]
    k.pop(-1)
    c +=1
if na > 0:print(-1)
else:print(c)
### BUGGY CODE ###

import itertools
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

la = []
l = list(range(1, k+1))
for a, b, c in itertools.product(l, l, l):
    la.append(gcd(a, b, c))

print(sum(la))

### FIXED CODE ###

k = int(input())

ans = [
1,
9,
30,
76,
141,
267,
400,
624,
885,
1249,
1590,
2208,
2689,
3411,
4248,
5248,
6081,
7485,
8530,
10248,
11889,
13687,
15228,
17988,
20053,
22569,
25242,
28588,
31053,
35463,
38284,
42540,
46581,
50893,
55362,
61824,
65857,
71247,
76884,
84388,
89349,
97881,
103342,
111528,
120141,
128047,
134580,
146316,
154177,
164817,
174438,
185836,
194157,
207927,
218812,
233268,
245277,
257857,
268182,
288216,
299257,
313635,
330204,
347836,
362973,
383709,
397042,
416448,
434025,
456967,
471948,
499740,
515581,
536073,
559758,
583960,
604833,
633651,
652216,
683712,
709065,
734233,
754734,
793188,
818917,
846603,
874512,
909496,
933081,
977145,
1006126,
1041504,
1073385,
1106467,
1138536,
1187112,
1215145,
1255101,
1295142,
1342852,
1373253,
1422195,
1453816,
1502376,
1553361,
1595437,
1629570,
1691292,
1726717,
1782111,
1827492,
1887772,
1925853,
1986837,
2033674,
2089776,
2145333,
2197483,
2246640,
2332104,
2379085,
2434833,
2490534,
2554600,
2609625,
2693919,
2742052,
2813988,
2875245,
2952085,
3003306,
3096024,
3157249,
3224511,
3306240,
3388576,
3444609,
3533637,
3591322,
3693924,
3767085,
3842623,
3912324,
4027884,
4102093,
4181949,
4270422,
4361548,
4427853,
4548003,
4616104,
4718640,
4812789,
4918561,
5003286,
5131848,
5205481,
5299011,
5392008,
5521384,
5610705,
5739009,
5818390,
5930196,
6052893,
6156139,
6239472,
6402720,
6493681,
6623853,
6741078,
6864016,
6953457,
7094451,
7215016,
7359936,
7475145,
7593865,
7689630,
7886244,
7984165,
8130747,
8253888,
8403448,
8523897,
8684853,
8802826,
8949612,
9105537,
9267595,
9376656,
9574704,
9686065,
9827097,
9997134,
10174780,
10290813,
10493367,
10611772,
10813692
]

print(ans[k-1])
### BUGGY CODE ###

s=raw_input()
while True:
    f=0
    for i in xrange(len(s)-1):
        if s[i]=="S" and s[i+1]=="T":
            s=s[0:i]+s[i+2:len(s)]
            f=1
            break
    if f==0:
        break
print(len(s))

### FIXED CODE ###

s=raw_input()
stack=[]
for i in xrange(len(s)):
    if len(stack)==0 or s[i]=="S":
        stack.append(s[i])
        continue
    if s[i]=="T":
        if stack[-1]=="S":
            stack.pop()
        else:
            stack.append(s[i])
print(len(stack))
### BUGGY CODE ###

# coding:utf-8


INF = float('inf')


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


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

ans = INF
for k in range(1, N + 1):
    tmp = 0
    i = 0
    cur = N - k
    while True:
        e = 5 if i == 0 else 2 * i + 3
        tmp += e * (B[cur + k] - B[max(cur, 0)])
        if cur <= 0:
            break
        i += 1
        cur -= k

    ans = min(ans, tmp + (N + k) * X)

print(ans)

### FIXED CODE ###

# coding:utf-8


INF = float('inf')


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


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

ans = INF
for k in range(1, N + 1):
    e = 5
    cur = N - k
    tmp = e * (B[N] - B[cur]) + (N + k) * X
    cur -= k
    while True:
        tmp += e * (B[cur + k] - B[max(cur, 0)])
        if cur <= 0:
            break
        e += 2
        cur -= k

    ans = min(ans, tmp)

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

n,k=map(int,input().split())
s=[]
for i in range(n):
    a,b=map(int,input().split())
    s.extend([a for _ in range(b)])
s.sort()
print(s[k-1])

### FIXED CODE ###

import bisect
n,k=map(int,input().split())
s=[0 for _ in range((10**5)+1)]
maxa=0
for i in range(n):
    a,b=map(int,input().split())
    s[a]+=b
    maxa=max(maxa,a)
s=s[:maxa]
#print(s)
for i in range(1,len(s)):
    s[i]+=s[i-1]
#print(s)
print(bisect.bisect_left(s, k))
### BUGGY CODE ###

n, m = map(int, input().split())
Gr = {}
R = []
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d


rec = True
for i in Gr:
    for k in range(i[0], i[1]):
        if (i[0], k) in Gr and (k, i[1]) in Gr:
            if Gr[i] != Gr[(i[0], k)] + Gr[(k, i[1])]:
                rec = False

if rec:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N=int(input())
A=[None]*N

for i in range(N):
    A[i]=int(input())

B=[None]
Ans=0
for i in A:
    if i in B:
        continue
    else:
        if A.count(i)%2==1:
            Ans+=1
            B+=[i]



print(Ans)


### FIXED CODE ###

N=int(input())
A=[None]*N

for i in range(N):
    A[i]=int(input())

Ans=0
A.sort()
A+=[-1]
j=1
for i in range(1,N+1):
    if A[i]==A[i-1]:
        j+=1
    else:
        if j%2==1:
            Ans+=1
        j=1

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

import numpy as np

N = int(input())
L = np.sort(np.array(list(map(int, input().split(" ")))))[::-1]

cnt = 0
for i in range(0, len(L)-2):
    l1 = L[i]
    rest = L[i+1:]
    for i2 in range(0, len(rest)-1):
        l2 = rest[i2]
        rest2 = rest[i2+1:]
        if sum(rest2 > l1 - l2) == 0:
            break
        else:
            cnt += sum(rest2 > l1 - l2)

print(cnt)

### FIXED CODE ###

from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i):
        m = L[i]-L[j]
        k = bisect_right(L, m)
        n = max(0, j-k)
        ans+=n
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(int(N/R) + 1):
    for j in range(int(N/G) + 1):
        tmp = int((R * i) + (G * j))
        if N >= tmp and (N - tmp) % B == 0:
            ans += 1
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(int(N/R) + 1):
    for j in range(int(N/G) + 1):
        tmp = int((R * i) + (G * j))
        if N >= tmp and (N - tmp) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

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

tmp = set()

for val in range(m):
    l,r = map(int,input().split())
    tmp = set(list(range(l,r+1)))
    if val ==0:
        seki = tmp
    else:
        seki = seki & tmp

print(len(list(seki)))


### FIXED CODE ###

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

l_L,r_L = [],[]

for val in range(m):
    l,r = map(int,input().split())

    l_L.append(l)
    r_L.append(r)

r = min(r_L)
l = max(l_L)

if r-l >= 0:
    print(r-l+1)
else:
    print(0)
### BUGGY CODE ###

import numpy as np

n = int(input())
l = np.array(list(map(int, input().split())))

l = np.sort(l)[::-1]

cnt = 0
for a in range(n):
    for b in range(a, n):
        for c in range(b, n):
            if a != b and b != c and c != a:
                if l[a] > (l[b] + l[c]):
                    break
                if l[a] < (l[b] + l[c]) and l[b] < (l[a] + l[c]) and l[c] < (l[a] + l[b]):
                    cnt += 1

print(cnt)


### FIXED CODE ###

import numpy as np
import bisect

n = int(input())
l = np.array(list(map(int, input().split())))

# l.sort()

# ans = 0
# for a in range(n - 2):
#     for b in range(a + 1, n - 1):
#         ans += bisect.bisect_left(l, l[a] + l[b]) - (a + 1)
# print(ans)

res = 0
l = sorted(l)
for i in range(1, n - 1):
    b = l[i]
    for j in range(0, i):
        a = l[j]
        res += bisect.bisect_left(l, a + b) - (i + 1)
print(res)
### BUGGY CODE ###

import itertools


N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

res = 0
if M < N - 1:
    print(res)
else:
    for course in itertools.permutations(edges, N - 1):

        if 0 not in course[0]:
            continue

        num_of_v = [0] * N
        for edge in course:
            num_of_v[edge[0]] += 1
            num_of_v[edge[1]] += 1
        if num_of_v[0] != 1 and max(num_of_v) != 2:
            continue

        vertex = [False] + [True] * (N - 1)
        v = 0
        for edge in course:
            if v in edge:
                nv = edge[0] if v == edge[1] else edge[1]
                if vertex[nv]:
                    vertex[nv] = False
                    v = nv
                    continue
            break
        else:
            res += 1
    print(res)


### FIXED CODE ###

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

edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)


def dfs(node, track):
    if len(track) == N:
        global res
        res += 1
    else:
        for dst in [x for x in edges[node] if x not in track]:
            dfs(dst, track + tuple([dst]))


res = 0
dfs(0, tuple([0]))
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
    if t[-2]!=a[1]:
        ans=0
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans*=min(t[i+1],a[i+1])
print(ans%(10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
            break
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
            break
    if t[-2]!=a[1]:
        ans=0
        break
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans=(ans*(min(t[i+1],a[i+1])))%(10**9+7)
print(ans)
### BUGGY CODE ###

def solve():
    MOD = 10**9 + 7

    N = int(input())
    As = list(map(int, input().split()))

    ans = 0
    for d in range(60):
        nums = [0, 0]
        for A in As:
            b = (A>>d) & 1
            nums[b] += 1
        v = nums[0]*nums[1]
        v *= pow(2, d, MOD)
        ans += v
        ans %= MOD

    print(ans)


solve()


### FIXED CODE ###

MOD = 10**9 + 7

N = int(input())
As = list(map(int, input().split()))

ans = 0
for d in range(60):
    sumXOR = 0
    num0, num1 = 0, 0
    for A in As:
        if (A>>(59-d))&1:
            num1 += 1
        else:
            num0 += 1
#    print('d:', d, '/ num0:', num0, '/ num1:', num1)
    sumXOR += (num0 * num1) % MOD
    sumXOR %= MOD
    ans *= 2
    ans += sumXOR
    ans %= MOD

print(ans)