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

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()


### FIXED CODE ###

import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


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

N = int(input())
tmp = 0
for i in reversed(range(len(str(N)))):
  n, N = N//(10**i), N%(10**i)
  tmp += n
N = tmp 
if N%9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = input()
M = N
tmp = 0
for i in range(len(N)):
  n, M = int(M[0]), M[1:]
  tmp += n
if tmp%9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

def main():
    s = input()
    ans = 0
    for i in range(len(s)+1):
        for j in range(i-3):
            if int(s[j:i]) % 2019 == 0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019
    print(ans)

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

#!/usr/bin/env python3

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def main():
    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        while tmp > m:
            tmp >>= 1
            cnt += 1
        ret = 0
        for j in range(1 << cnt):
            weight_sum = 0
            value_sum = 0
            tmp = v
            idx = j
            while tmp > m:
                if idx & 1:
                    weight_sum += W[tmp - 1]
                    if weight_sum > L:
                        break
                    value_sum += V[tmp - 1]
                tmp >>= 1
                idx >>= 1
            else:
                value_sum += dp[tmp][L - weight_sum]
                ret = max(ret, value_sum)
        print(ret)
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

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

class UnionFind():
  def __init__(self,N):
    self.parents=list(range(N))
    self.size=[1]*N
  def find(self,x):
    if self.parents[x]==x:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x,y=self.find(x),self.find(y)
    if x==y:
      return 
    if self.size[x]<self.size[y]:
      self.size[y]+=self.size[x]
      self.parents[x]=y
    else:
      self.size[x]+=self.size[y]
      self.parents[y]=x
      
ans=['1']*N
UF=UnionFind(N)
for i in range(K):
  x,y=map(int,input().split())
  UF.union(x-1,y-1)
tmp=[]
for j in range(L):
  x,y=map(int,input().split())
  if UF.find(x-1)==UF.find(y-1):
    v=UF.find(x-1)
    ans[x-1]=str(int(ans[x-1])+1)
    ans[y-1]=str(int(ans[y-1])+1)
    tmp.append([v,x,y])
searched=[]
for k in range(len(tmp)-1):
  for l in range(k+1,len(tmp)):
    if tmp[k][0]==tmp[l][0]:
      x,y=tmp[k][1],tmp[k][2]
      z,w=tmp[l][1],tmp[l][2]
      tmp_l=[[x,z],[x,w],[y,z],[y,w]]
      if y==z:
        tmp_l.remove([y,z])
      for _ in tmp_l:
        if [tmp[k][0]]+_ not in tmp and _ not in searched :
          x,y=_[0],_[1]
          searched.append([x,y])
          ans[x-1]=str(int(ans[x-1])+1)
          ans[y-1]=str(int(ans[y-1])+1)      
print(' '.join(ans))

### FIXED CODE ###

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

class UnionFind():
  def __init__(self,N):
    self.parents=list(range(N))
    self.size=[1]*N
  def find(self,x):
    if self.parents[x]==x:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x,y=self.find(x),self.find(y)
    if x==y:
      return 
    if self.size[x]<self.size[y]:
      self.size[y]+=self.size[x]
      self.parents[x]=y
    else:
      self.size[x]+=self.size[y]
      self.parents[y]=x

uf1=UnionFind(N)
uf2=UnionFind(N)
for i in range(K):
  x,y=map(int,input().split())
  uf1.union(x-1,y-1)
for j in range(L):
  x,y=map(int,input().split())
  uf2.union(x-1,y-1)

keys=[(uf1.find(x),uf2.find(x)) for x in range(N)]
count={}
for key in keys:
  if key in count:
    count[key]+=1
  else:
    count[key]=1
print(*[count[key] for key in keys])
### BUGGY CODE ###

N, A, B = list(map(int, input().split()))
C=0
for i in range(N):
    if 0 < (i + 1) % (A + B) <= A:
        C += 1
print(C)

### FIXED CODE ###

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

C = N // (A + B) * A
D = N % (A + B)

if 0 <= D and D <= A:
    print(C + D)
else:
    print(C + A)
### BUGGY CODE ###

n = int(input())
seq = input()
ans = 0
for i, val in enumerate(seq[:-2]):
    for j, val in enumerate(seq[i+1:-1], i+1):
        for k, val in enumerate(seq[j+1:], j+1):
            if seq[i] != seq[j] and seq[i] != seq[k] and seq[j] != seq[k] and j-i != k-j:
                ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
seq = input().strip()
ans = 0
r = set()
g = set()
b = set()
for i in range(len(seq)):
    if seq[i] == 'R':
        r.add(i)
    elif seq[i] == 'G':
        g.add(i)
    else:
        b.add(i)

ans = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        if (i+j) % 2 == 0 and ((i + j) //2) in b:
            ans -= 1
        if max(i,j) + (max(i,j) - min(i,j)) in b:
            ans -= 1
        if min(i,j) - (max(i,j) - min(i,j)) in b:
            ans -= 1
        
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
mod=10**18
for i in A:
    ans*=i
if ans>mod:
    ans=-1
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
mod=10**18
for i in A:
    if i==0:
        ans=0
        break
    elif i==1:
        continue
    elif ans!=-1:
        ans=ans*i
        if ans>mod:
            ans=-1
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1 ,N):
            a = L[i]
            b = L[j]
            c = L[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)


ans = 0
for i in range(N - 1 , 1, -1):
    for j in range(i - 1 , 0 , -1):
        #work = l[:j]
        x = l[i] - l[j]
        #idx = bisect.bisect_right(work, x)
        idx = bisect.bisect_right(l, x)
        ans += max(j - idx , 0)
print(ans)
### BUGGY CODE ###

n=int(input())
lis=[]
t=[]
for i in range(n):
    x=input()
    if lis.count(x)==0:
        lis.append(x)
        t.append(1)
    else:
        k=lis.index(x)
        t[k]+=1
m=max(t)
lis1=[]
for i in range(len(t)):
    if t[i]==m:lis1.append(lis[i])
lis1.sort()
for x in lis1:
    print(x)









### FIXED CODE ###

from collections import Counter
c=Counter()
n=int(input())
lis=[]
for _ in range(n):
    lis.append(input())
for x in lis:
    c[x]+=1

max=0
for k,v in c.items():
    if max<v:
        max=v

lis=[]
for k,v in c.items():
    if max==v:
        lis.append(k)
lis.sort()
for x in lis:
    print(x)
### BUGGY CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+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()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i in range(len(s)):
    if s[i] == '?':
        for j in range(10):
            next = j * 10 ** i
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = int(s[i]) * 10**i
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
print(rem[len(s)][5]%mod)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

d = [-1 for _ in range(n)]

def dfs(i, s):
    d[i] = len(s)

    for to in edges[i]:
        if d[to] == -1:
            t = s.copy()
            if t[-1] < a[to]:
                t.append(a[to])
            else:
                t[bisect.bisect_left(t, a[to])] = a[to]

            dfs(to, t)

dfs(0, [a[0]])
for i in range(n):
    print(d[i])


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

inf = 10 ** 10
d = [inf for _ in range(n)]
dp = [inf for _ in range(n)]

def dfs(cur, prev):
    memo = bisect.bisect_left(dp, a[cur])
    memo_v = dp[memo]
    dp[memo] = a[cur]
    d[cur] = bisect.bisect_left(dp, inf)

    for to in edges[cur]:
        if to != prev:
            dfs(to, cur)

    dp[memo] = memo_v

dfs(0, -1)
for i in range(n):
    print(d[i])
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array([int(x) for x in input().split()])
A.sort()
X = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[0])
num_list = [sum(A)]

for b, c in X:
    A[:b][A[:b] <= c] = c
    num_list.append(sum(A))
    A.sort()
print(max(num_list))

### FIXED CODE ###

from sys import stdin
from collections import deque
from operator import itemgetter

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
A = deque(A)
X = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
X.sort(key=itemgetter(1), reverse=True)
D = []
for b, c in X:
    if len(D) < N:
        D.extend([c] * b)
    else:
        break
D = deque(D)

for i in range(len(D) if len(D) < len(A) else len(A)):
    a = A.popleft()
    c = D.popleft()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print(sum(A))
        quit()
print(sum(A))
### BUGGY CODE ###

#import math
#=input()
n=int(input())
#=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10 ** 18:
    ans = -1

print(ans)

### FIXED CODE ###

#import math
#=input()
n=int(input())
#=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

ans = 1
if 0 in a:
    ans = 0
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10 ** 18:
            ans = -1
            break

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

n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
aa=[]
ans=defaultdict(int)
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    ac=Counter(a)
    aa.append(ac)

for i in range(len(aa)):
    for a in aa[i].keys():
        ans[a]+=aa[i][a]

for i in range(1,n):
    print(ans[i])

### FIXED CODE ###

n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
from copy import deepcopy
dist=dijkstra_heap(0)
distx=dijkstra_heap(x-1)
disty=dijkstra_heap(y-1)
counts=[]
for i in range(n-1):
    if i<x-1:
        tmp=[d-i for d in dist[i:]]
        counts.append(Counter(tmp))
    elif x-1<=i<y-1:
        tmp=[min(distx[i]+distx[d], disty[i]+disty[d], abs(d-i)) for d in range(i,n)]
        counts.append(Counter(tmp))
    else:
        tmp=[disty[d]-disty[i] for d in range(i,n)]
        counts.append(Counter(tmp))
ans=defaultdict(int)

for i in range(n-1):
    keys=counts[i].keys()
    for kk in keys:
        ans[kk]+=counts[i][kk]

for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

import collections

n = int(input())

ss = []
for i in range(n):
	s = input()
	ss.append(collections.Counter(s))

c = 0
for i in range(n):
	for k in range(i+1,n):
		if ss[i] == ss[k]:
			c+=1
print(c)

### FIXED CODE ###

import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())

ss = []
for i in range(n):
	s = list(input())
	s.sort()
	ss.append("".join(s))

cs = collections.Counter(ss)
l = list(cs.values())
l.sort(reverse=True)

c = 0
for i in l:
	if i > 1:
		c+= cmb(i,2)
	elif i == 1:
		print(int(c))
		exit()
print(int(c))
### BUGGY CODE ###

from collections import deque

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        for edge in graph[v]:
            u = edge[0]
            d = edge[1]
            if(dist[u] == int(1e10)):
                dist[u] = dist[v] + d
                Q.append(u)
            else:
                if(dist[u] != dist[v] + d):
                    print("No")
                    exit()

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

graph = [[] for i in range(N)] 

for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])

visited = [False] * N

for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")




### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])
    graph[R-1].append([L-1, -D])

dist = [int(1e10)] * N

def bfs(id):
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")
### BUGGY CODE ###

from functools import reduce
N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

ans = (sum(cnt[x:x+K]) for x in range(N-K+1))
print(reduce(max, ans))

### FIXED CODE ###

N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

add = [0]
for i in cnt:
    add.append(add[-1]+i)

ans = [add[i+K]-add[i] for i in range(N-K+1)]

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

# 問題D
import numpy as np
import warnings
warnings.filterwarnings('ignore')

#N = "6 15"
#h = "6 5 5 6 6 4 6 6 3 5 7 2"
#N,W = list(map(int, N.split()))
#w = np.array(list(map(int, h.split()))).reshape(N,2)[:,0]
#v = np.array(list(map(int, h.split()))).reshape(N,2)[:,1]

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    for j in range(0, (W+1)):
        if j - w[i] >= 0:
            dp[i, j] = max(dp[i-1, j], dp[i-1, j-w[i]]+v[i])
        else:
            dp[i, j] = dp[i-1, j]

print(dp[N, W])


### FIXED CODE ###

#問題D
#これだとタイムアウト
import numpy as np
import warnings
warnings.filterwarnings('ignore')

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

n = int(input())
edge = {}
ans = [0 for i in range(n)]
for i in range(n):
    edge[i] = {}
for i in range(n-1):
    u,v,w = map(int, input().split())
    edge[u-1][v-1] = w
    edge[v-1][u-1] = w

def bfsC(pre, now, nowc):
    for node, weight in edge[now].items():
        if node != pre:
            if weight%2 == 0:
                ans[node] = nowc
            else:
                ans[node] = 1 - nowc
            bfsC(now, node, ans[node])
bfsC(-1, 0, 0)
for i in range(n):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)                    #再帰の深さブースト

n = int(input())
edge = [[] for i in range(n)]
ans = [0 for i in range(n)]
for i in range(n-1):
    u,v,w = map(int, input().split())
    edge[u-1].append([v-1,w%2])
    edge[v-1].append([u-1,w%2])

def bfsC(pre, now, nowc):
    for node, weight in edge[now]:
        if node != pre:
            if weight:
                ans[node] = 1-nowc
                bfsC(now, node, 1-nowc)
            else:
                ans[node] = nowc
                bfsC(now, node, nowc)
bfsC(-1, 0, 0)
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N, L = map(int, readline().split())
node = set([1])
for _ in range(N):
    S = list(map(int, readline().strip()))
    pre = 1
    for s in S:
        vn = 2*pre + s
        if vn not in node:
            node.add(vn)
        pre = vn
cnt = 0
for d in node:
    if (2*d in node) ^ (2*d + 1 in node):
        depth = L-d.bit_length()+1
        cnt ^= (-depth&depth)

print('Alice' if cnt else 'Bob')  

### FIXED CODE ###

import sys
readline = sys.stdin.readline

class Node:
    def __init__(self, sigma, depth):
        self.end = False
        self.child = [None] * sigma
        self.depth = depth
    def __setitem__(self, i, x):
        self.child[i] = x
    def __getitem__(self, i):
        return self.child[i]

sigma = 2
root = Node(sigma, 0)
def add_trie(S):
    vn = root
    for cs in S:
        if vn[cs] is None:
            vn[cs] = Node(sigma, vn.depth + 1)
        vn = vn[cs]
    vn.end = True

ans = 0

N, L = map(int, readline().split())

for _ in range(N):
    S = list(map(int, readline().strip()))
    add_trie(S)

cnt = 0
stack = [root]
while stack:
    vn = stack.pop()
    for i in range(2):
        if vn[i] is None:
            r = L - vn.depth
            cnt ^= -r&r
        else:
            stack.append(vn[i])

print('Alice' if cnt else 'Bob')
### BUGGY CODE ###

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

### FIXED CODE ###

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