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

N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個
def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  res = [INF for _ in range(n+1)] #道が0本からn本
  for s in range(1<<n): #選ばれたものを全探索
    p = [0] #最初の大通り
    for i in range(n):
      if (s>>i)&1 == 1: #bitが立っている位置は道があるので追加
        p.append(A[i][0])
    p.sort()
    now = 0 #現在の移動距離
    pi = 0 #i個目の町の位置よりも小さい位置
    for i in range(n): #i個目の町に注目
      #m = INF
      x = A[i][0] #xoryとして選ばれた町のi番目の位置。
      while pi+1 < len(p) and p[pi+1] < x:
        pi += 1
      m = abs(x-p[pi])
      if pi+1 < len(p):
        m = min(m,abs(x-p[pi+1]))
      #for j in range(len(p)): #すべての道に対して愚直に最短距離を求める。
      #  m = min(m,abs(p[j]-A[i][0]))
      now += m*A[i][1] #最短距離×人数
    b = len(p) -1 #道を何本追加したか。1を引くのは最初の大通り。
    res[b] = min(res[b],now)
  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)

### FIXED CODE ###

N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個

def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] #i個目までカバーしてj個目まで道を置いた。
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1):
      now = INF
      for k in range(l,r):
        s = 0
        for i in range(l,r):
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n):
        dp[r][j+1] = min(dp[r][j+1], dp[l][j]+now)
      now = 0
      for i in range(l,r):
        now += abs(A[i][0])*A[i][1]
      for j in range(n+1):
        dp[r][j] = min(dp[r][j], dp[l][j]+now)

  
  res = [INF for _ in range(n+1)] #道が0本からn本
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)
### BUGGY CODE ###

n = int(input())
L = []
for i in range(n):
  L.append(int(input()))

for i in range(n):
  R = L[0:i]+L[i+1:]
  print(max(R))


### FIXED CODE ###

n = int(input())
L = []
for i in range(n):
  L.append(int(input()))

R = sorted(L)
a = R[-2]
b = R[-1]

for i in L:
  if i == b:
    print(a)
  else:
    print(b)
### BUGGY CODE ###

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

input = sys.stdin.readline
mod = 998244353


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N, K = MI()

steps = set()
for _ in range(K):
    l, r = MI()
    steps |= set(range(l, r + 1))

dp = np.zeros(N)
dp[0] = 1

for i in range(N):
    for s in steps:
        tmp = i - s
        if tmp >= 0:
            dp[i] += dp[tmp]
            dp[i] %= mod

print(int(dp[N - 1]))


### FIXED CODE ###

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

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))
### BUGGY CODE ###

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

ab = []
ma = 0
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])
    ma = max(ma,a)

dp = [float('inf')]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min([dp[max(i-a,0)]+b for a,b in ab])

print(min(dp[h:]))

### FIXED CODE ###

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

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

print(min(dp[h:]))
### BUGGY CODE ###

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

ok = 0
ng = 0
ng_tmp = [0] * n
ok_l = []

for i in range(m):
  tmp = input().split()
  p = int(tmp[0])
  s = tmp[1]
  if ok_l.count(p) == 0:
    if s == 'AC':
      ok_l.append(p)
      ok += 1
      ng += ng_tmp[p-1]
    if s == 'WA':
      ng_tmp[p-1] += 1

  
print(ok, ng)

### FIXED CODE ###

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

ok = 0
ng = 0
ng_tmp = [0] * n
flag = [True] * n

for i in range(m):
  tmp = input().split()
  p = int(tmp[0])
  s = tmp[1]
  if flag[p-1]:
    if s == 'AC':
      flag[p-1] = False
      ok += 1
      ng += ng_tmp[p-1]
    if s == 'WA':
      ng_tmp[p-1] += 1

  
print(ok, ng)
### BUGGY CODE ###

# import sys
import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

def main():
    n = int(input())
    for i in range(1,n+1):
        ans = 0
        for x in range(1,int(i**0.5+1)):
            for y in range(1,int(i**0.5+1)):
                z1 = (-(x+y)+((x+y)**2-4*(x**2+y**2+x*y-i))**0.5)/2
                if not isinstance(z1,complex):
                    if int(z1)==z1 and z1>=1:
                        ans += 1
                z2 = (-(x+y)-((x+y)**2-4*(x**2+y**2+x*y-i))**0.5)/2
                if not isinstance(z2,complex):
                    if int(z2)==z2 and z2>=1:
                        ans += 1
        print(ans)
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import sys
import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

def main():
    n = int(input())
    ans = [0 for i in range(n+1)]
    for i in range(1,int(n**0.5)+1):
        for j in range(1,int(n**0.5)+1):
            for k in range(1,int(n**0.5)+1):
                a = i**2+j**2+k**2+i*j+j*k+i*k
                if a<=n:
                    ans[a] += 1
    for i in range(1,n+1):
        print(ans[i])
    return

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

from itertools import *
n=range(49994);a=list(n)
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in iter(input,'0'):
 x=int(x)
 if x%2:print(sum(1 for c in p[2:x]if 2+c==x))
 elif x-4:print(sum(1 for a,b in combinations_with_replacement(p[1:x],2)if a+b==x))
 else:print(1)


### FIXED CODE ###

import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print(len([1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]]))
### BUGGY CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]

	S = Counter(A)
	for a in A:
		S[a] -= 1
		ans = 0
		for d in S.values():
			ans += cmb2(d)
		print(ans)
		S[a] += 1

### FIXED CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]
	# A = list(map(int, input().split()))

	c = Counter(A)
	s = 0
	for v in c.values():
		s += cmb2(v)

	for a in A:
		print(s - cmb2(c[a]) + cmb2(c[a] - 1))
### BUGGY CODE ###

N,K = map(int,input().split())
x = N

while x>K/2:
    x = abs(x-K)
print(x)

### FIXED CODE ###

N,K = map(int,input().split())
r = N%K
s = K-r
print(min([r,s]))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
flag=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if flag[n1][n2][n3]:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0
    flag[n1][n2][n3]=1
    ret=1/(1-(n-n1-n2-n3)/n)
    if n1>0:
        ret+=f(n1-1,n2,n3)*(n1/n)/(1-(n-n1-n2-n3)/n)
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*(n2/n)/(1-(n-n1-n2-n3)/n)
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*(n3/n)/(1-(n-n1-n2-n3)/n)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

n = int(input())
xy = list(list(map(int, input().split())) for _ in range(n))

#print(n, xy)
tmp = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        l = abs(xy[i][0] - xy[j][0]) + abs(xy[i][1] - xy[j][1])
        if tmp <= l:
            tmp = l
print(tmp)


### FIXED CODE ###

n = int(input())
xy = list(list(map(int, input().split())) for _ in range(n))

#print(n, xy)
x_minus_y = []
x_plus_y = []
for i in range(n):
    x_minus_y.append(xy[i][0] - xy[i][1])
    x_plus_y.append(xy[i][0] + xy[i][1])
x_max = max(x_minus_y)
x_min = min(x_minus_y)
y_max = max(x_plus_y)
y_min = min(x_plus_y)

if x_max - x_min >= y_max - y_min:
    print(x_max - x_min)
else:
    print(y_max - y_min)
### BUGGY CODE ###

from functools import reduce
from operator import mul
N = int(input())
An = input().split()
Ani = [int(i) for i in An]
AnS = reduce(mul,Ani)
if AnS <= 10**18:
    print(AnS)
else:
    print("-1")


### FIXED CODE ###

import sys
N = int(input())
An = list(map(int,input().split()))
a = 1
if 0 in An:
    print("0")
    sys.exit()
else:
    for i in range(N):
        a *= An[i]
        if a > 10**18:
            print("-1")
            sys.exit()
    if a <= 10**18:
        print(a)
        sys.exit()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
 
num_cnt = {}
sum_cnt = 0
 
for x in a:
    if x not in num_cnt:
        cnt = a.count(x)
        num_cnt[x] = cnt
        sum_cnt += cnt*(cnt-1)//2

res = []
for x in a:
    cnt = num_cnt[x]
    res.append(str( sum_cnt - (cnt-1) ))

print('\n'.join(res))

### FIXED CODE ###

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

import collections
cnt = collections.Counter(a)

sum_cnt = 0
for v in cnt.values():
    sum_cnt += v*(v-1)//2

res = []
for value in a:
    res.append(str( sum_cnt - (cnt[value]-1) ))
print('\n'.join(res))
### BUGGY CODE ###

def tentwo(N):
    ret = [0] * 60
    NN = N
    for i in range(60):
        ret[i] = NN % 2
        NN //= 2
    return ret

N = int(input())

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

B = [0] * N

for i in range(N):
    B[i] = tentwo(A[i])

ans = 0
for j in range(60):
    count = 0
    for i in range(N):
        if B[i][j] == 1:
            count += 1
    ans = (ans + (count * (N-count)) * (2 ** j)) % (10**9 + 7)

print(ans)

### FIXED CODE ###

def tentwo(N):
    ret = [0] * 60
    NN = N
    for i in range(60):
        ret[i] = NN % 2
        NN //= 2
    return ret

N = int(input())

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

B = [0] * N

for i in range(N):
    B[i] = tentwo(A[i])

ans = 0
for j in range(60):
    count = 0
    for i in range(N):
        if B[i][j] == 1:
            count += 1
    ans = (ans + (count * (N-count)) * (2 ** j)) % (10**9 + 7)

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

def main():
    S = input()
    Q = int(input())
    rvCt = 0
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            rvCt += 1
        else:
            if rvCt % 2 == 1:
                S = S[::-1]
            rvCt = 0
            if query[1] == '1':
                S = query[2] + S
            else:
                S = S + query[2]

    if rvCt % 2 == 1:
        S = S[::-1]
    
    print(S)

main()

### FIXED CODE ###

from collections import deque
def main():
    S = input()
    S = deque([c for c in S])
    Q = int(input())
    rvCt = 0

    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            rvCt += 1
        else:
            doReverse = False
            if rvCt % 2 == 1:
                doReverse = True

            if query[1] == '1':
                if doReverse:
                    S.append(query[2])
                else:
                    S.appendleft(query[2])
            else:
                if doReverse:
                    S.appendleft(query[2])
                else:
                    S.append(query[2])

    if rvCt % 2 == 1:
        S.reverse()
    
    print(''.join(S))

main()
### BUGGY CODE ###

from bisect import bisect_right as br
n,m,v,p=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=n,-1
while l-r>1:
    t=(l+r)//2
    s=a[t]+m
    w=a[:]
    k=m*(v-1)
    for i in range(n):
        if i!=t:
            if i<t:
                c=min(k,m)
                k-=c
                w[i]+=c
            else:
                if w[i]>=s:
                    break
                else:
                    c=min(k,s-w[i])
                    k-=c
                    w[i]+=c
        if k==0:
            break
    if k>0:
        for j in range(n-1,-1,-1):
            if j!=t:
                g=min(k,m-w[j]+a[j])
                w[j]+=g
                k-=g
            if k==0:
                break
    w.pop(t)
    w=sorted(w)
    if n-br(w,s)<=p:
        l=t
    else:
        r=t
print(n-l)

### FIXED CODE ###

from bisect import bisect_right as br
n,m,v,p=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=n,-1
while l-r>1:
    t=(l+r)//2
    s=a[t]+m
    w=a[:]
    k=m*(v-1)
    for i in range(n):
        if i!=t:
            if i<t:
                c=min(k,m)
                k-=c
                w[i]+=c
            else:
                if w[i]>=s:
                    break
                else:
                    c=min(k,s-w[i])
                    k-=c
                    w[i]+=c
        if k==0:
            break
    if k>0:
        for j in range(n-1,-1,-1):
            if j!=t:
                g=min(k,m-w[j]+a[j])
                w[j]+=g
                k-=g
            if k==0:
                break
    w.pop(t)
    w=sorted(w)
    if n-br(w,s)<=p:
        l=t
    else:
        r=t
print(n-l)
### BUGGY CODE ###

H, W = map(int,input().split())
s = [list(input()) for i in range(H)]
num_of_point = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            num_of_point += 1
 
counter = 0
position = [[0,0]]
while True:
    counter += 1
    new_position =[]
    for i,j in position:
        for i_,j_ in [[-1,0],[1,0],[0,1],[0,-1]]:
            i_new = i+i_
            j_new = j+j_
            if i_new >=0 and i_new <= H-1 and j_new >= 0 and j_new <= W-1:
                if s[i_new][j_new] == '.':
                    new_position.append([i_new,j_new])
                    s[i_new][j_new] = counter
    if [H-1,W-1] in new_position:
        break
    position = new_position
 
print(num_of_point-counter-1)

### FIXED CODE ###

H, W = map(int,input().split())
s = [list(input()) for i in range(H)]
num_of_point = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            num_of_point += 1
 
counter = 0
position = [[0,0]]
while True:
    counter += 1
    new_position =[]
    for i,j in position:
        for i_,j_ in [[-1,0],[1,0],[0,1],[0,-1]]:
            i_new = i+i_
            j_new = j+j_
            if i_new >=0 and i_new <= H-1 and j_new >= 0 and j_new <= W-1:
                if s[i_new][j_new] == '.':
                    new_position.append([i_new,j_new])
                    s[i_new][j_new] = counter
    if [H-1,W-1] in new_position:
        print(num_of_point-counter-1)
        break
    if counter >= H*W:
      	print(-1)
      	break
    position = new_position
### BUGGY CODE ###

h, w = map(int, input().split())
b = 0
l = [0]*h
for k in range(h):
  a = str(input())
  b += a.count('#')
  l[k] = a
#l = [str(input()) for _ in range(h)]

from collections import deque

queue = deque()
visit = [[-1]*w for _ in range(h)]
queue.append([0, 0])
visit[0][0] = 1

while queue:
  y, x = queue.popleft()
  if y == h-1 and x == w-1:
    print(h*w-visit[y][x]-b)
    exit()
  for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
    new_y, new_x = y+i, x+j
    if (new_x<0) or (new_x>=w) or (new_y<0) or (new_y>=h) or l[new_y][new_x]=='#':
      continue
    else:
      visit[new_y][new_x] = visit[y][x]+1
      queue.append([new_y,new_x])
else:
  print('-1')
      

### FIXED CODE ###

h, w = map(int, input().split())
b = 0
l = [0]*h
for k in range(h):
  a = str(input())
  for k_ in range(w):
    if a[k_] == '#':
      b += 1
  l[k] = a
#l = [str(input()) for _ in range(h)]
 
from collections import deque
 
queue = deque()
visit = [[-1]*w for _ in range(h)]
queue.append([0, 0])
visit[0][0] = 1
 
while queue:
  y, x = queue.popleft()
  if y == h-1 and x == w-1:
    print(h*w-visit[y][x]-b)
    exit()
  for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
    new_y, new_x = y+i, x+j
    if (new_x>=0) and (new_x<w) and (new_y>=0) and (new_y<h) and l[new_y][new_x]=='.' and visit[new_y][new_x] == -1:
      visit[new_y][new_x] = visit[y][x]+1
      queue.append([new_y,new_x])
    else:
      continue
else:
  print('-1')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        D = [d[i]%M for i in range(k)]
        SUMD = sum(D)
        last = 0
        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = D.count(0)*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + sum(D[:(N-1)%k])
            equal_count = D.count(0)*((N-1)//k)+D[:(N-1)%k].count(0)
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    k = int(next(tokens))  # type: int
    q = int(next(tokens))  # type: int
    d = [int(next(tokens)) for _ in range(k - 1 - 0 + 1)]  # type: "List[int]"
    n = [int()] * (q)  # type: "List[int]"
    x = [int()] * (q)  # type: "List[int]"
    m = [int()] * (q)  # type: "List[int]"
    for i in range(q):
        n[i] = int(next(tokens))
        x[i] = int(next(tokens))
        m[i] = int(next(tokens))
    solve(k, q, d, n, x, m)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        count = [0]*k
        D = [0]*k
        c = 0
        for i in range(k):
            D[i] = d[i]%M
            if D[i] == 0:
                c += 1
            count[i] = c
        accum = list(accumulate(D))
        SUMD = accum[-1]
        COUNTD = count[-1]

        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + accum[(N-1)%k-1]
            equal_count = COUNTD*((N-1)//k)+count[(N-1)%k-1]
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    k = int(next(tokens))  # type: int
    q = int(next(tokens))  # type: int
    d = [int(next(tokens)) for _ in range(k - 1 - 0 + 1)]  # type: "List[int]"
    n = [int()] * (q)  # type: "List[int]"
    x = [int()] * (q)  # type: "List[int]"
    m = [int()] * (q)  # type: "List[int]"
    for i in range(q):
        n[i] = int(next(tokens))
        x[i] = int(next(tokens))
        m[i] = int(next(tokens))
    solve(k, q, d, n, x, m)

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

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

print(ans)


### FIXED CODE ###

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

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

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

for l_index in range(N):
    my_sum = 0
    for r_index in range(l_index, N):
        if my_sum + A[r_index] == my_sum ^ A[r_index]:
            my_sum += A[r_index]
            count += 1
        else:
            break

print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
my_sum = 0
count = 0
r, l = 0, 0

while r < N:
    boo = my_sum + A[r]
    foo = my_sum ^ A[r]
    if boo == foo:
        my_sum += A[r]
        r += 1
        count += (r - l)
    else:
        my_sum -= A[l]
        l += 1

print(count)