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

n,m,l=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  if c>l:continue
  a-=1;b-=1
  edge[a].append([b,c])
  edge[b].append([a,c])
from heapq import heappop,heappush
inf=10**10
cost=[[[inf,inf]for _ in range(n)]for _ in range(n)]
for i in range(n):
  cost[i][i]=[0,0]
  h=[[0,i]]
  while h:
    c,v=heappop(h)
    c,co=c//(10**9+7),c%(10**9+7)
    if cost[i][v][0]<c or (cost[i][v][0]==c and cost[i][v][1]<co):continue
    for u,t in edge[v]:
      if co+t>l:
        c2=c+1
        co2=t
      else:
        c2=c
        co2=co+t
      if cost[i][u][0]>c2 or (cost[i][u][0]==c2 and cost[i][u][1]>co2):
        cost[i][u]=[c2,co2]
        heappush(h,[c2*(10**9+7)+co2,u])
ans=[[j[0]for j in i]for i in cost]
q=int(input())
ab=[list(map(int,input().split()))for _ in range(q)]
for a,b in ab:
  if ans[a-1][b-1]==10**10:print(-1)
  else:print(ans[a-1][b-1])

### FIXED CODE ###

def warshall_floyd(edge):
  e=edge
  for k in range(len(e)):
    for i in range(len(e)):
      for j in range(len(e)):e[i][j]=min(e[i][j],e[i][k]+e[k][j])
  return e
n,m,l=map(int,input().split())
edge=[n*[10**10]for _ in range(n)]
for i in range(n):edge[i][i]=0
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1;b-=1
  edge[a][b]=edge[b][a]=c
edge=warshall_floyd(edge)
edgee=[n*[10**10]for _ in range(n)]
for i in range(n):
  edgee[i][i]=0
  for j in range(n):
    if edge[i][j]<=l:edgee[i][j]=1
edgee=warshall_floyd(edgee)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  s-=1;t-=1
  ans=edgee[s][t]
  if ans==10**10:print(-1)
  else:print(ans-1)
### BUGGY CODE ###

n = int(input())

c = [0] * n
f = [0] * n
s = [0] * n

for i in range(n - 1):
    c[i], s[i], f[i] = map(int, input().split())

lapse = [0] * n

for i in range(n):
    for j in range(i + 1, n):

        t = 0
        while s[j - 1] + t * f[j - 1] < lapse[i]:
            t += 1

        lapse[i] = s[j - 1] + t * f[j - 1] + c[j - 1]

    print(lapse[i])


### FIXED CODE ###

n = int(input())

c = [0] * n
f = [0] * n
s = [0] * n

for i in range(n - 1):
    c[i], s[i], f[i] = map(int, input().split())

lapse = [0] * n

for i in range(n):
    for j in range(i + 1, n):

        t = 0
        while s[j - 1] + t * f[j - 1] < lapse[i]:
            t += 1

        lapse[i] = s[j - 1] + t * f[j - 1] + c[j - 1]

    print(lapse[i])
### BUGGY CODE ###

from collections import defaultdict
from itertools import product

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

Count = [sum(c == '1' for c in s) for s in S]
total = sum(Count)

while 0 in Count:
  i = Count.index(0)
  del S[i]
  del Count[i]
H = len(S)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    DS = []
    for s, x in zip(S, [True] + list(X)):
      if x:
        DS.append([])
      DS[-1].append(s)
    DC = [[sum(s[j] == '1' for s in ds) for ds in DS] for j in range(W)]
    D = [0] * len(DS)
    for dc in DC:
      if any(d + c > K for d, c in zip(D, dc)):
        ans += 1
        if ans > answer:
          break
        D = [0] * len(DS)
      for k, c in enumerate(dc):
        D[k] += c
    answer = min(answer, ans)

print(answer)

### FIXED CODE ###

from collections import defaultdict
from itertools import product

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

i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)

C = [[int(s[i]) for s in S] for i in range(W)]

total = sum(sum(c) for c in C)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)
### BUGGY CODE ###

s=input()
c=0
while "ABC" in s:
    s=s.replace("ABC","BCA",1)
    c+=1
print(c)

### FIXED CODE ###

s=input()
i=1
new=[s[0]]
while i<len(s):
    if s[i]=="C" and s[i-1] == "B":
        new.pop()
        new.append("K")
    else:
        new.append(s[i])
    i+=1

cnt=0
ans=0
for i in range(len(new)-1,-1,-1):
    if new[i]=="A" and cnt > 0:
        ans+=cnt
    elif new[i]=="K":
        cnt+=1
    else:
        cnt=0
    
print(ans)
### BUGGY CODE ###

A,B,C,D = list(map(int,input().split()))
while A > 0 or B > 0:
  A -= D
  C -= B
if A <= 0:
  print('No')
elif B <= 0:
        print('Yes')
  
  

### FIXED CODE ###

A,B,C,D = list(map(int,input().split()))
a=0
c=0
while A > 0:
  A -= D
  a += 1#何回でやられたか
while C > 0:
  C -= B
  c += 1#何回で倒したか
if a < c:
  print('No')
elif a >= c:
  print('Yes')
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0

for i in range(min(li), max(li)+1):
  x = 0
  for j in li:
    if i-1 <= j <= i+1:
      x += 1
  if x > ans:
    ans = x
    
print(ans)

### FIXED CODE ###

import collections

n = int(input())
li = list(map(int,input().split()))
ans = []

for i in li:
    ans.append(i-1)
    ans.append(i)
    ans.append(i+1)

c = collections.Counter(ans)

print(c.most_common()[0][1])
### BUGGY CODE ###

import itertools

N, M = map(int, input().split())
np = len(list(itertools.permutations(list(range(N))))) % (10**9+7)
mp = len(list(itertools.permutations(list(range(M))))) % (10**9+7)
if N == M:
    ans = np*mp % (10**9+7)*2
elif abs(N - M) == 1:
    ans = np * mp % (10 ** 9 + 7)
else:
    ans = 0
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
mod = 10**9+7


def for_factorial(n):
    mod = 10**9+7
    val = 1
    for i in range(2, n + 1):
        val = (val*i) % mod
    return val


f = for_factorial(N)*for_factorial(M) % mod
if N == M:
    ans = f*2 % mod
elif abs(N - M) == 1:
    ans = f % mod
else:
    ans = 0

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

n = int(input())
c = sorted([int(_) for _ in input().split()])
mod = 10**9 + 7
ans = 0
for i in range(n):
    ans += c[i] * 2**(2 * n - 2) * (n - i + 1)
    ans %= mod
print(ans)


### FIXED CODE ###

n = int(input())
c = sorted([int(_) for _ in input().split()])
mod = 10**9 + 7
ans = 0
for i in range(n):
    ans += c[i] * pow(2, 2 * n - 2, mod) * (n - i + 1)
    ans %= mod
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
a = [int(i) for i in input().split()]
b=a.copy()
s0p = a[0]
s0n = b[0]
countp = 0
countn = 0

if a.count(0)==n:
  print(2*n+1)
  exit()

if s0p<=0:
  while s0p<=0:
    s0p+=1
    countp+=1

if s0n>=0:
  while s0n>=0:
    s0n-=1
    countn+=1

for i in range(1,n):
  s1 = s0p+a[i]
  if s0p*s1>=0:
    if s1>0:
      a[i]-=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1<0:
      a[i]+=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1==0:
      if s0p>0:
        a[i]-=1
        countp+=1
      elif s0p<0:
        a[i]+=1
        countp+=1
  s0p += a[i]

for i in range(1,n):
  s1 = s0n+b[i]
  if s0n*s1>=0:
    if s1>0:
      b[i]-=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1<0:
      b[i]+=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1==0:
      if s0n>0:
        b[i]-=1
        countn+=1
      elif s0n<0:
        b[i]+=1
        countn+=1
  s0n += b[i]

print(countp if countp<=countn else(countn))





### FIXED CODE ###

import copy
n = int(input())
a = [int(i) for i in input().split()]
b=a.copy()
s0p = a[0]
s0n = b[0]
countp = 0
countn = 0

if a.count(0)==n:
  print(2*n-1)
  exit()

if s0p<=0:
  s0p+=(abs(a[0])+1)
  countp+=(abs(a[0])+1)
  
if s0n>=0:
  s0n-=(abs(b[0])+1)
  countn+=(abs(b[0])+1)

for i in range(1,n):
  s1 = s0p+a[i]
  if s0p*s1>=0:
    if s1>0:
      a[i]-=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1<0:
      a[i]+=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1==0:
      if s0p>0:
        a[i]-=1
        countp+=1
      elif s0p<0:
        a[i]+=1
        countp+=1
  s0p += a[i]

for i in range(1,n):
  s1 = s0n+b[i]
  if s0n*s1>=0:
    if s1>0:
      b[i]-=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1<0:
      b[i]+=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1==0:
      if s0n>0:
        b[i]-=1
        countn+=1
      elif s0n<0:
        b[i]+=1
        countn+=1
  s0n += b[i]
  
print(countp if countp<=countn else(countn))
### BUGGY CODE ###

n = int(input())
new_s = input()
# new_s = ""
# for i in range(len(s)):
#    if i<3:
#        new_s+=s[i]
#     else:
#         if s[i-1] == s[i] and s[i-2] == s[i]:
#             pass
#         else:
#             new_s+=s[i]
pas = -1
ans = 0
for i in range(1000):
    ott = 0
    pas = int(pas)+1
    if pas < 10:
        pas = "00"+str(pas)
    elif pas < 100:
        pas = "0"+str(pas)
    pas = str(pas)
    idx = -1
    while idx < len(new_s)-1:
        idx += 1
        if ott == 0:
            if pas[0] == new_s[idx]:
                ott += 1
        elif ott == 1:
            if pas[1] == new_s[idx]:
                ott += 1
        elif ott == 2:
            if pas[2] == new_s[idx]:
                ott += 1
                ans += 1
        if ott == 3:
            break
print(ans)



### FIXED CODE ###

n = int(input())
new_s = input()
pas = -1

ans = 0
lens = len(new_s)
for i in range(1000):
    ott = 0
    pas = int(pas)+1
    if pas < 10:
        pas = "00"+str(pas)
    elif pas < 100:
        pas = "0"+str(pas)
    pas = str(pas)
    idx = -1
    while idx < lens-1:
        idx += 1
        if ott == 0:
            if pas[0] == new_s[idx]:
                ott += 1
        elif ott == 1:
            if pas[1] == new_s[idx]:
                ott += 1
        elif ott == 2:
            if pas[2] == new_s[idx]:
                ott += 1
                ans += 1
        if ott == 3:
            break
print(ans)
### BUGGY CODE ###

from operator import or_
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class SparseTable:
    def __init__(self, N, arr, op):
        self.N = N
        self.depth = N.bit_length()
        self.op = op
        self.arr = tuple(arr)
        self._build()

    def __call__(self, s, t):
        """
        [s, t)区間（0-indexed）での値を返す
        """
        i = (t - s).bit_length() - 1
        L = self.table[i][s]
        R = self.table[i][t - (1 << i)]
        return self.op(L, R)

    def _build(self):
        self.table = []
        self.table.append(self.arr)
        N = self.N
        for i in range(self.depth - 1):
            shift = 1 << i
            N -= shift
            t = tuple(self.op(self.table[-1][j], self.table[-1][j+shift])
                      for j in range(N))
            self.table.append(t)


N, Q = map(int, input().split())
C = [1 << (i-1) for i in map(int, input().split())] + [0]
sp = SparseTable(N+1, C, or_)
for _ in range(Q):
    s, t = map(int, input().split())
    b = bin(sp(s-1, t)).count("1")
    print(b)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

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

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


N, Q = map(int, input().split())
U = 5 * 10 ** 5 + 10

C = tuple(map(int, input().split()))
LR = [list() for _ in range(U)]
for i in range(Q):
    l, r = map(int, input().split())
    LR[r].append((l, i))

ans = [-1] * Q
bit = BinaryIndexTree(N + 5)
seen = defaultdict(int)
for i, c in enumerate(C, 1):
    if seen[c]:
        bit.add(seen[c], -1)
    bit.add(i, 1)
    seen[c] = i
    if LR[i]:
        R = bit.sum(i)
        for L, x in LR[i]:
            ans[x] = R - bit.sum(L - 1)


print(*ans, sep="\n")
### BUGGY CODE ###

import sys

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

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = list(map(int, input().split()))
    ans = 0
    for k in range(56):
        t = 1 << k
        t2 = t << 1
        am = list(map(lambda x: x % t2, aa))
        bm = list(map(lambda x: x % t2, bb))
        am.sort(reverse=True)
        bm.sort()
        #print(am)
        #print(bm)
        cnt = n % 2
        for tk in range(t, t * 4, t):
            j = 0
            for a in am:
                while j < n and a + bm[j] < tk:
                    j += 1
                cnt += j
        if cnt % 2:
            ans += t
    print(ans)

main()


### FIXED CODE ###

import sys
import numpy as np

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

def main():
    n = int(input())
    aa = np.array(list(map(int, input().split())), dtype="i8")
    bb = np.array(list(map(int, input().split())), dtype="i8")
    ans = 0
    for k in range(29):
        t = 1 << k
        t2 = t << 1
        am = aa % t2
        bm = bb % t2
        # am.sort(reverse=True)
        bm.sort()
        # print(am)
        # print(bm)
        cnt = n % 2
        for tk in range(t, t * 4, t):
            cnt += np.sum(np.searchsorted(bm, tk - am))
        if cnt % 2:
            ans += t
    print(ans)

main()
### BUGGY CODE ###

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    s = [0]*(N+1)
    for i in range(N):
        s[i+1] = s[i] + A[i]
    mod = 998244353
    ans = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if s[j] - s[i] == S:
    #             left = i+1
    #             right = N - j + 1
    #             ans += left*right % mod
    #             print(left, right, i, j)
    # print(ans % mod)

    dp = [[0, dict()] for i in range(S+1)]
    dp[0][0] = 1

    for j, a in enumerate(A):
        for i in range(S-1, -1, -1):
            if dp[i][0] > 0 and i+a <= S:
                dp[i+a][0] += dp[i][0]
                if i == 0:
                    dp[i+a][1][((j, j))] = 1
                else:
                    for l, r in dp[i][1]:

                        ll = min(l, j)
                        rr = max(r, j)
                        if (ll, rr) in dp[i+a][1]:
                            dp[i+a][1][(ll, rr)] += dp[i][1][(l, r)]
                        else:
                            dp[i+a][1][(ll, rr)] = dp[i][1][(l, r)] % mod

    for l, r in dp[S][1]:
        ans += (l+1) * (N - r) * dp[S][1][l, r]
        ans %= mod
    print(ans)


main()


### FIXED CODE ###

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] = i+1
        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()
### BUGGY CODE ###

from itertools import product
N = int(input())

list_N = list(range(1, int((N + 1)**0.5)))

list_xyz = list(product(list_N, repeat=3))

ans_list = [x**2 + y**2 + z ** 2 + x*y + y*z + x * z for x, y ,z in list_xyz]
for n in range(1, N+1):
    print(ans_list.count(n))

### FIXED CODE ###

from itertools import product
import heapq

N = int(input())

list_N = list(range(1, int((N + 1)**0.5)))

list_xyz = list(product(list_N, repeat=3))

ans_list = [x**2 + y**2 + z ** 2 + x*y + y*z + x * z for x, y ,z in list_xyz]
heapq.heapify(ans_list)
for n in range(1, N+1):
    ans = 0
    while True:
        if len(ans_list) < 1:
            break
        tmp = heapq.heappop(ans_list)
        if tmp == n:
            ans += 1
        elif tmp > n:
            heapq.heappush(ans_list, tmp)
            break
        
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
score = -INF
for st in range(n):
    tot = 0 # cost of one lap
    costs = []
    nx = st
    while True:
        nx = P[nx]
        costs.append(C[nx])
        tot += C[nx]
        if nx == st: break

    lap_c = -INF # lap costs
    r = k
    if tot >= 0:
        nl, r = divmod(k, len(costs)) # number of loops
        lap_c = max(lap_c, tot * nl)
        # print('nl {}, k {}'.format(nl, k))

    sum_c = 0
    max_c = -INF
    for c in costs[:min(r, len(costs))]:
        sum_c += c
        max_c = max(max_c, sum_c)

    score = max(score, lap_c, max_c, lap_c + max_c)

    # print(st, costs, tot)
    # print(lap_c, max_c, lap_c+max_c, '=', score)

print(score)

# print('===')
# print(n,k)
# print(P)
# print(C,end='\n\n')


### FIXED CODE ###

n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 # lap count
    lap_sc = 0 # lap score
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break

        sum_sc += C[nx]
        score = sum_sc + max(0, lap_sc) * ((k - kc) // lc)
        max_score = max(max_score, score)

        nx = P[nx]
        if nx == st: break

print(max_score)

# print('===')
# print(n,k)
# print(P)
# print(C,end='\n\n')
### BUGGY CODE ###

lists=[]
n=int(input())
nums=0
while nums<=n+1:
    
    
    if nums<6:
        lists.append(nums)
        nums=+1
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7726 or nums==46656:
        lists.append(1)
        nums+=1
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        nums+=1
    else:
        order6=0
        order9=0
        for k in range(6):
            if 6**(k+1)< nums <6**(k+2):
                order6=k+1
                # nums は6のκ＋1乗までならば考慮に入れても良い
                break
                
            else:
                continue
                
        for j in range(5):
            if 9**(j+1) <nums< 9**(j+2):
                order9=j+1
                #numsは9のｊ＋1乗までならば考慮に入れてもいい
                break
            else:
                continue
                
        add=min(min(lists[n-6**(k)] for k in range(0,order6+1)),min(lists[n-9**(j)] for j in range(0,order9+1)))
        lists.append(add)
        nums+=1
print(lists)

### FIXED CODE ###

lists=[]
emptylists=[]
numbers=int(input())

for nums in range(numbers+3):
    
    if nums<6:
        lists.append(int(nums))
         
    elif nums==6 or nums==36 or nums==216 or nums==1296 or nums==7776 or nums==46656:
        lists.append(1)
        
    elif nums==9 or nums==81 or nums==729 or nums==6561 or nums==59049:
        lists.append(1)
        
    else:
        power6=0
        power9=0
        for k in range(7):
            if 6**(k)< nums <6**(k+1):
                power6=k
                break   
                
        for j in range(6):
            if 9**(j) <nums< 9**(j+1):
                power9=j
                break
        add=min(min(lists[nums-6**(k)]+1 for k in range(0,power6+1)),min(lists[nums-9**(j)]+1 for j in range(0,power9+1)))
        lists.append(add)
print(lists[numbers])
### BUGGY CODE ###

import copy
N,K = map(int,input().split())
A = [int(a) for a in input().split()]

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

max_num = max(score)
i = 0
while(True):
    if(2**(i+1)>max_num):
        break
    else:
        i+=1

ans = 0
for j in range(i,-1,-1):
    count = 0
    score_a = []
    score_b = []
    for k in range(len(score)):
        if score[k] >= 2**j:
            count += 1
            score[k] -= 2**j
            score_a.append(score[k])
        score_b.append(score[k])
    if count >= K:
        ans += 2**j
        score = copy.deepcopy(score_a)
    else:
        score = copy.deepcopy(score_b)

print(ans)


### FIXED CODE ###

import copy
N,K = map(int,input().split())
A = map(int,input().split())

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

ans = 0
for i in range(40,-1,-1):
    count = 0
    score_a = []
    for j in score:
        if (j & (1<<i)):
            count += 1
            score_a.append(j)
    if count >= K:
        ans += (1<<i)
        score = copy.deepcopy(score_a)

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

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    s = sum(a)
    cand = [s]
    for i in range(2, int(s ** 0.5) + 1):
        if s % i == 0:
            cand.append(i)
            cand.append(s // i)
    cand.sort(reverse=True)

    for c in cand:
        arr = [[a[i] % c, a[i] % c - c] for i in range(n)]
        for i in range(1 << n):
            tmp = [0] * 2
            for j in range(n):
                if i & (1 << j):
                    tmp[0] += arr[j][0]
                else:
                    tmp[1] += arr[j][1]
            if sum(tmp) == 0 and tmp[0] <= k:
                print(c)
                exit()
    print(1)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    s = sum(a)
    cand = [s]
    for i in range(2, int(s ** 0.5) + 1):
        if s % i == 0:
            cand.append(i)
            cand.append(s // i)
    cand.sort(reverse=True)

    for c in cand:
        arr = [a[i] % c for i in range(n)]
        arr.sort()
        sum_r = [0] * n
        sum_r[0] = arr[0]
        for i in range(1, n):
            sum_r[i] = sum_r[i - 1] + arr[i]
        for i in range(n - 1):
            if sum_r[i] <= k:
                sum_l = c * (n - i - 1) - sum_r[-1] + sum_r[i]
                if sum_r[i] == sum_l:
                    print(c)
                    exit()

    print(1)


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

def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=tuple(map(int,input().split()))
  mod=pow(10,9)+7
  x=[0]*61
  for i in a:
    for j in range(60):
      if (i >> j) & 1:
        x[j+1]+=1
  ans=0
  for i in range(1,61):
    ans+=pow(2,i-1,mod)*(x[i]%mod)*((n-x[i])%mod)%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  import numpy as np
  n=int(input()) 
  a=np.array(list(map(int,input().split())))
  mod=pow(10,9)+7
  ans=0
  
  for i in range(60):
    x=np.count_nonzero(a & 1)
    ans+=pow(2,i,mod)*x*(n-x)
    ans=ans%mod
    a=a>>1
  print(ans)
if __name__=='__main__':
  main()