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

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)


### FIXED CODE ###

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)
### BUGGY CODE ###

n=int(input())

pnt=[]
for i in range(n):
  pnt.append(list(map(int,input().split())))
pnt.sort(key=lambda x:abs(x[0])+abs(x[1]),reverse=True)
mn=list(reversed(pnt))
mx=0

for i in range(min(n,16000)):
  for j in range(i+1,min(n,16000)):
    mx=max(abs(pnt[i][0]-pnt[j][0])+abs(pnt[i][1]-pnt[j][1]),mx)
    mx=max(abs(pnt[i][0]-mn[j][0])+abs(pnt[i][1]-mn[j][1]),mx)
print(mx)


### FIXED CODE ###

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

z=[]
w=[]

for i in pnt:
  z.append(i[0]+i[1])
  w.append(i[0]-i[1])
print(max(max(z)-min(z),max(w)-min(w)))
### BUGGY CODE ###

MOD = 998244353

N, K = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(K)]

S = set()
for l, r in lr:
    for j in range(l, r+1):
        S.add(j)

dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N+1):
    for s in S:
        if i+s <= N:
            dp[i+s] += dp[i]
            dp[i+s] %= MOD

print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= MOD
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

MOD = 998244353


lr = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N+10)
add(1, 2, 1)
for i in range(1, N+1):
    dp[i] = query(i, i+1) % MOD
    for l, r in lr:
        if i+l > N+1: continue
        add(l+i, min(i+r+1, N+1), dp[i])
    

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

(k, s),  = [list(map(int, s.split())) for s in open(0)]

pairs = []
for i in range(k + 1):
    for j in range(k + 1):
        if s - i - j <= k and s - i - j >= 0 :
            l = s - i - j
            pairs.append((i, j, l))
print(len(pairs))

### FIXED CODE ###

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

num = 0
for x in range(sk[0] + 1):
	for y in range(sk[0] + 1):
		if x + y <= sk[1] and sk[1] - x - y <= sk[0]:
			num += 1
        

print(num)
### BUGGY CODE ###

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    E[v].sort()
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
c = 1
for v in range(1, N):
    available = {c: True for c in range(1, K+1)}
    for u in E[v]:
        if v > u:
            e_idx = edge_idx[(u, v)]
            available[edge_color[e_idx]] = False
            continue
        e_idx = edge_idx[(v, u)]
        while not available[c]: c = (c + 1) % K if c + 1 != K else K
        edge_color[e_idx] = c
        c = (c + 1) % K if c + 1 != K else K
for i in range(N-1):
    print(edge_color[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
q = deque([(-1, 1)])
visited = {i: False for i in range(1, N+1)}
while q:
    p, v = q.popleft()
    visited[v] = True
    if p == -1:
        used = -1
    else:
        used = edge_color[edge_idx[(p, v)]] if p < v else edge_color[edge_idx[(v, p)]]
    c = 1
    for u in E[v]:
        if visited[u]: continue
        q.append((v, u))
        if c == used: c += 1
        if u < v:
            edge_color[edge_idx[(u, v)]] = c
        else:
            edge_color[edge_idx[(v, u)]] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])
### BUGGY CODE ###

from collections import Counter
n=int(input())
s=[]
res=0
for i in range(n):
	t=input()
	s.append(Counter(t))
for i in range(n):
	for j in range(i+1,n):
		if s[i]==s[j]:
			res += 1
print(res)

### FIXED CODE ###

P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
n=int(input())
A=[1]*n

for i in range(n):
	s=input()
	for j in range(10):
		A[i] *= P[ord(s[j])-97]

res=0
A.sort()
cnt=0

for i in range(n-1):
		if A[i]==A[i+1]:
			cnt += 1
		else:
			res += cnt*(cnt+1)//2
			cnt=0
if cnt != 0:
	res += cnt*(cnt+1)//2
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
alist=[ 0 for i in range(n)]
for _ in a:
    alist[_ - 1] += 1
for j in aset:
    ans += (a.count(j)*(a.count(j)-1)) // 2
for u in a:
    print(ans - alist[u - 1]+1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
aset=list(set(a))
ans=0
al=[0]*200000
for i in a:
    al[i]+=1
for j in aset:
    k=al[j]
    ans+=(k*(k-1))//2
for u in a:
    print(ans-al[u]+1)
### BUGGY CODE ###

from decimal import Decimal, getcontext

getcontext().prec = 20

N = int(input())
p = [0] + list(map(Decimal, input().split()))

#print(p)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率

dp[1][0] = 1-p[1]
dp[1][1] = p[1]

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i][j] = (dp[i-1][j-1] * p[i] + dp[i-1][j] * (1-p[i]))
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])

ans = Decimal(0)

for k in range(-(-N//2), N+1):
    ans += dp[N][k]

print(ans)

### FIXED CODE ###

import numpy as np

N = int(input())
p = [0] + list(map(float, input().split()))

dp = np.zeros((3100, 3100))
#dp[i, j] = i枚目までのコインを投げて，表の個数がj枚である確率
#pythonのlistだと遅いので，numpyにおけるベクトル漸化式としてdpを埋めていく

dp[1, 0] = 1-p[1]
dp[1, 1] = p[1]

for i in range(2, N + 1):
    dp[i] = np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (1-p[i])
    #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
    #つまり，dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i])
    #numpyを使ってベクトル漸化式と見ることで，for_loopを一層分解消。
    #print(i, j, dp[i][j])

ans = 0

for k in range(-(-N//2), N+1):
    ans += dp[N, k]

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

A, B, C, K = map(int, input().split())

wa = 0
wa += A
nokori = K - A - B

while nokori != 0:
    if C != 0:
        wa -= 1
        C -= 1
        nokori -= 1
    else:
        break

print(wa)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

nokori = K - A - B

wa = 0
while True:
    if A >= K:
        wa += K
        break
    else:
        wa += A
    if C >= nokori:
        wa -= nokori
        break
    else:
        wa -= C
        break

print(wa)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)


    new = [0]*n
    for i in range(n):
        new[i] = [i]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print(len(el)+1)
                        for e in el:
                            print(e+1)
                        print(go+1)

                        exit()
                    tank.append(el+[go])
        new = tank
        
    print(-1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

edge = [[] for _ in [0]*n]
back = [[] for _ in [0]*n]

for _ in [0]*m:
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    back[b-1].append(a-1)


res = [None]*(n+1)

for end in range(n):
    for start in edge[end]:
        cost = [-1]*n
        cost[start] = 0
        new = [start]
        tank = []
        judge = True

        while len(new) > 0 and judge:
            tank = []
            for fr in new:
                for go in edge[fr]:
                    if cost[go] < 0:
                        cost[go] = cost[fr] + 1
                        tank.append(go)
                        if go == end:
                            judge = False
            new = tank

        
        if cost[end] >= 0 and cost[end] < len(res):
            p = end
            res = [p+1]
            while p != start:
                for e in back[p]:
                    if cost[p] == cost[e]+1:
                        p = e
                        res.append(p+1)
                        break
if res[0] == None:
    print(-1)
else:                      
    print(len(res))
    for e in res:
        print(e)
### BUGGY CODE ###

N=int(input())
Sarr1=[]
Sarr2=[]
for _ in range(N):
    s=input()
    if Sarr1.count(s)==0:
        Sarr1.append(s)
        Sarr2.append(0)
    else:
        i=Sarr1.index(s)
        Sarr2[i]+=1
ans=[]
for i in range(len(Sarr2)):
    if Sarr2[i]==max(Sarr2):
        ans.append(Sarr1[i])
    else:
        pass
FA=sorted(ans)
for z in FA:
    print(z)


### FIXED CODE ###

from collections import Counter

N=int(input())
S=[]

for _ in range(N):
    s=input()
    S.append(s)

c=Counter(S)
arr=c.most_common()

maxnum=arr[0][1]
ans=[]

for i in range(len(arr)):
    if arr[i][1]==maxnum:
        ans.append(arr[i][0])        
    else:
        break
FA=sorted(ans)
for j in FA:
    print(j)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)

first = a_list[:, 0]
target = n_index[first[first] == n_index]
a_index[target] += 1
ans = 1
for i in range(N * (N-1) // 2):

    cand = a_list[target, a_index[target]]
    target_index = (a_list[cand, a_index[cand]] == target)
    target = np.unique(np.hstack((cand[target_index], target[target_index])))
    if len(target) == 0:
        break

    a_index[target] += 1
    ans += 1

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from sys import stdin
# import numpy as np
from collections import deque
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

if count == (N * (N-1) // 2):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

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

counter = 0
for r in range(int(N / R) + 1):
    for g in range(int((N - R * r) / G) + 1):
        if (N - R * r - G * g) % B ==0:
            b = int((N - R * r - G * g) / B)
            #print(r,g,b)
            if b >= 0:
                counter += 1
print(counter)

### FIXED CODE ###

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

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

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

def one_n_sum(x):
  return (1+x)*x//2

list00 = []
for i in range(0, n):
  list00.append(one_n_sum(p[i])/p[i])

def larger(x,y):
  if x>=y:
    return x
  else:
    return y

m = 0
for j in range(0, n-k+1):
  m_cal = sum(list00[j:j+k])
  m = larger(m,m_cal)
  
print(m)


### FIXED CODE ###

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

kouho=0
lis=[0]*n
lis[0]=(1+p[0])/2
for i in range(0,n):
  if i>=1:
    lis[i]=lis[i-1]+(1+p[i])/2
  if i==k-1:
    kouho=lis[i]
  if i>k:
    if lis[i]-lis[i-k]>kouho:
      kouho=lis[i]-lis[i-k]
print(kouho)
### BUGGY CODE ###

from functools import partial, reduce
xor = partial(reduce, lambda x,y: x^y)
n = int(input())
xs = list(map(int, input().split()))
sections = (xs[i:j] for i in range(n) for j in range(i+1, n+1))
print(sum(sum(x)==xor(x) for x in sections))

### FIXED CODE ###

n = int(input())
xs = list(map(int, input().split()))
 
ans = 0
sums = xs[0]
xors = xs[0]
i, j = 0, 0

while True:
  if xors == sums:
    ans += j - i + 1
    j += 1
    if j >= n: break
    sums += xs[j]
    xors ^= xs[j]
  else:
    sums -= xs[i]
    xors ^= xs[i]
    i += 1
    
print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
aaa = sorted(aaa)
len_aaa = len(aaa)
cccbbb = []
for i in range(m):
    b, c = list(map(int, input().split(' ')))
    cccbbb += [c] * b
    cccbbb = sorted(cccbbb)[::-1]
    if len(cccbbb) > len(aaa):
        cccbbb = cccbbb[:len_aaa]
len_cccbbb = len(cccbbb)
if len_aaa < len_cccbbb:
    print(sum([max(a, c) for a, c in zip(aaa, cccbbb[:len_aaa])]))
elif len_aaa >= len_cccbbb:
    print(sum([max(a, c) for a, c in zip(aaa, cccbbb + [0] * (len_aaa - len_cccbbb))]))


### FIXED CODE ###

import bisect
n, m = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
aaa = sorted([-a for a in aaa])[::-1]
len_aaa = len(aaa)

cccbbb = []
for i in range(m):
    b, c = list(map(int, input().split(' ')))
    cccbbb.append((-c, b))
cccbbb = sorted(cccbbb)
ccc = []
for c, b in cccbbb:
    ccc += [c] * b
    if len(ccc) > len_aaa:
        break
ans = 0
for i in range(len_aaa):
    c = ccc[i] if i < len(ccc) else 0
    ans += min(aaa[i], c)
print(abs(ans))
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    B = []
    M = 80 * H * W
    for _ in range(H):
        a = tuple(map(int, input().split()))
        A.append(a)
    for _ in range(H):
        b = tuple(map(int, input().split()))
        B.append(b)
    l = [[[0] * (M+1) for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                t = abs(A[0][0] - B[0][0])
                l[i][j][t] = 1
            else:
                t = abs(A[i][j] - B[i][j])
                for k in range(M+1):
                    if i > 0 and l[i-1][j][k] == 1:
                        if k + t <= M:
                            l[i][j][k+t] = 1
                        if k - t >= 0:
                            l[i][j][k-t] = 1
                        if t - k >= 0:
                            l[i][j][t-k] = 1
                    if j > 0 and l[i][j-1][k] == 1:
                        if k + t <= M:
                            l[i][j][k+t] = 1
                        if k - t >= 0:
                            l[i][j][k-t] = 1
                        if t - k >= 0:
                            l[i][j][t-k] = 1
    for k in range(M):
        if l[-1][-1][k] == 1:
            return k
print(main())



### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = []
    B = []
    M = 80 * (H + W)
    for _ in range(H):
        a = tuple(map(int, input().split()))
        A.append(a)
    for _ in range(H):
        b = tuple(map(int, input().split()))
        B.append(b)
    AB = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            AB[i][j] = abs(A[i][j] - B[i][j])
    l = [set([]) for _ in range(W)]
    lt = [set([]) for _ in range(W)]
    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                lt[j].add(AB[0][0])
            else:
                t = AB[i][j]
                if i > 0:
                    for k in l[j]:
                        lt[j].add(k+t)
                        lt[j].add(abs(k-t))
                if j > 0:
                    for k in lt[j-1]:
                        lt[j].add(k+t)
                        lt[j].add(abs(k-t))
        l = lt
        lt = [set([]) for _ in range(W)]
    return min(l[-1])
print(main())
### BUGGY CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s[nexty][nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.append([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
### BUGGY CODE ###

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

mod=10**9+7
ans=0

for i in range(60):
    a=0
    for x in A:
        if x>>i&1:
            a+=1
    ans+=a*(N-a)*pow(2,i,mod)
    ans%=mod

    
print(ans)

### FIXED CODE ###

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

mod=10**9+7
ans=0
cnt=[[0]*2 for _ in range(60)]

for x in A:
    for i in range(60):
        a=x%2
        x//=2
        cnt[i][a]+=1

for p,q in enumerate(cnt):
    i,j=q
    ans+=((i*j)%mod)*pow(2,p,mod)
    ans%=mod
    
print(ans)