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

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([i, a, b])

    dp = [[0, set()] for _ in range(W + 1)]

    for i in range(1, W + 1):
        ma = 0
        cp = set()
        for j, w, v in shina:
            if i >= w:
                if j not in dp[i - w][1]:
                    tmp = ma
                    ma = max(ma, dp[i - w][0] + v)
                    if tmp != ma:
                        cp.clear()
                        cp = cp | dp[i - w][1]
                        cp.add(j)

        dp[i][0] = ma
        dp[i][1] = dp[i][1] | cp

    print(dp[W][0])


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


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

import bisect

n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5)+1):
    primes.difference_update(range(i*2, n+1, i))
primes = list(primes)

l_2017 = []
for p in primes[1:]:
    if (p+1)//2 in primes:
        l_2017.append(p)

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(l_2017, r) - bisect.bisect_left(l_2017, l))


### FIXED CODE ###

import bisect

n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5)+1):
    primes.difference_update(range(i*2, n+1, i))
primes = list(primes)

l_2017 = []
for p in primes[1:]:
    if (p+1)//2 in primes:
        l_2017.append(p)

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(l_2017, r) - bisect.bisect_left(l_2017, l))
### BUGGY CODE ###

def gijkstra(n,E,key=1,s=1):
    T, Q = [[float('inf'), -1] for i in range(n+1)], list(range(1,n+1))
    T[s][0] = 0
    while Q:
        u = min(Q, key=lambda x:T[x][0])
        Q.remove(u)
        for e in E[u]:
            v = e[0]
            d = T[u][0] + e[key]
            if T[v][0] > d:
                T[v] = [d, u]
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

### FIXED CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]
### BUGGY CODE ###

x = int(input())
h = x

for i in range(2,10**9):
    if x%i == 0:
        h = i
        break


for i in range(1, 10**9):
    a = i
    b = h-i
    if a**5-b**5 == x:
        print(a, b)
        exit(0)
    b = i-h
    if a**5-b**5 == x:
        print(a, b)
        exit(0)

### FIXED CODE ###

x = int(input())

for a in range(-118, 120):
    for b in range(-119, 119):
        if a**5-b**5 == x:
            print(a, b)
            exit()
### BUGGY CODE ###

# sys.stdin.readline
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        A, B, C, D, E, F = map(int, input().split())

        sousa1 = 0
        sousa2 = 0
        ans = (0, 0, 0)
        while True:
            if sousa1 * 100 * A > F:
                break
            while True:
                water = sousa1 * 100 * A + sousa2 * 100 * B
                if water == 0:
                    continue
                if water > F:
                    sousa2 = 0
                    break
                sugar_limit = water // 100 * E
                sousa3 = 0
                sousa4 = 0
                max_sugar = 0
                while True:
                    if sousa3 * C > sugar_limit:
                        break
                    while True:
                        sugar = sousa3 * C + sousa4 * D
                        if water + sugar > F or sugar > sugar_limit:
                            sousa4 = 0
                            break
                        else:
                            max_sugar = max(max_sugar, sugar)
                        sousa4 += 1
                    sousa3 += 1
                concentration = 100 * max_sugar / (water + max_sugar)
                if ans[0] < concentration:
                    ans = [concentration, water, max_sugar]
                sousa2 += 1
            sousa1 += 1

        print('{} {}'.format(sum(ans[1:]), ans[2]))


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

# sys.stdin.readline
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        A, B, C, D, E, F = map(int, input().split())

        sousa1 = 1
        sousa2 = 0
        ans = (0, 100 * A, 0)
        while True:
            if sousa1 * 100 * A > F:
                break
            while True:
                water = sousa1 * 100 * A + sousa2 * 100 * B
                if water > F:
                    sousa2 = 0
                    break

                sugar_limit = water // 100 * E
                sousa3 = 0
                sousa4 = 0
                max_sugar = 0
                while True:
                    if sousa3 * C > sugar_limit:
                        break
                    while True:
                        sugar = sousa3 * C + sousa4 * D
                        if water + sugar > F or sugar > sugar_limit:
                            sousa4 = 0
                            break
                        else:
                            max_sugar = max(max_sugar, sugar)
                        sousa4 += 1
                    sousa3 += 1
                concentration = 100 * max_sugar / (water + max_sugar)
                if ans[0] < concentration:
                    ans = [concentration, water, max_sugar]
                sousa2 += 1
            sousa1 += 1

        print('{} {}'.format(sum(ans[1:]), ans[2]))


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

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()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
D = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if i * j * k > K:
                break
            D.append(A[i] + B[j] + C[k])
D.sort(reverse=True)
for ans in D[:K]:
    print(ans)

### FIXED CODE ###

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()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
a=0
b=10**9+7
for i in range(len(c)):
    for j in range(i+1,n):
        
        a=(a%b+((c[i]%b*c[j]%b)%b)%b)%b
        
print(a)

### FIXED CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
ans=0
b=10**9+7
sum1=0
for i in range(n):
    ans=(ans+c[i]*sum1)%b
    sum1=(sum1+c[i])%b

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

from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    dam = list(accumulate(damage))
    if h[i]-dam[i] <= 0:
        continue
    bi = bisect.bisect(x,2*d+x[i])
    count = math.ceil((h[i]-dam[i])/a)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count

print(point)

### FIXED CODE ###

from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    if i != 0:
        damage[i] += damage[i-1]
    bi = bisect.bisect(x,2*d+x[i])
    count = max(math.ceil((h[i]-damage[i])/a),0)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count
    
print(point)
### BUGGY CODE ###

h, w = map(int, input().split())
s = []
s_conn = []
for i in range(h):
  s.append(input())
  s_conn.append([[0]*2 for j in range(w)])
 
# 縦にみる
for x in range(w):
  start = 0
  count = 0
  for y in range(h):
    if s[y][x] == '.':
      count += 1
      if y == h-1:
        for i in range(start, y+1):
          s_conn[i][x][0] = count
    else:
      for i in range(start, y):
        s_conn[i][x][0] = count
      count = 0
      start = y+1
 
# 横にみる
for y in range(h):
  start = 0
  count = 0
  for x in range(w):
    if s[y][x] == '.':
      count += 1
      if x == w-1:
        for i in range(start, x+1):
          s_conn[y][i][1] = count
    else:
      for i in range(start, x):
        s_conn[y][i][1] = count
      count = 0
      start = x+1
 
max_all = 0
for i in range(h):
  max_tmp = max(map(sum, s_conn[i]))
  if max_tmp > max_all:
    max_all = max_tmp
print(max_all - 1)

### FIXED CODE ###

h, w = map(int, input().split())
s = []
l = []
r = []
u = []
d = []
for i in range(h):
  s.append(input())
  l.append([0 for j in range(w)])
  r.append([0 for j in range(w)])
  u.append([0 for j in range(w)])
  d.append([0 for j in range(w)])
  
# lみる
for x in range(w):
  for y in range(h):
    if s[y][x] == '.':
      if x == 0:
        l[y][x] = 1
      else:
        l[y][x] = l[y][x-1] + 1
 
# rみる
for x in range(w-1, -1, -1):
  for y in range(h-1, -1, -1):
    if s[y][x] == '.':
      if x == w-1:
        r[y][x] = 1
      else:
        r[y][x] = r[y][x+1] + 1
 
# uみる
for y in range(h):
  for x in range(w):
    if s[y][x] == '.':
      if y == 0:
        u[y][x] = 1
      else:
        u[y][x] = u[y-1][x] + 1
 
# dみる
for y in range(h-1, -1, -1):
  for x in range(w-1, -1, -1):
    if s[y][x] == '.':
      if y == h-1:
        d[y][x] = 1
      else:
        d[y][x] = d[y+1][x] + 1
 
 
max_all = 0
for y in range(h):
  for x in range(w):
    max_tmp = l[y][x] + r[y][x] + u[y][x] + d[y][x]
    if max_tmp > max_all:
      max_all = max_tmp
      
print(max_all - 3)
### BUGGY CODE ###

N = int(input())
H = [-1] + [int(h) for h in input().split()]

max_count = 0
for n in range(1, N):
    count = 0
    for m in range(n, N):
        if H[m] >= H[m+1]:
            count += 1
        else:
            break
    max_count = max(max_count, count)

print(max_count)

### FIXED CODE ###

N = int(input())
H = [-1] + [int(h) for h in input().split()]

count = 0
max_count = 0
for n in range(1, N):
    if H[n] >= H[n+1]:
        count += 1
        max_count = max(max_count, count)
    else:
        count = 0

print(max_count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
tmp = [A[0]]
for i in range(1,N,1):
  #print(i)
  #print(tmp)
  ans += tmp[0]
  tmp = tmp[1:]
  tmp.append(A[i])
  tmp.append(A[i])
print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
d = deque([A[0]])
#tmp = [A[0]]
for i in range(1,N,1):
  #print(i)
  #print(tmp)
  ans += d.popleft()
  d.extend([A[i],A[i]])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3


def main():
    N, K = input_line(int, int)
    A = input_line(*[int for i in range(N)])
    F = input_line(*[int for i in range(N)])
    A.sort()
    F.sort(reverse=True)
    scores = [[a*f, a, f] for a, f in zip(A, F)]
    scores.sort(key=lambda x: x[0], reverse=True)
    while K > 0 and scores[0][1] > 0:
        scores[0][1] -= 1
        scores[0][0] = scores[0][1] * scores[0][2]
        K -= 1
        scores.sort(key=lambda x: x[0], reverse=True)
    print(scores[0][0])


def input_line(*types):
    if len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import numpy as np


def is_ok(mid, K, A, F):
    return np.maximum(A - mid // F, 0).sum() <= K


def main():
    N, K = input_line(int, int)
    A = input_line([int])
    F = input_line([int])
    A = np.array(sorted(A))
    F = np.array(sorted(F, reverse=True))

    ng = -1
    ok = int(1e12)
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if is_ok(mid, K, A, F):
            ok = mid
        else:
            ng = mid
    print(ok)


def input_line(*types):
    if isinstance(types[0], list):
        return [types[0][0](x) for x in input().split()]
    elif len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


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


# -*- coding: utf-8 -*-
import random
import sys

input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def slv():
    N, M, L = list(map(int, input().split()))
    g = [[sys.maxsize]*(N) for _ in range(N)]
    for i in range(N):
        g[i][i] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        if c <= L:
            g[a-1][b-1] = c
            g[b-1][a-1] = c
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    gg = [[sys.maxsize]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if g[u][v] <= L:
                gg[u][v] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                gg[i][j] = min(gg[i][j], gg[i][k] + gg[k][j])

    Q = read_int()
    for _ in range(Q):
        s, t = list(map(int, input().split()))
        c = gg[s-1][t-1]
        if c != sys.maxsize:
            print(c-1)
        else:
            print(-1)



def main():
    slv()
    # N, M, L = read_int_n()
    # ABC = [read_int_n() for _ in range(M)]
    # Q = read_int()
    # ST = [read_int_n() for _ in range(Q)]
    
    # (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

    for i in range(n):
        w[i][i] = 0

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                w[j][k] = min(w[j][k], w[j][i] + w[i][k])

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


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

import sys
from collections import Counter
from bisect import bisect_left

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

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    l = n + 1
    pi=len(aa)
    for k in range(1, n + 1):
        r = l + 1
        l = 0
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa[:pi + 1], m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        pi = i
        print(l)

main()


### FIXED CODE ###

import sys
from collections import Counter
from bisect import bisect_left

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

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    for k in range(1, n + 1):
        l = 0
        r = n // k + 2
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B

        if A==[n]*n:
            break
    
    

    print(*A[:-1])    
    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()
### BUGGY CODE ###

def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    if l < h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r < h and a[r] > a[largest]:
        largest = r

    if largest != i:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[len(a) - 1]
    build_max_heap(a[:-1])
    return max


heap = []
ans = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        ans.append(heap[0])
        heap = heap[1:]
        build_max_heap(heap)
    elif s[0] == "insert":
        heap.append(int(s[1]))
        build_max_heap(heap)

for x in ans:
    print(x)


### FIXED CODE ###

import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


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

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

gcd_list = []
for skip in range(N):
    ans = max(A)
    for i in range(N):
        if i == skip: continue
        buf = gcd(ans, A[i])
        if ans > buf:
            ans = buf
    gcd_list.append(ans)

gcd_list.sort()
print(gcd_list[-1])


### FIXED CODE ###

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

L = [0] * N
for i in range(N-1):
    L[i+1] = gcd(L[i],A[i])

R = [0] * N
for i in range(N-1,0,-1):
    R[i-1] = gcd(R[i],A[i])

ans = max([gcd(l,r) for l,r in zip(L,R)])
print(ans)
### BUGGY CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)