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

import sys
sys.setrecursionlimit(10**6)

# 入力
N, K = map(int, input().split())
H = [int(i) for i in input().split()]

# メモ用のDPテーブル生成
dp = [float("inf") for i in range(N)]

# 初期値をセット
dp[0] = 0

# 足場iへたどり着く最小コストを返す
def rec(i):
    # ベースケース
    if i == 0:
        return 0
    
    # メモをチェック
    if dp[i] < float("inf"):
        return dp[i]
    
    # 足場iの最小コスト
    for j in range(1, K+1):
        if i - j >= 0:
            # 最小コストをメモ
            dp[i] = min(dp[i], rec(i-j) + abs(H[i] - H[i-j]))
    
    return dp[i]

print(rec(N-1))

### FIXED CODE ###

import numpy as np

# 入力
N, K = map(int, input().split())
H = np.array([int(i) for i in input().split()])

# ndarray型のDPテーブルを生成
dp = np.zeros(N, dtype=int)
# 初期値をセット
dp[0] = 0

# 各足場へたどり着く最小コストを調べる
for i in range(1, N):
    s = max(0, i-K)
    dp[i] = min(dp[s:i] + np.abs(H[i] - H[s:i])) # iより前の足場のコストに足す

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


def sieve(n):
    nums = [i+1 for i in range(2, n, 2) if (i+1) % 3 != 0 and (i+1) % 5 !=0] # リスト内包表記で3,5の倍数をはじく
    ans = [2,3,5] # 3,5は素数なので加えてしまう
    while nums[0] <= n**0.5:
        for i in range(nums[0]**2, nums[-1]+1, nums[0]):
            if i in nums: nums.remove(i)
            ans.append(nums.pop(0))
            ans += nums
    return ans


A,B =map(int,input().split())
if A<B:
    A,B =B,A
foo = 1
while foo != 0:
    A,B = B, A%B
    #print(A,B)
    foo = B

foo =A

plis = sieve(1000)
ans = 1
for p in plis:
    if foo%p==0:
        ans += 1
        foo = foo//p
    while foo%p ==0:
        foo = foo//p



plis = sieve(max(7,foo))

for p in plis:
    if  foo % p ==0:
        ans += 1
        foo = foo//p
        if foo < 1:
            break
print(ans)



### FIXED CODE ###


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

#素数列挙
def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum



#素因数分解(素数列挙が必要)
def pfact(N):
    plis = searchPrimeNum(int(N**0.5+1))
    ans = 1
    for p in plis:
        if N%p == 0:
            ans += 1
            N = N//p
        while N%p == 0:
            N = N//p
        if N == 1:
            break
    if N != 1:
        ans += 1
    return ans

#互除法(最大公約数)
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

print(pfact(gcd(A,B)))
### BUGGY CODE ###

import sys
import numpy as np

read = lambda : sys.stdin.readline().rstrip('\n')
tint = lambda x: [int(x) for x in x.split()]
ttuple = lambda x: tuple(int(x) for x in x.split())

def main():
    n, k = tint(read())
    stones = ttuple(read())
    inf = 10**9
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                v = dp[i]+abs(stones[i]-stones[step])
                if v < dp[step]:
                    dp[step] = v
    print(dp[-1])


if __name__ == '__main__':    
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def GCM(a,b):
    while(a%b!=0):
        a,b = b,a%b
    return b

def calc(a,b):
    count_two_a = 0
    count_two_b = 0
    while(a%2==0):
        a //= 2
        count_two_a += 1
    while(b%2==0):
        b //= 2
        count_two_b += 1
    if count_two_a != count_two_b:
        return 0

    return pow(2,count_two_a) * a * b // GCM(a,b)





def main():
    N,M = LI()
    A = LI()

    tmp = A[0]

    for i in range(1,N):
        tmp = calc(tmp,A[i])
        if tmp==0:
            print(0)
            return
    tmp = tmp//2

    ans = M//tmp
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def GCM(a,b):
    while(a%b!=0):
        a,b = b,a%b
    return b

def main():
    N,M = LI()
    A = LI()

    count_two = 0
    while(A[0]%2==0):
        A[0] //= 2
        count_two += 1
    pow_two = pow(2,count_two)

    for i in range(1,N):
        if A[i]%pow_two != 0:
            print(0)
            return
        A[i] //= pow_two
        if A[i]%2 == 0:
            print(0)
            return

    tmp = A[0]

    for i in range(1,N):
        tmp = tmp * A[i] // GCM(tmp,A[i])
        if tmp > M:
            print(0)
            return

    ans = M//(tmp*pow_two//2)
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


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

H, W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            L[h][w] = L[h][w-1] + 1
            U[h][w] = U[h-1][w] + 1
        if S[h][W-w-1] == ".":
            R[h][-w-1] = R[h][-w] + 1
        if S[H-h-1][w] == ".":
            D[-h-1][w] = D[-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, R[h][w] + L[h][w] + U[h][w] + D[h][w] - 3)
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            L[h][w] = L[h][w-1] + 1
            U[h][w] = U[h-1][w] + 1
        if S[h][W-w-1] == ".":
            R[h][-w-1] = R[h][-w] + 1
        if S[H-h-1][w] == ".":
            D[-h-1][w] = D[-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, R[h][w] + L[h][w] + U[h][w] + D[h][w] - 3)
print(ans)
### BUGGY CODE ###

[X,K,D]=[int(_) for _ in input().split()]
X=abs(X)
X/=D
#print(k1,k2)
for _ in range(K//2):
  X = min([abs(X-2), abs(X), abs(X+2)])
  #print(X)
if K%2 == 1:
  X = min([abs(X-1), abs(X+1)])
  #print(X)
print(abs(int(X*D)))

### FIXED CODE ###

[X,K,D]=[int(_) for _ in input().split()]
X=abs(X)
Y=X//D
if Y <= K:
  X-=Y*D
  if (K-Y)%2 != 0:
    X = abs(X-D) if abs(X-D) < abs(X+D) else abs(X+D)
else:
  X-=K*D
print(X)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

mods = [0] * (N+1)
for i in range(N):
  mods[i] = int(S[i:]) % P
c = dict()
for m in mods:
  c[m] = c.get(m, 0)+1

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c[mods[i]]

print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()

mods = [0] * (N+1)
for i in range(N-1, -1, -1):
  mods[i] = (int(S[i])*pow(10, N-i-1, P)+mods[i+1]) % P
c = dict()
for m in mods:
  c[m] = c.get(m, 0)+1

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c[mods[i]]

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

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

aa = [0]*(n+1)

for i in range(n):
    aa[i+1] = aa[i] + a[i]

ans = sum(a)
for i in range(n):
    ans = min(ans,abs(sum(a)-2*aa[i]))

print(ans)

### FIXED CODE ###

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

aa = [0]*(n+1)

for i in range(n):
    aa[i+1] = aa[i] + a[i]

sm = sum(a)
ans = sm
for i in range(n):
    ans = min(ans,abs(sm-2*aa[i]))

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

a,b,c=map(int,input().split(" "))
count=0
while(1):
    if c%a==0:
        count+=1
    a+=1
    
    if a==b:
        break
    
print(count)




### FIXED CODE ###

a,b,c=map(int,input().split(" "))
count=0
while(a<=b):
    if c%a==0:
        count+=1
    a+=1

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

n, m = map(int, input().split())
query = []
for i in range(m):
    query.append(list(map(int, input().split())))
result =  [[] for i in range(n)]
 
for city in query:
    result[city[0]-1].append(city[1])
 
for i in result:
    i.sort()
 
for city in query:
    rank = result[city[0]-1].index(city[1])+1
    resultStr = "{}{}".format(str(city[0]).zfill(6), str(rank).zfill(6))
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append([CY, CX])  # スタート地点
# 各頂点について2*2の幅優先する？
INF = float("inf")
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[INF]*W for _ in range(H)]
# print(distant)
# 更新されるなら追加
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()  # 現在位置
    # 壁に当たったらワープ開始
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == ".":
            # 道の場合はコスト0で移動できる
            if distant[ny][nx] > distant[cy][cx]:
                distant[ny][nx] = distant[cy][cx]
                q.append([ny, nx])
        # 新しい移動先が壁の場合
        elif gridgraph[ny][nx] == "#":
            # 周囲5*5の道に+1で到達する
            for i in range(-2, 3, 1):
                for j in range(-2, 3, 1):
                    target_y, target_x = cy+i, cx+j
                    if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                        continue
                    else:
                        if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                            distant[target_y][target_x] = distant[cy][cx]+1
                            q.append([target_y, target_x])
if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])

# print(distant)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.appendleft((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])
### BUGGY CODE ###

n,w = map(int,input().split())
dp = [[0 for i in range(w+1)]for j in range(n+1)]

for i in range(n):
    weight,value = map(int,input().split())
    for j in range(w+1):
        if j >= weight:
            dp[i+1][j] = max(dp[i][j-weight]+value,dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])


### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  w,v=map(int,input().split())
  for j in range(W+1):
    if j>=w:
      dp[i+1][j]=max(dp[i][j-w]+v,dp[i][j])
    else:
      dp[i+1][j]=dp[i][j]
print(dp[N][W])
### BUGGY CODE ###

N=int(input())
L=[int(i) for i in input().split()]
L1=sorted(L)
a=L[N//2]
b=L[N//2-1]
 
for i in range(N):
  L2=L1[:]
  L2.remove(L[i])
  print(L2[N//2-1])


### FIXED CODE ###

N=int(input())
L=[int(i) for i in input().split()]
L1=sorted(L)
a=L1[N//2]
b=L1[N//2-1]
for i in range(N):
  if L[i]<a:
    print(a)
  else:
    print(b)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, q = map(int, input().split())
es = [[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
use = [1] * n
cnt = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x


def dfs(v, c):
    k = c + cnt[v]
    cnt[v] = k
    use[v] = 0
    for i in es[v]:
        if use[i]:
            dfs(i, k)


dfs(0, 0)
print(*cnt)


### FIXED CODE ###

#再帰のlimitを解除
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
#何と繋がっているか（隣接リスト）
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

memo = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    memo[p] += x

#深さ優先探索 累積和
def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        #1つ先に情報を流す
        memo[nv] += memo[v]
        #dfsを更新
        dfs(nv, v)

dfs(0, -1)

print(*memo)
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

a_dict={}
b_dict={}
for i in range(h):
  a=lnii()
  for j in range(w):
    a_dict[a[j]]=(i,j)
    b_dict[(i,j)]=a[j]

q=int(input())
for i in range(q):
  l,r=nii()
  ans=0
  cy,cx=a_dict[l]
  while l!=r:
    l+=d
    ny,nx=a_dict[l]
    ans+=abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

  print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

a_dict={}
for i in range(h):
  a=lnii()
  for j in range(w):
    a_dict[a[j]]=(i,j)

b_dict={}
for i in range(1,d+1):
  num=i
  cy,cx=a_dict[num]
  b_dict[num]=0
  while num+d<=h*w:
    num+=d
    ny,nx=a_dict[num]
    b_dict[num]=b_dict[num-d]+abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)
### BUGGY CODE ###

import sys

n, m = map(int, input().split())
nums = []

# for i in range(n):
#     nums.append(i + 1)

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

    if i == 0:
        for j in range(l, r + 1):
            nums.append(j)

    nums = list(filter(lambda x: l <= x <= r, nums))

    if len(nums) == 0:
        print(0)
        sys.exit()

print(len(nums))

### FIXED CODE ###

n, m = map(int, input().split())
lr = []

for i in range(m):
    lr.append(list(map(int, input().split())))

lmax = 0
mmin = 10**5

for i in range(m):
    lmax = max(lmax, lr[i][0])
    mmin = min(mmin, lr[i][1])

print(max(0, mmin - lmax + 1))
### BUGGY CODE ###

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1
    
MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]

import itertools
X = list(itertools.product(h_list, w_list))

ans = MAX_h+MAX_w
check = 0

if len(X)<=3*10**5:
    for i in range(M):
        if (h[i],w[i]) in X:
            check += 1

if len(X)==check:
    ans -= 1
    
print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1

MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]


ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if counter_h[h[i]]==MAX_h and counter_w[w[i]]==MAX_w:
        check += 1

if len(h_list)*len(w_list)==check:
    ans -= 1

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

from collections import deque
n = int(input())
de = deque([int(input()) for _ in range(n)])
for i in range(n):
  f = de[0]
  del de[0]
  print(max(de))
  de.append(f)

### FIXED CODE ###

from collections import deque
n = int(input())
li = [int(input()) for _ in range(n)]
m = max(li)
ind = li.index(m)
li.sort()
mm= li[n-2]
for i in range(n):
  if i == ind:
    print(mm)
  else:
    print(m)
### BUGGY CODE ###

# coding: utf-8

N = int(input())

votes = []

for _ in range(N):
    votes.append([int(n) for n in input().split()])

# an = votes[0][0]
# bn = votes[0][1]
#
# for a, b in votes:
#     if a == b :
#         an = bn = max(an, bn)
#     elif a < b:
#         az = a
#         while(a)
#     elif a > b:

sum = 0
befa = 0
befb = 0

for a, b in votes:
    a_m = a
    b_m = b
    while(a < befa or b < befb):
        a += a_m
        b += b_m
    t = a + b;
    i = 1
    while(t * i < sum):
        i += 1
    sum = t * i
    befa = a
    befb = b

print(sum)



### FIXED CODE ###

# coding: utf-8
import math
from decimal import Decimal

N = int(input())

votes = []

for _ in range(N):
    votes.append([Decimal(n) for n in input().split()])

befa = 1
befb = 1

for a, b in votes:
    kakeru = Decimal(max(math.ceil(befa / a), math.ceil(befb / b)))
    befa = a * kakeru
    befb = b * kakeru

print(int(befa)+int(befb))
### BUGGY CODE ###

import sys

n = input()
for i2 in range(n):
    seq1 = raw_input()
    seq2 = raw_input()
    
    a,b = len(seq1)+1, len(seq2)+1
    length = [[0 for i in range(b)] for j in range(a)]

    for i in range(a):
        for j in range(b):
            if i==0 or j==0:
                length[i][j]=0
            else:
                if seq1[i-1] == seq2[j-1]:
                    length[i][j] = length[i-1][j-1] + 1
                else:
                    length[i][j] = max(length[i-1][j], length[i][j-1])
    print length[a-1][b-1]

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)