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

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

routes = []
for i in range(m):
    x,y = map(int, input().split())
    routes.append([x-1,y-1])
    # routes[i] = routes[i] - [1,1] #道の番号をずらす

rooms = [0 for i in range(n)] # 行ったら1,まだなら0
marks = [0 for i in range(n)] # 部屋におく道標
roads = [0 for i in range(m)]
rooms_rate = [[0]] # １回目、２回目、３回目…に行ける部屋
rooms[0] = 1

turn = 0
for i in rooms_rate:
    newrate = []
    for j in rooms_rate[turn]: #turn回目に行ける部屋を調べる
        for k in range(m):
            if(roads[k] == 1):
                continue
            else:
                a = routes[k][0]
                b = routes[k][1]
            if (j == a and rooms[b] == 0):
                rooms[b] = 1
                marks[b] = a
                newrate.append(b)
                roads[k] = 1
            elif (j == b and rooms[a] == 0):
                rooms[a] = 1
                marks[a] = b
                newrate.append(a)
                roads[k] = 1
    rooms_rate.append(newrate)
    if (len(newrate) == 0):
        break
    turn = turn + 1


if(all(rooms) == True):
    print('Yes')
    for i in range(1,n):
        print(str(int(marks[i]) + 1))

else:
    print('No')

### FIXED CODE ###

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

routes = [[] for i in range(n)]
for i in range(m):
    x,y = map(int, input().split())
    routes[x-1].append(y-1)
    routes[y-1].append(x-1)


rooms = [0 for i in range(n)] # 行ったら1,まだなら0
marks = [0 for i in range(n)] # 部屋におく道標
rooms_rate = [[0]] # ０回目、１回目、２回目、３回目…に行ける部屋
rooms[0] = 1

turn = 0
for i in rooms_rate:
    newrate = []
    for j in rooms_rate[turn]: #(turn)回目に行けた部屋から行ける部屋を調べる
        for k in routes[j]: 
            if (rooms[k] == 0): #行ったことのない部屋なら
                rooms[k] = 1
                marks[k] = j # 道標をセット
                newrate.append(k)
    rooms_rate.append(newrate)
    if (len(newrate) == 0): #新しく行けなくなったら終わり
        break
    turn = turn + 1


if(all(rooms) == True):
    print('Yes')
    for i in range(1,n):
        print(str(int(marks[i]) + 1))

else:
    print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def checker(n):
    ans = 0
    for a in range(1, 101):
        if a ** 2 + 2 * a > n:
            break
        for b in range(1, 101-a):
            if a * 2 + b * 2 > n:
                break
            _rest = n - a ** 2 - b ** 2
            for c in range(1, 101-a-b):
                if (c + a) * (c + b) == _rest:
                    ans += 1
                    break
                elif (c + a) * (c + b) > _rest:
                    break
    return ans


def main():
    N = int(input().strip())
    for n in range(1, N + 1):
        print(checker(n))
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def checker():
    ans = [0] * 10001
    for a in range(1, 101):
        for b in range(1, 101):
            for c in range(1, 101):
                n = a * a + b * b + c * c + a * b + b * c + c * a
                if n > 10000:
                    continue
                else:
                    ans[n] += 1
    return ans


def main():
    N = int(input().strip())
    ans = checker()
    for n in range(1, N + 1):
        print(ans[n])
    return


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

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

def main():
    n = int(input())
    ans =1
    for i in range(1,n+1):
        ans *=i
    print(ans%1000000007)

if __name__=="__main__":
    main()

### FIXED CODE ###

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

import math

def main():
    n = int(input())
    ans =math.factorial(n)
    print(ans%1000000007)

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

import heapq

R = lambda: map(int, input().split())
n, m = R()
a = list(R())
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    for i in range(b):
        if a[0] >= c:
            break
        heapq.heapreplace(a, c)
print(sum(a))


### FIXED CODE ###

import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: map(int, input().split())
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        heapq.heappop(a)
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heappush(a, (x, y))
    heapq.heappush(a, (c, b - i))
print(sum(starmap(mul, a)))
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
d=[[]for _ in range(n**2)]
start=[0]*(n**2)
for i in range(n):
	for j in range(n-2):
		p=[i,a[i][j]-1];q=[i,a[i][j+1]-1]
		if i>a[i][j]-1:
			p=[a[i][j]-1,i]
		if i>a[i][j+1]-1:
			q=[a[i][j+1]-1,i]
		start[p[0]*n+p[1]]+=1
		start[q[0]*n+q[1]]=-10**7
		d[p[0]*n+p[1]].append(q[0]*n+q[1])
st=-1
for i in range(n**2):
	if start[i]>0:
		st=i
		break
if st==-1:
	print(-1)
	exit()
stack=[st]
deep=[1]*(n**2)
while stack:
	p=stack.pop()
	for x in d[p]:
		stack.append(x)
		deep[x]=deep[p]+1
print(max(deep))

### FIXED CODE ###

def main():
	from collections import deque
	n=int(input())
	battle=n*(n-1)//2
	lis=[[] for i in range(battle)]
	num=[-1]*(n**2)
	cnt=-1
	for x in range(n**2):
		if x//n<x%n:
			cnt+=1
			num[x]=cnt
	for i in range(n):
		a=list(map(int,input().split()))
		for j in range(n-2):
			x=a[j]-1
			y=a[j+1]-1
			px=num[min(i*n+x,x*n+i)]
			py=num[min(i*n+y,y*n+i)]
			lis[px].append(py)
	node_in=[0]*(battle)
	for i in range(battle):
		for x in lis[i]:
			node_in[x]+=1
	zero=deque([])
	days=[10**9]*(battle)
	for i in range(battle):
		if node_in[i]==0:
			zero.append(i)
			days[i]=1
	while zero:
		r=zero.popleft()
		for x in lis[r]:
			node_in[x]-=1
			if node_in[x]==0:
				zero.append(x)
				days[x]=days[r]+1
	if 10**9 in days:
		print(-1)
	else:
		print(max(days))
if __name__ == '__main__':
	main()
### BUGGY CODE ###

import sys
from bisect import bisect_left,bisect

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,m=map(int,input().split())



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

if len(A)>10**5:
	Al=A[-10**5:]
	Af=A[:-10**5]
	for i in range(m):
		Al.insert(bisect_left(Al,max(Al)//2),max(Al)//2)
		del Al[n]
	print(sum(Al)+sum(Af))
	
else:
	for i in range(m):
		A.insert(bisect_left(A,max(A)//2),max(A)//2)
		del A[n]
	
	print(sum(A))



### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍

heapq.heapify(a)

for i in range(m):
    minimum=heapq.heappop(a)
    mini=((minimum*(-1))//2)*(-1)
    heapq.heappush(a,mini)
    
print(-sum(a))
### BUGGY CODE ###

N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  for j in range(M):
    if i|c[j]<2**N:
      X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

### FIXED CODE ###

N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  if X[i]<10**10:
    for j in range(M):
      if i|c[j]<2**N:
        X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)
### BUGGY CODE ###

s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
sum_mod = 0
for m in mod:
    sum_mod += m*(m-1)//2
print(sum_mod)

### FIXED CODE ###

s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
    x %= 2019
print(sum([m*(m-1)//2 for m in mod]))
### BUGGY CODE ###

N = int(input())


def query(i):
    print(i, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


"""
初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
まずis_okを定義すべし
ng, okは,とり得る最小の値-1,とり得る最大の値+1
"""

# 適当にいじる
ng = -1  # ind=0が条件を満たすこともあるため
ok = N  # ind=len(a)-1が条件を満たさないこともあるため

# いじらない
# okとngのどちらが大きいかわからないことを考慮
while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
return False




### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]

ans = 0
for i in range(1, n+1):
    low = sorted(p[:i])
    if low[0] == p[i-1]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ppp = list(map(int, input().split()))
curr = 10 ** 6
ans = 0
for p in ppp:
    if p < curr:
        ans += 1
        curr = p
print(ans)
### BUGGY CODE ###

import sys
import itertools

sys.setrecursionlimit(10**8)

def find(x,table):	#xの根を返す	
	if table[x] == x:
		return x
	else:
		table[x] = find(table[x],table)	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,table,rank):	#xとyを繋げる
	x = find(x,table)	
	y = find(y,table)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y,table):
	if find(x,table) == find(y,table):
		return True
	else:
		return False

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

table_car = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank_car  = [1 for i in range(N)]	#木の長さ
table_tr  = [i for i in range(N)] 
rank_tr   = [1 for i in range(N)]

for i in range(0,K):
	a,b = map(int, input().split())
	union(a-1,b-1,table_car,rank_car)
	
for i in range(0,L):
	a,b = map(int, input().split())
	union(a-1,b-1,table_tr,rank_tr)
	
iters = list(itertools.combinations(range(N),2))
ans_li = [1 for i in range(N)]

for iter in iters:
	a,b = iter
	if check(a,b,table_car) and check(a,b,table_tr):
		ans_li[a] += 1
		ans_li[b] += 1

print (' '.join(map(str,ans_li)))

### FIXED CODE ###

import sys
import itertools
from collections import defaultdict

sys.setrecursionlimit(10**8)

def find(x,table):	#xの根を返す	
	if table[x] == x:
		return x
	else:
		table[x] = find(table[x],table)	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,table,rank):	#xとyを繋げる
	x = find(x,table)	
	y = find(y,table)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y,table):
	if find(x,table) == find(y,table):
		return True
	else:
		return False

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

table_car = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank_car  = [1 for i in range(N)]	#木の長さ
table_tr  = [i for i in range(N)] 
rank_tr   = [1 for i in range(N)]

for i in range(0,K):
	a,b = map(int, input().split())
	union(a-1,b-1,table_car,rank_car)
	
for i in range(0,L):
	a,b = map(int, input().split())
	union(a-1,b-1,table_tr,rank_tr)
	
ar = [(find(i,table_car),find(i,table_tr)) for i in range(N)]
dd = defaultdict(int)
for s in ar:
    dd[s] += 1
	
ans =[]
for i in range(N):
    ans.append(dd[ar[i]])
	
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
miss = 0
for i in range(n):
    s = p[0:i]
    if not s:
        continue
    if p[i] > max(s):
        miss += 1
        continue
 
    s = sorted(s,reverse=True)
    #print(s)
    for j in range(i):
        if p[i] > s[j]:
            miss += 1
            break

print(n-miss)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
cnt = 0
t = p[0]

for i in range(n):
    if t >= p[i]:
        cnt += 1
        t = p[i]


print(cnt)
### BUGGY CODE ###

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

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

E = []
for i in range(X):
    for j in range(Y):
        E.append(A[i] + B[j])
E.sort(reverse=True)

F = []
for i in range(min(X * Y, K)):
    for j in range(Z):
        F.append(E[i] + C[j])
F.sort(reverse=True)

for i in range(K):
    print(F[i])


### FIXED CODE ###

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

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

Comb = []
for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            Comb.append(A[i] + B[j] + C[k])

Comb.sort(reverse=True)
for i in range(K):
    print(Comb[i])
### BUGGY CODE ###

def calc(value):
    res = 0
    while True:
        if len(value) == 1 or len(value) == 0:
            break
        elif value[0] != value[-1] and value[0] != "x" and value[-1] != "x":
            res = -1
            break
        elif value[0] == value[-1]:
            value.pop(0)
            value.pop()
        else:
            value.extend("x") if value[0] == "x" else value.insert(0, "x")
            value.pop(0)
            value.pop()
            res += 1
    return res


def main():
    value = list(input())
    print(calc(value))


if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()
ns = s.replace('x', '')
if s == s[::-1]:
    print(0)
elif ns != ns[::-1]:
    print(-1)
else:
    cnt = 0
    i = 0
    j = len(s)-1
    while(i<j):
        if s[i]=='x' and s[j]!='x':
            cnt += 1
            j += 1
        elif s[i]!='x' and s[j]=='x':
            cnt += 1
            i -= 1
        i += 1
        j -= 1
    print(cnt)
### BUGGY CODE ###

a,b,n=map(int,input().split())
l=[]
for i in range(1,n+1):
    m=(a*i//b)-a*(i//b)
    l.append(m)
print(max(l))

### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(n,b-1)
print(a*x//b)
### BUGGY CODE ###

import sys
from operator import itemgetter
N,M = map(int,input().split())
A = [0] * M
#B = [0] * M
for i in range(M):
    A[i] = list(map(int,input().split()))
    if A[i][0] > A[i][1]:
        A[i][0],A[i][1] = A[i][1],A[i][0]
A = sorted(A, key = itemgetter(0))        
C = [set()]
if M != 0:
    C[0].add(A[0][0])
    C[0].add(A[0][1])
else:
    print(1)
    sys.exit()
for i in range(1,M):
    for j in range(len(C)):
        if A[i][0] in C[j]:
            C[j].add(A[i][1])
        elif A[i][1] in C[j]:
            C[j].add(A[i][0])
        else:
            C.append({A[i][0],A[i][1]})
ans = 0
for j in range(len(C)):
    if len(C[j]) > ans:
        ans = len(C[j])
print(ans)

### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
N, M = map(int,input().split())
A = [None] * M
B = [None] * M
for i in range(M):
    A[i], B[i] = map(int,input().split())
uf = UnionFind(N)
for j,h in zip(A,B):
    uf.Unite(j,h)
print(min(uf.root)*(-1))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    edge = np.array([list(map(int,input().split())) for _ in range(N)])
    use = np.array([[True for _ in range(N)] for _ in range(N)])
    count = 0
    for k in range(N):
        for i in range(N):
            if k == i:
                continue
            for j in range(N):
                if (k == j or i == j):
                    continue
                if edge[i][j] == edge[i][k] + edge[k][j]:
                    use[i][j] = False
                elif edge[i][j] > edge[i][k] + edge[k][j]:
                    print(-1)
                    exit()
    
    ans = 0
    for i in range(N):
        ans += sum(edge[i,i:]*use[i,i:])
        
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        edge[i][i] = 10**10
        
    ans = 0
    for i in range(N):
        for j in range(i):
            d = min(a+b for a,b in zip(edge[i],edge[j]))
            if edge[i][j] > d:
                print(-1)
                exit()
            elif edge[i][j] < d:
                ans += edge[i][j]

    print(ans)    

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

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=[]
total=0
for i in range(N-1):
    for j in range(i+1,N):
        sum.append(((number[i]%MOD)*(number[j]%MOD))%MOD)
total=0
for i in range(len(sum)):
    total=(total+sum[i])%MOD
print(total)

### FIXED CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=sum(number)
s=sum%MOD
ans=0
for i in number:
    s-=i
    s%=MOD
    ans+=s*i
    ans%=MOD
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
import itertools
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
K = int(input())
cnt = 0
    
for v in itertools.product(range(1,K+1),repeat=3):
    cnt += gcd(v[0],v[1],v[2])
    
print(cnt)



### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
K = int(input())
cnt = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            cnt += gcd(i,j,k)
            
print(cnt)
### BUGGY CODE ###

k = int(input())
a = []

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

for i in range(1, k+1):
    for j in range(1, k+1):
        x = gcd(i, j)
        for l in range(1, k+1):
            y = gcd(l, x)
            a.append(y)
print(sum(a))

### FIXED CODE ###

import math
k = int(input())
a = []
for i in range(1, k+1):
    for j in range(1, k+1):
        x = math.gcd(i, j)
        for l in range(1, k+1):
            y = math.gcd(l, x)
            a.append(y)
print(sum(a))
### BUGGY CODE ###

A, B, N = map(int,input().split())
fivex = 0
i = 1
ans = 0
while True:
    fivex = i * B
    if (fivex % A == 0):
        x = fivex // A
    else:
        x = fivex // A + 1
    if x > N:
        break
    if i - A *  int(x / B) > ans:
        ans = i - A *  int(x / B)
    i += 1

print(ans)

### FIXED CODE ###

A, B, N = map(int,input().split())
fivex = 0
i = 1
ans = 0
x = 0
# ans_x = -((-1)*A*N // B)
# if ans_x>N:
#     ans_x -= 1
# print(ans_x)
# print(int(A*ans_x/B)-A*int(ans_x/B))
while x <= B:
    x = -((-1)*i*B // A)
    if x > N:
        break
    now = i - A *  int(x / B)
    if now > ans and x <= N:
        # print(x)
        ans = now
    i += 1

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

n=int(input())
a=list(map(int,input().split()))
d=0
for i in range(0,n-1):
    for j in range(i+1,n):
        b=a[i]
        c=a[j]
        if b==c:
            d=1
            break
    if d==1:
        break
if d==0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

n=int(input())
a=set(map(int,input().split()))
b=len(a)
if n==b:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from collections import Counter
x=Counter(a)
for i in range(1,n+1):
  print(x[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(n)]
for i in range(n):
    if i%2 == 0:
        l[i] = 2*(sum(a)//2 - sum(a[i+1::2]) - sum(a[:i:2]))
    else:
        l[i] = 2*(sum(a)//2 - sum(a[i+1::2]) - sum(a[1:i:2]))
print(" ".join(map(str, l)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
a_sum = sum(a)//2
a2 = a + a
l = [0 for i in range(2*n)]
for i in range(2*n):
    if i == 0:
        l[i] = 0
    elif i == 1:
        l[i] = a2[0]
    else:
        l[i] = l[i-2] + a2[i-1]
for i in range(n):
    ans.append(2*(a_sum - l[i+n-1] + l[i]))
print(" ".join(map(str, ans)))
### BUGGY CODE ###

import bisect
n,m=map(int, input().split())
pl=[0]*100000
yl=[0]*100000
ol=[[] for i in range(100001)]
for i in range(m):
    pl[i],yl[i] = map(int, input().split())
    bisect.insort_left(ol[pl[i]], yl[i])
for i in range(m):
    x = bisect.bisect_right(ol[pl[i]], yl[i])
    print("%06d%06d" % (pl[i], x))


### FIXED CODE ###

import bisect
n,m=map(int, input().split())
pl=[0]*100000
yl=[0]*100000
ol=[[] for i in range(100001)]
for i in range(m):
    pl[i],yl[i] = map(int, input().split())
    ol[pl[i]].append(yl[i])
for i in range(1,n+1):
    ol[i].sort()
for i in range(m):
    print("%06d%06d" % (pl[i], bisect.bisect_right(ol[pl[i]], yl[i])))
### BUGGY CODE ###

from sys import stdin
def main():
    n = int(stdin.readline().rstrip())
    a = list(map(int,stdin.readline().rstrip().split()))
    mod = 10**9+7
    point = 0
    for i in range(61):
        now = sum(1 for j in a if(j >> i)&1)
        point += now*(n-now)*(2**i)
        point %= mod
    print(point)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
point = 0
for i in range(61):
    now = 0
    for j in a:
        now += (j >> i&1)
    now *= n-now
    now %= mod
    for k in range(i):
        now *= 2
        now %= mod
    point += now
    point %= mod
print(point)