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

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

R,C,K = LI()
r,c,v = LIR(K,3)

a = [[0]*C for _ in range(R)]
for i in range(K):
    a[r[i]-1][c[i]-1] = v[i]

dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
if a[0][0]:
    dp[0][0][1] = a[0][0]

for i in range(R):
    for j in range(C):
        upper_max = max(dp[i-1][j]) if i >= 1 else 0
        for k in range(4):
            if j >= 1:
                dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
            if k == 0 and i >= 1:
                dp[i][j][k] = max(dp[i][j][k],upper_max)
            if a[i][j] != 0:
                if k == 1 and i >= 1:
                    dp[i][j][k] = max(dp[i][j][k],upper_max+a[i][j])
                if k >= 1 and j >= 1:
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+a[i][j])

print(max(dp[R-1][C-1]))

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

R,C,K = LI()
r,c,v = LIR(K,3)

def index(i,j,k):
    return k*C*R + i*C + j

a = [[0]*C for _ in range(R)]
for i in range(K):
    a[r[i]-1][c[i]-1] = v[i]

dp = [0]*(4*C*R)
dp[index(0,0,1)] = a[0][0]

for i in range(R):
    for j in range(C):
        if i == j == 0:
            continue
        upper_max = 0
        if i >= 1:
            for k in range(4):
                upper_max = max(upper_max,dp[index(i-1,j,k)])
        for k in range(4):
            val1 = 0
            val2 = 0
            val3 = 0
            val4 = 0
            if j >= 1:
                val1 = dp[index(i,j-1,k)]
            if k == 0 and i >= 1:
                val2 = upper_max
            if a[i][j] != 0:
                if k == 1 and i >= 1:
                    val3 = upper_max + a[i][j]
                if k >= 1 and j >= 1:
                    val4 = dp[index(i,j-1,k-1)] + a[i][j]
            dp[index(i,j,k)] = max(val1,val2,val3,val4)

ans = 0
for k in range(4):
    ans = max(ans,dp[index(R-1,C-1,k)])

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

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

isum = 0
for i in range(n):
  if i+k > n:
    break
  temp = p[i:i+k]
  if sum(temp) > isum:
    isum = sum(temp)

print(isum)


### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ret = 0
for i in range(len(P)):
  if min(P[:i+1]) == P[i]:
    ret += 1
print(ret)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
ret = 0
minval = 0
for i in range(len(P)):
  if i == 0:
    minval = P[i]
  if minval >= P[i]:
    ret += 1
    minval = P[i]
print(ret)
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
N=int(input())
risuto=list(map(int,input().split()))
ans=prod(risuto)

if ans<=(10**18):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import math
N=int(input())
risuto=list(map(int,input().split()))
ans=1
kari=0
if 0 in risuto:
    print(0)
else:
    for j in range(N):
        kari+=math.log10(risuto[j])

    if kari<18:
        for i in range(N):
            ans*=risuto[i]
        print(ans) 
    elif kari==18:
        for i in range(N):
            ans*=risuto[i]
        if ans>10**18:
            print(-1)
        else:
            print(ans)
    else:
        print(-1)
### BUGGY CODE ###

from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
root_yen = defaultdict(set)
root_snu = defaultdict(set)


#cost[a][b] = a -> b のコスト
cost_yen = [[0 for i in range(N+1)] for j in range(N+1)]
cost_snu = [[0 for i in range(N+1)] for j in range(N+1)]


#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


#q = 次に探索する(確定する)もの q[0]=[w,n]
q_yen = [[0,s]]
q_snu = [[0,t]]
heapq.heapify(q_yen)
heapq.heapify(q_snu)


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #
	
	root_yen[u].add(v)
	root_yen[v].add(u)
	
	root_snu[u].add(v)
	root_snu[v].add(u)
	
	cost_yen[u][v] = a
	cost_yen[v][u] = a
	cost_snu[u][v] = b
	cost_snu[v][u] = b
	
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global cost_yen
	global weight_yen
	global q_yen
		
	for i in list(root_yen[n]):
		w = w_0 + cost_yen[n][i]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q_yen, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global cost_snu
	global weight_snu
	global q_snu
		
	for i in list(root_snu[n]):
		w = w_0 + cost_snu[n][i]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q_snu, [w,i])
			weight_snu[i] = w			
			
while q_yen:
	w,n = heapq.heappop(q_yen)
	search_yen(n,w)
	
while q_snu:
	w,n = heapq.heappop(q_snu)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])

### FIXED CODE ###

from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
roots = defaultdict(set)

#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #

	roots[u].add((v,a,b))
	roots[v].add((u,a,b))
		
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global weight_yen
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[1]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global weight_snu
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[2]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_snu[i] = w

#q = 次に探索する(確定する)もの q[0]=[w,n]
q = [[0,s]]
heapq.heapify(q)
			
while q:
	w,n = heapq.heappop(q)
	search_yen(n,w)
	
heapq.heappush(q, [0,t])
	
while q:
	w,n = heapq.heappop(q)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])
### BUGGY CODE ###

S = input()
M = 10**9+7

case = [1] + [0] * 12
temp = [0] * 13
unit = 1
before = 0
for i in reversed(range(len(S))):
    if(S[i] == '?'):
        for k in range(13):
            for j in range(10):
                before = (k - unit * j) % 13
                temp[k] += case[before]
            temp[k] %= M
    else:
        for k in range(13):
            before = (k - unit * int(S[i])) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13
    temp = [0] * 13

print(case[5])


### FIXED CODE ###

S = input()
M = 10**9+7

case = [1] + [0] * 12
temp = [0] * 13
unit = 1
before = 0
for i in reversed(range(len(S))):
    if(S[i] == '?'):
        for k in range(13):
            for j in range(10):
                before = (k - unit * j) % 13
                temp[k] += case[before]
            temp[k] %= M
    else:
        for k in range(13):
            before = (k - unit * int(S[i])) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13
    temp = [0] * 13

print(case[5])
### BUGGY CODE ###

h,w,d = map(int, input().split())

a = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    a[i] = list(map(int, input().split()))

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

point = [0] * (h*w)
for i in range(1,h*w-d+1):
    point[i] = abs(masu[i][0] - masu[i+d][0]) + abs(masu[i][1] - masu[i+d][1])


q = int(input())
ans = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        ans[i] = 0
    else:
        ans[i] = sum(point[l:r:d])
 
for i in range(q):
    print(ans[i])


### FIXED CODE ###

h,w,d = map(int, input().split())

a = [[0 for _ in range(w)] for _ in range(h)]
masu = {}
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j in range(w):
        masu[a[i][j]] = (i,j)

point = [0] * (h*w+10)
for i in range(d+1,h*w+1):
    point[i] = point[i-d] + abs(masu[i][0] - masu[i-d][0]) + abs(masu[i][1] - masu[i-d][1])


q = int(input())
ans = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        ans[i] = 0
    else:
        ans[i] = point[r] - point[l]
 
for i in range(q):
    print(ans[i])
### BUGGY CODE ###

def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(r-l-c):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    break
        c += 1

    print(mi)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(min(r-l-c, 2019)):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    print(0)
                    return 
        c += 1

    print(mi)


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

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

    res = 0
    balls = {}

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1

    while len(balls.keys()) > k:
        
        minValue = 200000
        maxValue = 0

        for key, value in balls.items():
            if value < minValue and value > 0:
                minValue = value
                minKey = key
        
            if value >= maxValue:
                maxValue = value
                maxKey = key
        
        balls[maxKey] += minValue
        balls.pop(minKey)

        res += minValue
    
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    res = 0
    balls = {}
    bucket = [[] for _ in range(n+1)]

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    for key, value in balls.items():
        bucket[value].append(key)

    for i in range(len(bucket)):
        for j in range(len(bucket[i])):
            if bucket[i] != [] and len(balls) > k:
                res += i
                balls.pop(bucket[i][j])

    print(res)

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

# BinaryIndexedTree
# O(logN)で累積和取得と値の更新
# add(i,x)...i番目にxを加算
# sum(i,j)...[i,j)の累積和を取得
# sum_sub(i)...[0:i]の累積和を取得
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a
mod=998244353
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l,r=map(int,input().split())
  lr.append((l,r))
bit=BinaryIndexedTree(2*n+7)
bit.add(0,1)
bit.add(1,-1)
for i in range(n-1):
  x=bit.sum_sub(i)%mod
  for l,r in lr:
    bit.add(i+l,x)
    bit.add(i+r+1,-x)
print(bit.sum_sub(n-1)%mod)

### FIXED CODE ###

import sys
input=lambda:sys.stdin.readline().rstrip()

# BinaryIndexedTree
# O(logN)で累積和取得と値の更新
# add(i,x)...i番目にxを加算
# sum(i,j)...[i,j)の累積和を取得
# sum_sub(i)...[0:i]の累積和を取得
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a
mod=998244353
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l,r=map(int,input().split())
  lr.append((l,r))
bit=BinaryIndexedTree(2*n+7)
bit.add(0,1)
bit.add(1,-1)
for i in range(n-1):
  x=bit.sum_sub(i)%mod
  for l,r in lr:
    bit.add(i+l,x)
    bit.add(i+r+1,-x)
print(bit.sum_sub(n-1)%mod)
### BUGGY CODE ###

# E
import fractions
N = int(input()) 
A = list(map(int, input().split()))

value = A[0]
for i in range(1, N):
    value = value * A[i] // fractions.gcd(value, A[i])

mod = 10**9+7
ans = 0
for i in A:
    ans += value * pow(i, mod-2,mod)
    ans = ans % mod

print(ans)


### FIXED CODE ###

# E
from fractions import gcd

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

value = 1
for a in A:
    value = value * a // gcd(value, a)

mod = 10**9+7

ans = 0
for i in A:
    ans += value // i

print(ans%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
p=0
for i in range(n):
    try:
        p+=a[p:].index(i+1)
    except:
        ans=i
        break
else:
    ans=n
print(n-ans if ans>0 else -1)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=ans=0
for i in range(1,n+1):
    for j in range(p,n):
        if i==a[j]:
            p=j
            break
    else:
        ans=i-1
        break
else:
    ans=n
print(n-ans if ans>0 else -1)
### BUGGY CODE ###

n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
calc_tree = []

for i in range(n):
  tmp = [i+1]
  for j in range(n-1):
    if tree[j][0] in tmp:
      tmp.append(tree[j][1])
  calc_tree.append(tmp)
#print(calc_tree)
ans = [0] * n
  
for i in range(q):
  order = px[i][0] -1
  for j in calc_tree[order]:
    ans[j-1] += px[i][1]
    
for i in ans:
  print(i,end=' ')

### FIXED CODE ###

from collections import deque
import sys
def input():
   return sys.stdin.readline()[:-1]
  
n,q = map(int, input().split())
tree = [[int(i) for i in input().split()] for i in range(n-1)] 
px = [[int(i) for i in input().split()] for i in range(q)] 
A = [set() for i in range(n)]
B = [set() for i in range(n)]
C = [set() for i in range(n)]
flag = [False] * n

for i,a in enumerate(tree):
  A[a[1]-1].add(tree[i][0])
  B[a[0]-1].add(tree[i][1])

for i in range(n):
  C[i] = A[i] | B[i]

ans = [0] * n

for i in px:

  ans[i[0]-1] += i[1]
  
cr = deque()
cr.append(1)
flag[0] = True

while cr:
  c = cr.popleft()
  flag[c-1] = True
  for i in C[c-1]:
    if flag[i-1]:
      continue
    else:
      cr.append(i)
      ans[i-1] += ans[c-1]
print(*ans)
### BUGGY CODE ###

import numpy as np
import sys
from collections import deque

input = sys.stdin.readline
def dfs(start, G):
    stack = deque()
    stack.append(start)
    visited = [0]*len(G)
    while stack:
        label = stack.pop()
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    v_temp = dfs(i,G)
    visit = np.logical_or(visit, v_temp)
  else:
    visit[i-1] = 1
  count += 1
 
print(count)

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**5+1)
input = sys.stdin.readline

def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        _ = dfs(next,G,visit) 
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0

visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

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

x = int(input())
def make_divisors(n):
    divisors = [0]
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
    return divisors

flag = 0
a_s = 0
if x == 1:
  print(1, 0)
else:
  l = make_divisors(x)
  for i in range(x+1):
    if 2*(i**5) >= x:
      a_s = i
      break
  for a in range(a_s, x+1):
    if flag == 1:
      break
    for b_a in l:
      if b_a <= a:
        b = a - b_a
        if a**5 - b**5 == x:
          print(a, b)
          flag += 1
          break
        elif a**5 + b**5 == x:
          print(a, -1*b)
          flag += 1
          break
      else:
        continue

### FIXED CODE ###

x = int(input())
def make_divisors(n):
    divisors = [0]
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
    return divisors

flag = 0
a_s = 0
if x == 1:
  print(1, 0)
else:
  l = make_divisors(x)
  for a in range(a_s, x+1):
    if flag == 1:
      break
    for b_a in l:
      if b_a <= a:
        b = a - b_a
        if a**5 - b**5 == x or a**5 + b**5 == x:
          flag += 1
          print(a, b)
          break
      if b_a > a:
        b = b_a - a
        if a**5 + b**5 == x:
          flag += 1
          print(a, -b)
          break
### BUGGY CODE ###

N=int(input())
S=[input() for _ in range(N)]
s=sorted(list(set(S)))
l=len(s)
x=[0]*l
for i in range(l):
    x[i]+=S.count(s[i])
m=max(x)
for i in range(l):
    if m==x[i]:
        print(s[i])

### FIXED CODE ###

import collections

N=int(input())
S=sorted([input() for _ in range(N)])
s=sorted(list(set(S)))
l=len(s)
c=collections.Counter(S)
max_v = max(c.values())
for i in range(l):
    if max_v==c[s[i]]:
        print(s[i])
### BUGGY CODE ###

#import math
#from functools import reduce
from fractions import gcd
#from functools import lru_cache

#def lcm_base(x, y):
#    return (x * y) // gcd(x, y)

#def lcm(numbers):
#    return reduce(lcm_base, numbers, 1)

#@lru_cache(maxsize=1000)
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


n = int(input())
A = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))


### FIXED CODE ###

#import math
#from functools import reduce
from fractions import gcd
#from functools import lru_cache


#def lcm_base(x, y):
#    return (x * y) // gcd(x, y)

#def lcm(numbers):
#    return reduce(lcm_base, numbers, 1)


def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


n = int(input())
A = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))
### BUGGY CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man = [i for i in [0]*n]
    ball,a = p,0
    while p not in man:
        if ball >0:ball,man[a%n] =ball-1, man[a%n]+1
        elif ball == 0:ball,man[a%n] = man[a%n],ball
        a+=1
    print(man.index(max(man)))        

### FIXED CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        if man[a]==p:break
        a+=1
    print(a)
### BUGGY CODE ###

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

ans = 0
MOD = 10**9+7
for i in range(60):
    b = 1 << i
    cnt_1 = sum([a & b > 0 for a in A])
    cnt_0 = N - cnt_1
    b_sum = cnt_1 * cnt_0
    ans += (b_sum << i) % MOD
print(ans%MOD)


### FIXED CODE ###

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

ans = 0
MOD = 10**9+7
for i in range(60):
    b = 1 << i
    cnt_1 = sum([a & b > 0 for a in A])
    cnt_0 = N - cnt_1
    b_sum = cnt_1 * cnt_0
    ans += (b_sum << i) % MOD
print(ans%MOD)
### BUGGY CODE ###

n, m=map(int, input().split())
prices=list(map(int, input().split()))
for i in range(m):
  prices[prices.index(max(prices))]//=2
print(sum(prices))

### FIXED CODE ###

import heapq

n, m=map(int, input().split())
A=list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(A)

for _ in range(m):
  temp=(-1)*heapq.heappop(A)>>1
  heapq.heappush(A, temp*(-1))
print(-sum(A))
### BUGGY CODE ###

def main():
    R, C, K = map(int, input().split())
    scores = [[0] * (C + 1) for _ in range(R+1)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r][c] = v
    dp = [[[0] *4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                dp[i][j][k-1] + scores[i][j])

    answer = dp[R][C][3]
    print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    dp=np.zeros((R+1,C+1,4), np.int64)

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                  dp[i][j][k-1] + scores[i-1][j-1])

    
    return dp[R][C][3]

print(main())