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

import math
mod=10**9+7
N=10**6+1
inv_t=[0]+[1]
for i in range(2,N):
    inv_t+=[inv_t[mod%i]*(mod-int(mod/i))%mod]
n=int(input())
A=list(map(int,input().split()))
l=[0]*10**6
for a in A:
    for i in [2]+list(range(3,int(math.sqrt(a))+1,2)):
        c=0
        while a%i==0:
            c+=1
            a//=i
        l[i]=max(l[i],c)
    if a!=1:
        l[a]=max(l[a],1)
lcm=1
for i in range(10**6):
    if l[i]!=0:
        lcm=(lcm*(i**l[i]))%mod
ans=0
for a in A:
    ans=(ans+lcm*inv_t[a])%mod
print(ans)

### FIXED CODE ###

N=10**6+1
mod=10**9+7

inv_l=[0,1]
for i in range(2,N):
    inv_l+=[inv_l[mod%i]*(mod-int(mod/i))%mod]

prime_list=[]
min_prime=[1]*(N+1)
is_prime=[0,0]+[1]*(N-1)
for i in range(2,N+1):
    if is_prime[i]==1:
        prime_list.append(i)
        j=i
        while j<=N:
            is_prime[j]=0
            if min_prime[j]==1:
                min_prime[j]=i
            j+=i

def lcm(l,mod):
    max_count=[0]*(N+1)
    for a in l:
        a_min_prime=min_prime[a]
        a_count=0
        while a>1:
            if min_prime[a]==a_min_prime:
                a_count+=1
                a//=a_min_prime
            else:
                max_count[a_min_prime]=max(max_count[a_min_prime],a_count)
                a_min_prime=min_prime[a]
                a//=a_min_prime
                a_count=1
            if a==1:
                max_count[a_min_prime]=max(max_count[a_min_prime],a_count)
    ret=1
    for i in range(1,N+1):
        if max_count[i]!=0:
            ret=(ret*i**max_count[i])%mod
    return ret

n=int(input())
A=list(map(int,input().split()))
L=lcm(A,mod)
ans=0
for i in range(n):
    ans=(ans+L*inv_l[A[i]])%mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())  
st = s
count = 0
for i in range(q):
  k = input().split()
  if(k[0] == '1'):
    count = (count + 1) % 2
  else:
    c = count
    d = int(k[1]) 
    e = k[2]
    if(c + d == 1 or c + d == 3):
      st = e + st
    elif(c + d == 2):
      st = st + e

if(count % 2 == 1):
  st = st[::-1]
      
print(st)

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())  
st = s
sth = s
sth2 = ""
stm = ""
stm2 = ""
count = 0
flagh = 0
flagm = 0
for i in range(q):
  k = input().split()
  if(k[0] == '1'):
    count = (count + 1) % 2
  else:
    c = count - 2
    d = int(k[1]) 
    e = k[2]
    if(c + d != 0):
      sth = e + sth
      if(len(sth) > 5000 and flagh == 0):
        flagh = 1
        sth2 = sth
        sth = ""
    else:
      stm = stm + e
      if(len(stm) > 5000 and flagm == 0):
        flagm = 1
        stm2 = stm
        stm = ""
      

st = sth + sth2 + stm2 + stm
if(count == 1):
  st = st[::-1]
  
print(st)
### BUGGY CODE ###

X = input()

while(True):
    temp = X.replace("ST","")
    if len(X)==len(temp):break
    X = temp
    
print(len(X))

### FIXED CODE ###

X = input()

T = 0
S = 0
TS = True
for x in X:
    if x=="T":
        if TS:
            T += 1
        else:
            S -= 1
            if S==0:
                TS = True
    else:
        if TS: TS = False
        S += 1
    
print(T+S)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
abs_a = []
minus = 0

for i in range(n):
  if a[i] < 0: minus += 1

if minus % 2 == 0:
  for i in range(n):
    abs_a.append(abs(a[i]))
  print(sum(abs_a))
else:
  for i in range(n):
    abs_a.append(abs(a[i]))
    min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
abs_a = []
minus = 0

for i in range(n):
  if a[i] < 0: minus += 1

for i in range(n):
  abs_a.append(abs(a[i]))
  
if minus % 2 == 0:
  print(sum(abs_a))
else:
  min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)
### BUGGY CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        new_stack = deque()
        #for a,b in stack:
        while stack:
            a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()




### FIXED CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す

"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx]+S[sidx+1] == 'AC':
        ACs.append(sidx)
#  print(ACs)
#  LR = []
#  for i in range(Q):
#      LR.append(LI())
#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
for _ in range(Q):
    l,r = LI()
    res = len([i for i in ACs if i >= l- 1 and i < r-1])
    result.append(res)
for i in result:
    print(i)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx] == 'A':
        if S[sidx+1] == 'C':
            ACs.append(sidx)

#  print(ACs)

LR = []
for i in range(Q):
    LR.append(LI())

#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for l, r in LR:
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    print(end-start)
### BUGGY CODE ###

H, W = map(int, input().split())
S_list = [None] * H

for h in range(H):
    S_list[h] = list(input())


l_list = [[0] * W for _ in range(H)]
r_list = [[0] * W for _ in range(H)]
d_list = [[0] * W for _ in range(H)]
u_list = [[0] * W for _ in range(H)]
for h in range(H):
    for w in range(W):
        left_index = w
        right_index = W - w - 1
        up_index = h
        down_index = H - h - 1

        #left
        if S_list[h][left_index] != '#':
            if left_index == 0:
                l_list[h][left_index] = 1
            else:
                l_list[h][left_index] = l_list[h][left_index - 1] + 1

        #right
        if S_list[h][right_index] != '#':
            if right_index == W - 1:
                r_list[h][right_index] = 1
            else:
                r_list[h][right_index] = r_list[h][right_index + 1] + 1

        #up
        if S_list[up_index][w] != '#':
            if up_index == 0:
                u_list[up_index][w] = 1
            else:
                u_list[up_index][w] = u_list[up_index - 1][w] + 1

        #down
        if S_list[down_index][w] != '#':
            if down_index == H - 1:
                d_list[down_index][w] = 1
            else:
                d_list[down_index][w] = d_list[down_index + 1][w] + 1


max_right = 0
for h in range(H):
    for w in range(W):
        rights = l_list[h][w] + r_list[h][w] + u_list[h][w] + d_list[h][w] - 3
        max_right = max(max_right, rights)

print(max_right)


### FIXED CODE ###

#ref. https://atcoder.jp/contests/abc129/submissions/5906191
import numpy as np
import sys

def main():
    sin = sys.stdin.buffer
    H, W = map(int, sin.readline().split())
    grid = np.frombuffer(sin.read(H * (W + 1)), dtype="B") == ord(".")
    grid = grid.reshape((H, W + 1))[:, :-1]

    L = np.empty((H, W), dtype="i4")
    R = np.empty((H, W), dtype="i4")
    T = np.empty((H, W), dtype="i4")
    B = np.empty((H, W), dtype="i4")

    T[0] = grid[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * grid[i]

    B[-1] = grid[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * grid[i]

    L[:, 0] = grid[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * grid[:, i]

    R[:, -1] = grid[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * grid[:, i]

    ans = (T + B + L + R - 3).max()
    print(ans)

main()
### BUGGY CODE ###

from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    Q =     _in[1]   # type:str
    Q_arr = []
    for __in in _in[2:]:
        _ = __in.split(' ')
        if len(_) == 1:
            Q_arr.append([int(_[0])])
        else:
            Q_arr.append([int(_[0]),int(_[1]),_[2]])
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    reverse = False
    for _Q in Q_arr:
        if _Q[0] == 1:
            reverse = not reverse
        elif (_Q[1] == 1 and (not reverse)) or (_Q[1] == 2 and reverse):
            S = _Q[2] + S
        else:
            S = S + _Q[2]
    if reverse:
        S = S[::-1]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(S)


### FIXED CODE ###

from sys import stdin
from collections import deque

if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    Q =     _in[1]   # type:str
    Q_arr = []
    for __in in _in[2:]:
        _ = __in.split(' ')
        if len(_) == 1:
            Q_arr.append([int(_[0])])
        else:
            Q_arr.append([int(_[0]),int(_[1]),_[2]])
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    S_arr = deque([s for s in S])
    reverse = False
    for _Q in Q_arr:
        if _Q[0] == 1:
            reverse = not reverse
        elif (_Q[1] == 1 and (not reverse)) or (_Q[1] == 2 and reverse):
            S_arr.appendleft(_Q[2])
        else:
            S_arr.append(_Q[2])
    if reverse:
        S_arr.reverse()
    S_arr = list(S_arr)
    S = ''.join(S_arr)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(S)
### BUGGY CODE ###

s = input()
num = len(s)

def aaa(s, num):
    x = 0
    for i in range(4,num+1):
        for j in range(num - i + 1):
            if int(s[j:j+i]) % 2019 == 0:
                x += 1
    print(x)

aaa(s,num)

### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

N,P = map(int,input().split(' '))
#N=3
#P=24


def primes(n):
	f = [True]*(n+1)
	f[0] = False
	f[1] = False
	m = int(n**0.5+1)
	for i in range(2,m):
		if f[i]:
			for j in range(i*i,n+1, i):
				f[j] = False
	return f

if N == 1:
	print(P)
	exit()

s = 1/N
sP=int(P**s)+1
f = primes(sP)
prime = [x for x in range(1,sP+1) if f[x]]

ans = 1
for p in prime:
	if P % (p**N) == 0:
		ans*=p
		P=P//p**N
		while(P % p**N == 0):
			ans*=p
			P=P//p**N
print(ans)






### FIXED CODE ###

import numpy as np
N,P = map(int,input().split(' '))
#N=3
#P=24


def primes(n):
	f = [True]*(n+1)
	f[0] = False
	f[1] = False
	m = int(n**0.5+1)
	for i in range(2,m):
		if f[i]:
			for j in range(i*i,n+1, i):
				f[j] = False
	return f


if N == 1:
	print(P)
	exit()

thres = int(np.log2(P))+1
if N > thres:
	print(1)
	exit()

s = 1/N
sP=int(P**s)+1
f = primes(sP)
prime = [x for x in range(1,sP+1) if f[x]]

ans = 1
	
for p in prime:
	q = p**N
	if P < q:
		break
	if P % q == 0:
		ans*=p
		q*= p**N
		while(P % q == 0):
			ans*=p
			q*=p**N

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

N = int(input())
Mmax = 0
for i in range(N):
    Mmax += i
#a[0] = a[-1]

print(Mmax)

### FIXED CODE ###

N = int(input())

a = N/2
b = int(N/2)
if not(N%2 == 0):
    Mmax = N*b
elif N%2 == 0:
    Mmax = N*(b-1) + b



print(Mmax)
### BUGGY CODE ###

from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

import sys
input = sys.stdin.buffer.readline
from math import hypot
sx,sy,gx,gy=map(int,input().split())
n=int(input())
v=[(sx,sy,0),(gx,gy,0)]
for _ in range(n):
	v.append(tuple(map(int,input().split())))
con=[[] for _ in range(n+2)]
for i,p1 in enumerate(v):
	for j,p2 in enumerate(v[i+1:]):
		t=max(0,hypot(p1[0]-p2[0],p1[1]-p2[1])-p1[2]-p2[2])
		con[i].append((i+j+1,t))
		con[i+j+1].append((i,t))
print(Dijkstra(con)[1])

### FIXED CODE ###

from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

import sys
input = sys.stdin.buffer.readline
from math import hypot
sx,sy,gx,gy=map(int,input().split())
n=int(input())
v=[(sx,sy,0),(gx,gy,0)]
for _ in range(n):
	v.append(tuple(map(int,input().split())))
con=[[] for _ in range(n+2)]
for i,p1 in enumerate(v):
	for j,p2 in enumerate(v[i+1:]):
		t=max(0,hypot(p1[0]-p2[0],p1[1]-p2[1])-p1[2]-p2[2])
		con[i].append((i+j+1,t))
		con[i+j+1].append((i,t))
print(Dijkstra(con)[1])
### BUGGY CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))

from collections import deque

d=deque([])
total= 0
for i in range(N):
    d.append(Dices[i])
    if len(d)==K:
        total = max(total,sum(d))
        d.popleft()

print(total)



### FIXED CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))
import numpy as np 
Dices = np.cumsum(Dices)
# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=np.append(0,Dices)
total = 0
# for i in range(N+1):
#     S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])

print(total)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = list()
C = list()
for i in range(Q):
  b, c = map(int, input().split())
  B.append(b)
  C.append(c)
sorted(A)
A_sum = sum(A)

break_flg = False
for i in range(Q):
  count = 0
  break_flg = False
  bi = B[i]
  ci = C[i]
  for j in range(len(A)):
    ai = A[j]
    if bi == ai:
      A[j] = C[i]
      break_flg = True
      count += 1
    
    if (bi != ai or j == len(A)-1) and break_flg == True:
      A_sum += (count * (ci - bi))
      print(A_sum)
      break
    elif break_flg == False and j == len(A)-1:
      print(A_sum)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = list()
C = list()
for i in range(Q):
  b, c = map(int, input().split())
  B.append(b)
  C.append(c)

A_sum = sum(A)
num_count = [0] * (10 ** 5)

for a in A:
  num_count[a-1] += 1
for i in range(Q):
  if num_count[B[i]-1] != 0:
    A_sum += (C[i] - B[i]) * num_count[B[i]-1]
    print(A_sum)
    num_count[C[i]-1] += num_count[B[i]-1]
    num_count[B[i]-1] = 0
  else:
    print(A_sum)
### BUGGY CODE ###

import itertools
import queue
N=int(input())
S=input()
ans=0
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    for i in range(N):
        if seq[i]==0:
            T0=T0+S[i]
        else:
            T1=T1+S[i]
        T2+=S[-i-1]
    q=[queue.Queue() for i in range(N+1)]
    q[0].put((0,0))
    a0=len(T0)
    a1=len(T1)
    #print(T0,T1,T2)
    for i in range(N):
        while(not(q[i].empty())):
            r=q[i].get()
            #print(i,r)
            #print(r)
            if r[0]+r[1]>=N:
                continue
            if r[0]>=a0:
                if T2[r[1]+r[0]]==T1[r[1]]:
                    q[i+1].put((r[0],r[1]+1))
            elif r[1]>=a1:
                if T2[r[1]+r[0]]==T0[r[0]]:
                    q[i+1].put((r[0]+1,r[1]))
            else:
                if T2[r[1]+r[0]]==T0[r[0]]:
                    q[i+1].put((r[0]+1,r[1]))
                if T2[r[1]+r[0]]==T1[r[1]]:
                    q[i+1].put((r[0],r[1]+1))
    while(not(q[N].empty())):
        r=q[N].get()
        #print(N,r)
        ans+=1
        #print(ans)
print(ans)


### FIXED CODE ###

import itertools
import bisect
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    if (T0,T1) in L:
        L[(T0,T1)]+=1
    else:
        L[(T0,T1)]=1
    if (T2,T3) in R:
        R[(T2,T3)]+=1
    else:
        R[(T2,T3)]=1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)
### BUGGY CODE ###

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

Mat = [[0] * (N - 1) + [N] for d in range(20)]
prev = [-1] * 20

for i, A in enumerate(As):
    binA = format(A, 'b').zfill(20)
    for d in range(20):
        if binA[d] == '1':
            if prev[d] != -1:
                Mat[d][prev[d]] = i
            prev[d] = i

for d in range(20):
    for i in reversed(range(N - 1)):
        if Mat[d][i] == 0:
            Mat[d][i] = Mat[d][i + 1]

minM = list(map(min, *Mat))

print(sum(minM) - N * (N - 1) // 2)


### FIXED CODE ###

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

Mat = [[float('inf')] * (N - 1) + [N] for d in range(20)]
prev = [-1] * 20

for i, A in enumerate(As):
    binA = format(A, 'b').zfill(20)
    for d in range(20):
        if binA[d] == '1':
            if prev[d] != -1:
                Mat[d][prev[d]] = i
            prev[d] = i

minM = list(map(min, *Mat))

for i in reversed(range(N - 1)):
    minM[i] = min(minM[i], minM[i + 1])

print(sum(minM) - N * (N - 1) // 2)
### BUGGY CODE ###

def main():
    INF = 10**9
    H,N = map(int,input().split())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int,input().split())
    dp = [INF]*(H+max(A))
    dp[0] = 0
    for i in range(N):
        for j in range(A[i],H+max(A)):
            dp[j] = min(dp[j],dp[j-A[i]]+B[i])
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

n,m = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(m):
  a[-1] = a[-1]//2
  a = sorted(a)
  
print(sum(a))

### FIXED CODE ###

n,m = map(int, input().split())
def intm(x):
  return int(x)*-1
a = list(map(intm, input().split()))

import heapq

heapq.heapify(a)

for _ in range(m):
  x = heapq.heappop(a)
  x = int(x/2)
  heapq.heappush(a,x)
  
print(sum(a)*-1)