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


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], abs(H[i]-H[i+j])+dp[i])
#        print(dp)

print(dp[-1])

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], abs(H[i]-H[i+j])+dp[i])
#        print(dp)

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

#ABC C121
import sys
n, m = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

L = sorted(L, key=lambda x:x[0])
total=0
for a, b in L:
    if m-b>=0:
        m-=b
        total+=a*b
        if m==0:
            print(total)
            break
    else:
        for i in range(b):
            total +=a
            m -=1
            if m==0:
                print(total)
                break

### FIXED CODE ###

#ABC C121
import sys
n, m = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

L = sorted(L, key=lambda x:x[0])
total=0
for a, b in L:
    if m-b>=0:
        m-=b
        total+=a*b
        if m==0:
            print(total)
            break
    else:
        total +=a*m
        print(total)
        break
### BUGGY CODE ###

h,w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())
import sys
sys.setrecursionlimit(200000)
dy = [0,0,1,-1]
dx = [1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x] = 1
    if s[y][x] == "#":
        check[0] += 1
    else:
        check[1] += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx)
ans = 0
was = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check = [0,0]
            dfs(j,i)
            ans += check[0] * check[1]
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=[]
        lH.append((j,i,0))#0が黒
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.pop()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='#':
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num
ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)
### BUGGY CODE ###

num = int(input())
a_i = list(map(int, input().split()))
anslist = [0] * (num + 1)
printlist = [0] * (num + 1)
for x in range(num):
    val = x + 1
    cnt = a_i.count(val)
    if cnt <= 1: anslist[val] = 0
    else: anslist[val] = cnt * (cnt - 1) // 2

ans = sum(anslist)
for x in range(num):
    val = a_i[x]
    cnt = a_i.count(val)
    if printlist[val] != 0: 
        print(printlist[val])
        continue
    if cnt <= 1: print(ans)
    else: 
        sa = anslist[val] - (cnt - 1) * (cnt - 2) // 2
        print(ans - sa)
        printlist[val] = ans - sa


### FIXED CODE ###

import collections

num = int(input())
a_i = list(map(int, input().split()))
anslist = collections.Counter(a_i)

ans = 0
for x in anslist.values():
    ans += x * (x - 1) // 2
for x in range(num):
    val = a_i[x]
    cnt = anslist[val]
    print(ans - (cnt - 1))
### BUGGY CODE ###

a,b,k = map(int,input().split())
l = []
for i in range(a,b+1):
    l.append(i)
for j in sorted(set(l[:k]) | set(l[-k:])):
    print(j)

### FIXED CODE ###

a,b,k = map(int,input().split())
l = []
if b-a >= k:
    for i in range(k):
        l.append(a+i)
    for i in range(k):
        l.append(b-i)
    l = sorted(set(l))
    for i in range(len(l)):
        print(l[i])
else:
    for i in range(b-a+1):
        print(a+i)
### BUGGY CODE ###

x1, y1, x2, y2 = map(int, input().split())
k = (x2-x1)**2+(y2-y1)**2
for i in range(-100, 101):
    for j in range(-100, 101):
        for p in range(-100, 101):
            for q in range(-100, 101):
                if (i-x2)**2+(j-y2)**2 == k and (p-x1)**2+(q-y1)**2 == k and (i-p)**2+(j-q)**2 == k:
                    print(i, j, p, q)
                    exit()

### FIXED CODE ###

def resolve():
    x1, y1, x2, y2 = map(int, input().split())
    print(x2-y2+y1, y2+x2-x1, x1-y2+y1, y1+x2-x1)
resolve()
### BUGGY CODE ###

N, A ,B =map(int,input().split())
blue =0
while N >0:
    blue += min(A,N)
    N -= min(A,N)
    N = max(N-B,0)
print(blue)

### FIXED CODE ###

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

print(N//(A+B)*A+min(N%(A+B),A))
### BUGGY CODE ###

from sys import stdin
from collections import deque

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
lr_list = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]


for l, r in lr_list:
    stack = deque([])
    S2 = S[l-1:r]
    count = 0
    #print(S2)
    for s in S2:
        # スタックが空なら
        if not stack:
            stack.append(s)
        # スタックの一番上がAなら
        elif stack[-1] == "A" and s == "C":
            stack.pop()
            count += 1
        else:
            stack.append(s)
    print(count)
        

### FIXED CODE ###

from sys import stdin
from collections import deque

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
lr_list = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

#result_list = []
count = 0

result_list = deque([])

for i in range(N):
    result_list.append(count)
    if S[i] != "A":
        continue
    try:
        if S[i+1] == "C":
            count += 1
    except:
       pass

for l, r in lr_list:
    print(result_list[r-1] - result_list[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a,b = map(int, input().split())
c = str(input())

for i in range(0,b):
    d,e = map(int, input().split())
    print(c[d-1:e].count("AC"))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import accumulate
a,b = map(int, input().split())
c = str(input())
d = [list(map(int, input().split())) for i in range(0,b)]

flg = []
for i in range(a-1):
    moji = c[i:i+2]
    if moji == "AC":
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in d:
    print(flg2[a[1]-1] - flg2[a[0]-1])
### BUGGY CODE ###

N = int(input())
count = 0
for A in range(1,N):
    for B in range(1,N):
        for C in range(1,N):
            if N == A*B+C:
                count += 1
                # print(A,B,C)
print(count)

### FIXED CODE ###

N = int(input())
NR = int(N**0.5)
count = 0
if int(N/2)-N/2 == 0:
    for i in range(1,int(N/2)):
        if int(N/i)-N/i == 0:
            count += int(N/i)-1
        else:
            count += int(N/i)
else:
    for i in range(1,int(N/2)+1):
        if int(N/i)-N/i == 0:
            count += int(N/i)-1
        else:
            count += int(N/i)

count += int(N/2)
print(count)
### BUGGY CODE ###

k,s = map(int, input().split())

ans = 0
for i in range(min(s,k)+1):
    for j in range(min(s-i,k)+1):
        for l in range(min(s-i-j,k)+1):
            if i + j + l == s:
                ans += 1

print(ans)

### FIXED CODE ###

k,s = map(int, input().split())

ans = 0
for i in range(min(s,k)+1):
    for j in range(i,min(s-i,k)+1):
        l = s - i - j
        if k >= l >= j: 
            if i == j and j == l:
                ans += 1
            elif i != j and j!= l and i != l:
                ans += 6
            else:
                ans += 3

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

H,W = [int(i) for i in input().split(' ')]

MAP = []
SUM = 0 
for i in range(H):
    tmp = list(input())
    SUM += tmp.count('#')
    MAP.append(tmp)

# print(MAP,SUM)

S = [[0,0]]

while True:
    tmp = []
    for s in S:
        if not s[1] == W -1:
            if MAP[s[0]][s[1]+1] == '.':
                a = [s[0], s[1]+1]
                tmp.append(a)
        
        if not s[0] == H -1:
            if MAP[s[0]+1][s[1]] == '.':
                a = [s[0]+1, s[1]]
                tmp.append(a)
    S = tmp
    if len(s) == 0:
        print(-1)
        exit()

    if [H-1,W-1] in S:
        move = H + W - 1
        print(H*W - move - SUM)
        exit()


### FIXED CODE ###

from collections import deque

def main():
    R,C= map(int,input().split())

    S = [0,0]

    mv = [[1,0],[-1,0],[0,-1],[0,1]]
    MAP = []
    flg = 0
    block = 0
    for _ in range(R):
        t = list(input())
        block += t.count('#')
        MAP.append(t)
    stack = deque([S])
    MAP_c = [[None]*C for _ in range(R)]
    MAP_c[0][0] = 1
    while stack:
        v = stack.popleft()
        for m in mv:
            u = [v[0]+m[0],v[1]+m[1]]
            if u[0] >=0 and u[0] < R and u[1] >= 0 and u[1] < C and MAP[u[0]][u[1]] == '.':
                MAP[u[0]][u[1]] = '#'
                MAP_c[u[0]][u[1]] = MAP_c[v[0]][v[1]] + 1
                stack.append(u)
                if u == [R-1,C-1]:
                    flg = 1

        if flg == 1:
            break

    if flg == 1:
        a = MAP_c[R-1][C-1]
        print(R*C - a - block)
    else:
        print(-1)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())

dp = [[[-1]*(n+1) for _ in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
for d in range(n+1):
  for c in range(n+1-d):
    for b in range(n+1-d-c):
      if b == c == d == 0:
        continue
      dp[b][c][d] = 1
      if b != 0:
        dp[b][c][d] += b/n*dp[b-1][c][d]
      if c != 0:
        dp[b][c][d] += c/n*dp[b+1][c-1][d]
      if d != 0:
        dp[b][c][d] += d/n*dp[b][c+1][d-1]
      dp[b][c][d] /= (b+c+d)
      dp[b][c][d] *= n

L = [0]*3
for a in map(int, input().split()):
  L[a-1] += 1
ans = dp[L[0]][L[1]][L[2]]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
N=[0]*2020
for i in reversed(range(n)):
    N[int(s[i:])%2019]+=1
ans=s.count('0')
ans+=N[0]
for j in N:

    ans+=j*(j-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
s=input()
n=len(s)
N=defaultdict(int)
x=0
for i in reversed(range(n)):
    x+=int(s[i])*pow(10,(n-i-1),2019)
    x%=2019
    N[x]+=1
ans=N[0]
for j in N.values():
    ans+=j*(j-1)//2
print(ans)
### BUGGY CODE ###

from math import sqrt


def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i <= sqrt(n):
        if n % i == 0:
            return False
        else:
            i += 1
    return True


Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    count = 0
    for j in range(l, r+1, 2):
        count += is_prime(j) * is_prime((j+1)//2)
    print(count)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

Q = int(input())

L = []
R = []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)


def primes(max_r):
    is_prime = [True] * (max_r + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(max_r**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, max_r + 1, i):
            is_prime[j] = False
    return [i for i in range(max_r + 1) if is_prime[i] and is_prime[(i+1)//2]]


max_r = max(R)
ps = primes(max_r)

S = [0]
for i in range(1, max_r+1):
    if i in ps:
        S.append(S[i-1]+1)
    else:
        S.append(S[i-1])


for i in range(Q):
    print(S[R[i]] - S[L[i]-1])
### BUGGY CODE ###

n,c=[int(i) for i in input().split()]
s=[]
t=[]
for _ in range(n):
  a=[int(i) for i in input().split()]
  s.append(a[0]-0.5)
  t.append(a[1])

s.sort()
t.sort()
x=0
m=0
while s !=[] or t !=[]:
  if s==[]:
    x-=1
    del t[0]
  elif t==[]:
    x+=1
    del s[0]
  else:
    if s[0] < t[0]:
      x+=1
      del s[0]
    else:
      x-=1
      del t[0]
  m=max(m,x)
print(m)

### FIXED CODE ###

n,c=[int(i) for i in input().split()]
s0=[]
t0=[]
for _ in range(n):
  a=[int(i) for i in input().split()]
  s0.append((a[0],a[2]))
  t0.append((a[1],a[2]))
s1=set(s0)
t1=set(t0)
s2=list(s1.difference(t0))
t2=list(t1.difference(s0))
s=[i[0]-0.5 for i in s2]
t=[i[0] for i in t2]

s.sort()
t.sort()
x=0
m=0
si=0
ti=0
while si != len(s):
  if s[si] < t[ti]:
    x+=1
    si+=1
  else:
    x-=1
    ti+=1
  m = max(m,x)
print(m)
### BUGGY CODE ###

from collections import Counter as cnt
n = int(input())
s = list(input())

count = cnt(s)
num_rest = []
for i in range(n):
  count[s[i]] -= 1
  rest = 0
  for value in count.values():
    if value != 0:
      rest += 1
  num_rest.append(rest)
#print(num_rest)

checked = set()
total = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i] + s[j] not in checked:
      checked.add(s[i] + s[j])
      total += num_rest[j]
print(total)

### FIXED CODE ###

n = int(input())
s = list(input())

def search(s, c, left):
  for idx in range(left, len(s)):
    if s[idx] == c:
      return idx
  return -1

total = 0
for keta1 in range(10):
  first_keta1 = search(s, str(keta1), 0)
  if first_keta1 == -1 or first_keta1 >= n-2:
    continue
  for keta2 in range(10):
    first_keta2 = search(s, str(keta2), first_keta1 + 1)
    if first_keta2 == -1 or first_keta2 >= n-1:
      continue
    for keta3 in range(10):
      first_keta3 = search(s, str(keta3), first_keta2 + 1)
      if first_keta3 != -1:
        total += 1
print(total)
### BUGGY CODE ###

S = int(input())
j = 0
for i in range(int(S**0.5),0,-1):
    if S%i == 0:
        j = S//i
        break

print(0,0,i,0,0,j)


### FIXED CODE ###

S = int(input())

y = (S+10**9-1)//10**9
x = y*(10**9)-S

print(0,0,10**9,1,x,y)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
BC = [list(map(int, input().split(' '))) for _ in range(Q)]
temp = A
for i in range(Q):
    temp = [BC[i][1] if a == BC[i][0] else a for a in temp]
    print(sum(temp))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
BC = [list(map(int, input().split(' '))) for _ in range(Q)]
cnt = [0 for _ in range(10**5+1)]
sum_a = sum(A)
# print(A)
for i in range(len(A)):
    cnt[A[i]] += 1
    # print(A[i])
    # print(cnt[A[i]])
for bc in BC:
    # print(sum_a)
    # print(cnt.count(bc[0]))
    # print((bc[1]-bc[0])*cnt.count(bc[0]))
    sum_a = sum_a + (bc[1]-bc[0])*cnt[bc[0]]
    print(sum_a)
    cnt[bc[1]] += cnt[bc[0]]
    cnt[bc[0]] = 0
### BUGGY CODE ###

n,m=[int(x) for x in input().split()]
v=[int(x) for x in input().split()]
def insert(list, n): 
	j=0
	for j in range(len(list)): 
		if list[j] > n: 
			break
      
	list = list[:j] + [n] + list[j:] 
	return list
v.sort()
while (m>0):
	k=v[-1]/2
	del v[-1]
	v=insert(v,k)
	m-=1
i,sum=0,0
while(i<n):
	sum+=int(v[i])
	i+=1
print(sum)

### FIXED CODE ###

#coding:utf-8
 
import heapq
 
N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))
 
print(total)
### BUGGY CODE ###

N, M = map(int, input().split())
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = map(int, input().split())
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
for i in range(M):
    for j in range(dem[i][1]-dem[i][0]):
        if br_flag[dem[i][0] - 1 + j]:
            break
        elif j == dem[i][1] - dem[i][0] - 1:
            br_flag[dem[i][1]-2] = True
            count += 1
print(count)


### FIXED CODE ###

N, M = map(int, input().split())
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = map(int, input().split())
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
a = 0
for i in range(M):
    if a < dem[i][0]:
        br_flag[dem[i][1]-2] = True
        a = dem[i][1] - 1
        count += 1
print(count)
### BUGGY CODE ###

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

for i in range(0,a[0]*2+1,2):
    ans = [0]*n
    ans[0] = i
    for j in range(1,n):
        tmp = (a[j-1]-ans[j-1]//2)*2
        if tmp%2 == 0:
            ans[j] = tmp
        else:
            break
    if (ans[-1]//2 + ans[0]//2) == a[-1]:
        print(*ans)
        exit()

### FIXED CODE ###

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

s = sum(a)
s1 = 0
for i in range(1,n,2):
    s1 += a[i]

ans = [s-s1*2]
for i in range(1,n):
    ans.append((a[i-1]-ans[i-1]//2)*2)

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

n,k=map(int,input().split())
lst_1=list(map(int,input().split()))
# print(lst_1)
lst_2=[]
for i in range(n-k+1):
    temp=1
    for j in range(k):
        temp*=lst_1[i+j]
    lst_2.append(temp)
for i in range(len(lst_2)-1):
    if lst_2[i]<lst_2[i+1]:
        print("Yes")
    else:print("No")

### FIXED CODE ###

n,k=map(int,input().split())
lst_1=list(map(int,input().split()))
# print(lst_1)
lst_2=[]
for i in range(n-k):
    temp=1
    temp=lst_1[i+k]/lst_1[i]
    lst_2.append(temp)
for i in lst_2:
    if i>1:
        print("Yes")
    else:print("No")
### BUGGY CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019

s,d = 0,1

for i in S:
    if i == 0:
        s += i *d
        d *= 10

    else:
        s += i *d
        amari[s%2019] += 1
        d *= 10


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2

counter += amari[0]

print(int(counter))

### FIXED CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().split()[0]
t = input().split()[0]

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range((len(t))):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

i = len(s)
j = len(t)
ans = ''
while i>0 and j>0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans = s[i] + ans
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().split()[0]
t = input().split()[0]

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range((len(t))):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

i = len(s)
j = len(t)
ans = ''
while i>0 and j>0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans = s[i] + ans
print(ans)
### BUGGY CODE ###

import sys,random

rand = random.randint

def prime(n):
	if n == 2:
		return True
	if n == 1 or n & 1 == 0:
		return False
	d = n-1
	while d & 1 == 0:
		d >>= 1
	for i in range(20):
		a = rand(1,n-1)
		t = d
		y = pow(a, t, n)
		while t != n-1 and y != 1 and y != n-1:
			y = pow(y,2,n)
			t <<= 1
		if y != n-1 and t & 1 == 0:
			return False
	return True

a = [prime(i) for i in range(1000000)]

for s in sys.stdin:
	i = int(s)
	print(a[:i+1].count(True))

### FIXED CODE ###

import sys

a = [True] * 1000000

for i in range(2,1000000):
	if(a[i-1]):
		for j in range(i**2-1, 1000000, i):
			a[j] = False

for s in sys.stdin:
	print(a[1:int(s)].count(True))
### BUGGY CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    binArr = [[0 for i in range(60)] for j in range(n)]
    cnt=[0]*60
    for i in range(n):
        b = bin(arr[i])[2:]
        lenb = len(b)
        for j in range(lenb):
            binArr[i][j] = int(b[lenb-1-j])
            cnt[j]+=binArr[i][j]
    ans=[0]*60
    answer = 0
    for i in range(n):
        for j in range(60):
            # 1: cnt[j]
            # 0: n-cnt[j]
            cnt[j]-=binArr[i][j]
            if binArr[i][j] == 0:
                ans[j] += cnt[j]
            else:
                ans[j] += (n-cnt[j]-i-1)
    x=1
    for i in range(60):
        answer += ans[i]*x
        answer %= mod
        x*=2
    print(answer)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    binArr = [[0 for i in range(60)] for j in range(n)]
    cnt=[0]*60
    for i in range(n):
        b = bin(arr[i])[2:]
        lenb = len(b)
        for j in range(lenb):
            binArr[i][j] = int(b[lenb-1-j])
            cnt[j]+=binArr[i][j]
    ans=[0]*60
    answer = 0
    for i in range(n):
        for j in range(60):
            # 1: cnt[j]
            # 0: n-cnt[j]
            cnt[j]-=binArr[i][j]
            if binArr[i][j] == 0:
                ans[j] += cnt[j]
            else:
                ans[j] += (n-cnt[j]-i-1)
    x=1
    for i in range(60):
        answer += ans[i]*x
        answer %= mod
        x*=2
        x%=mod
    print(answer)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------