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

H, N = map(int, input().split())

magic = [tuple(map(int, input().split())) for _ in range(N)]

DP = [0] + [10**9]*H

for h in range(H):
  if DP[h] == 10**9:
    continue
  for damage, mp in magic:
    DP[min(h + damage, H)] = min(DP[min(h + damage, H)], DP[h] + mp)
print(DP[H])

### FIXED CODE ###

H, N = map(int, input().split())

magic = [tuple(map(int, input().split())) for _ in range(N)]

DP = [0] + [10**9]*H

for h in range(H):
  for damage, mp in magic:
    DP[min(h + damage, H)] = min(DP[min(h + damage, H)], DP[h] + mp)
print(DP[H])
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
n = int(input())
A = []
ans = 0
adjacent_list = defaultdict(list)
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in range(1, len(tmp)):
        l, g = min(i, tmp[j] - 1), max(i, tmp[j] - 1 )
        pre_l, pre_g = min(i, pre), max(i, pre) 
        adjacent_list[pre_l * n + pre_g].append(l * n + g)
        pre = tmp[j] - 1
nodes = list(adjacent_list.keys())
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if len(adjacent_list[node]) == 0:
        return 1
    if node in finish:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = max(tmp, finish[node])
    return finish[node]
finished = set()

for i in nodes:
    check(i)
finish = defaultdict(int)
for i in nodes:
    dfs_path(i)
print(max(max(finish.values()), 1))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(0,k+1):
  for y in range(0,k+1):
    for z in range(0,k+1):
      if x+y+z == s:
         ans+=1

print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(0,k+1):
  for y in range(0,k+1):
    if s-x-y<=k and s-x-y>=0:
      ans+=1

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

def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n = int(input())
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
for a,b in ab:
    a,b = a-1,b-1
    d[a][b] = 1
    d[b][a] = 1

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

d= warshall_floyd(d)

count_f = 0
for i in range(n):
    if d[0][i] <= d[n-1][i]:
        count_f+=1


if count_f > n-count_f: print('Fennec')
else: print('Snuke')


### FIXED CODE ###

n = int(input())

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')
### BUGGY CODE ###

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

words = []
cnt = dict()
for i in range(n):
  if s[i] not in words:
    words.append(s[i])
    cnt[s[i]] = 1
  else:
    cnt[s[i]] += 1

cnt_sorted = sorted(cnt.items(), key=lambda x:x[1], reverse=True)
top_words = []
for j in range(len(cnt_sorted)):
  if cnt_sorted[j][1] == cnt_sorted[0][1]:
    top_words.append(cnt_sorted[j][0])
  else:
    break

top_words =sorted(top_words)
for i in range(len(top_words)):
  print(top_words[i])

### FIXED CODE ###

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

words = set()
cnt = dict()
for i in range(n):
  if s[i] not in words:
    words.add(s[i])
    cnt[s[i]] = 1
  else:
    cnt[s[i]] += 1

top_words = []
max_val = 0
for k, v in cnt.items():
  if v > max_val:
    max_val = v
    top_words = [k]
  elif v == max_val:
    top_words.append(k)

top_words =sorted(top_words)
for i in range(len(top_words)):
  print(top_words[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

l= []
r = []
lr = []
p = []
q = []

for i in range(m):
    lri = list(map(int, input().split()))
    lr.append(lri)
    l.append(lri[0])
    r.append(lri[1])

lr.sort(key=lambda x:(x[0],x[1]))
l.sort()

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp = lr[idxl:]
    #print(lrtmp)
    lrtmp2 = [z[1] for z in lrtmp]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

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

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)
### BUGGY CODE ###

s, t  = map(int, input().split())
u = list(map(int,input().split()))
from collections import Counter
v = Counter(u)
w = 0
for i in range(s):
    if len(v) <= t:
        print(w)
        break
    else:
        w += min(v.values())
        del v[min(v, key = v.get)]

### FIXED CODE ###

from collections import Counter
n,k = map(int,input().split())
L = list( map(int,input().split()))
l = len(L)
L = Counter(L)
L = sorted(list(L.most_common(k)))

ans = 0
for i in range(len(L)):
    ans += L[i][1]
print(l - ans)
### BUGGY CODE ###

# coding: utf-8

n, m = map(int, input().split())
l = [int(n) for n in input().split()]

for j in range(m):
    i = l.index(max(l))
    k = int(l.pop(i)/2)
    if k > 0:
        l.append(k)
    if len(l) == 0:
        break
    
print(sum(l))



### FIXED CODE ###

# coding: utf-8
import heapq

n, m = map(int, input().split())
l = [ -1 * int(n) for n in input().split()]

heapq.heapify(l)

for i in range(m):
    a = heapq.heappop(l) * (-1)
    a = int(a/2)
    if a != 0:
        heapq.heappush(l, a * (-1))
    if len(l) == 0:
        break
    
    
print(sum(l) * (-1))
### BUGGY CODE ###

import sys, math, copy
input = sys.stdin.readline

N, K = map(int, input().split())
S = list(input().replace('\n',''))
S = list(map(int, S))

max_ans = 0
cursol = 0
for i in range(N):
    cursol = i
    while cursol < N and S[cursol] == 1:
        cursol += 1
    for k in range(K):
        if cursol >= N:
            break
        l = cursol
        r = cursol
        while r < N and S[r] == 0:
            r += 1
        # print(i, k, l, r)
        cursol += (r - l)
        while cursol < N and S[cursol] == 1:
            cursol += 1
    ans = cursol - i
    max_ans = ans if ans > max_ans else max_ans

print(max_ans)

### FIXED CODE ###

import sys, math, copy
input = sys.stdin.readline

N, K = map(int, input().split())
S = list(input().replace('\n',''))
S = list(map(int, S))

group = [0]

for i in range(1,N):
    if S[i-1] != S[i]:
        group.append(i)

ans = 0
for i in range(len(group)):
    start = group[i]
    if(S[start] == 1):
        end_group_id = i + 2 * K + 1
    else:
        end_group_id = i + 2 * K
    if end_group_id < len(group):
        end = group[end_group_id]
    else:
        end = len(S)
    ans = max(ans, end - start)

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

def gcd(a,b):
    c = 0
    if b > a:
        a,b = b,a
    while a % b != 0:
        c = b
        b = a % b
        a = c
    return b
K = int(input())
count = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            count += gcd(gcd(i,j),k)
print(count)

### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(1,K+1):
            if i != j:
                count += 2 * math.gcd(math.gcd(i,j),k)
            else:
                count += math.gcd(math.gcd(i,j),k)
print(count)
### BUGGY CODE ###

import math
N, M, K = map(int, input().split())
sosu = 10 ** 9 + 7

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)
dis = M * M * N * N * (N+1) // 2 % sosu
dis = dis - M * M * N * (N+1) * ( 2* N + 1) // 6 % sosu
dis = dis + N * N * M * M * (M+1) //2 % sosu
dis = dis - N * N * M * (M+1) * (2*M + 1) // 6 % sosu


if K >= 3:
    dis = dis * C(N*M-2, K-2) % sosu
if dis >= 0:
    print(dis)
else:
    print(dis + sosu)

### FIXED CODE ###

import math
N, M, K = map(int, input().split())
sosu = 10 ** 9 + 7

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)


dis = M * M * N * N * (N+1) // 2 % sosu
dis = dis - M * M * N * (N+1) * ( 2* N + 1) // 6 % sosu
dis = dis + N * N * M * M * (M+1) //2 % sosu
dis = dis - N * N * M * (M+1) * (2*M + 1) // 6 % sosu

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = sosu #出力の制限
N = N * M
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if K >= 3:
    dis = dis * cmb(N-2, K-2, mod) % sosu
if dis >= 0:
    print(dis)
else:
    print(dis + sosu)
### BUGGY CODE ###

string=input()
count=0
times=1
length=4
while len(string) > 3:
  target=int(string[:length])
  if target % 2019 == 0:
    count+=1
  length+=1
  if length == 2000000 or len(string) < length:
    length=4
    string=string[1:]
  times+=1
print(count)


### FIXED CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
s=1
l=len(A)
for i in range(l):
    s*=A[i]
if s<=10**18:
    print(s)
else:
    print(-1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
s=1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    s*=A[i]
    if s>10**18:
        print(-1)
        exit()
print(s)
### BUGGY CODE ###

N = int(input())
A = input().split()
for i in range(N):
  count = 0
  for j in range(N-1):
    if i+1 == int(A[j]):
      count += 1
  print(count)


### FIXED CODE ###

N = int(input())
A =[int(n) for n in input().split()]
b = [0]*N
for i in A:
  b[i-1]+=1
for i in range(N):
  print(b[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
mod = 10**9+7

def comb(n, r):
    if 2*r > n: comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        x = dp[u] * comb(n-1, size[u])
        val = ans[v] * pow(x, mod-2, mod) % mod
        bfs(u, v, val, n-size[u])

n = int(input())
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

fac = [1] * (n+1)
inv = [1] * (n+1)

for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i+1] * (i+1) % mod

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys

def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7

    def comb(n, r):
        if r > n: return 0
        return fac[n] * inv[r] * inv[n - r] % mod

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= inv[size[u]] % mod
        dp[v] *= fac[size[v]] % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

    n = int(input())
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        to[a].append(b)
        to[b].append(a)

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % mod
    INV = lambda x: pow(x, mod - 2, mod)
    inv[n] = INV(fac[n])
    for i in range(n - 1, 1, -1):
        inv[i] = inv[i + 1] * (i + 1) % mod

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')

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

def count(s):
    res = 0
    for i in range(len(s)-1):
        if s[i] == 'A':
            if s[i+1] == 'C':
                res+=1
    return res
n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int,input().split())
    print (count(s[l-1:r]))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
counts = [0 for i in range(n)]
count = 0

for i in range(n):
    if s[i-1:i+1] == 'AC':
        count+=1
    counts[i] = count


for i in range(q):
    l, r = map(int,input().split())
    print (counts[r-1] - counts[l-1])
### BUGGY CODE ###


s=input()
q=int(input())
p=0
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        p=(p+1)%2
    else:
        if p==0:
            if l[1]=="1":
                s=l[2]+s
            else:
                s=s+l[2]
        else:
            if l[1]=="1":
                s+=l[2]
            else:
                s=l[2]+s

if p==0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###


s=input()
q=int(input())
p=0
a=""
b=""
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        p=(p+1)%2
    else:
        if p==0:
            if l[1]=="1":
                a+=l[2]
            else:
                b+=l[2]
        else:
            if l[1]=="1":
                b+=l[2]
            else:
                a+=l[2]
if p==1:
    print(b[::-1]+s[::-1]+a)
else:
    print(a[::-1]+s+b)
### BUGGY CODE ###

import math

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


a = input()
a = int(a)
count = 0

for l in range(1, a + 1):
    for m in range(1, a + 1):
        for n in range(1, a + 1):
            count +=  gcd(l,m,n)

print(count)

### FIXED CODE ###

import math


a = input()
a = int(a)
count = 0
for l in range(1, a + 1):
    for m in range(1, a + 1):
        x = math.gcd(l, m)
        for n in range(1, a + 1):
            count += math.gcd(x,n)

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


N = int(input())
S = input()
ans = 0

for L in range(1,N): #比較する文字列同士の距離
    dp = [0] * (N+5)
    for x in range(N-L): #文字列の始点を全探索
        if S[x] == S[x+L]:
            if x == 0:
                dp[x] += 1
            else:
                dp[x] = min(dp[x-1]+1,L)
            ans = max(ans,dp[x])
        else:
            dp[x] = 0
            
print(ans)

### FIXED CODE ###


N = int(input())
S = input()
ans = 0

for L in range(1,N): #比較する文字列同士の距離
    dp = [0] * (N+5)
    for x in range(N-L): #文字列の始点を全探索
        if S[x] == S[x+L]:
            if x == 0:
                dp[x] += 1
            else:
                dp[x] = min(dp[x-1]+1,L)
            ans = max(ans,dp[x])
        else:
            dp[x] = 0
            
print(ans)
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

m = reduce(mul, A)

if m > 10 ** 18:
  print('-1')
else:
  print(m)

### FIXED CODE ###

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

mul = 1

A.sort()

for i in range(N):
  mul *= A[i]
  if mul == 0 or mul > 10 ** 18:
    break

if mul > 10 ** 18:
  print('-1')
else:
  print(mul)
### BUGGY CODE ###

N = int(input())


def func(n):
    result = 0
    for x in range(1, n+1):
        for y in range(1, n+1):
            for z in range(1, n+1):
                check = x**2 + y**2 + z**2 + x * y + y * z + z * x
                if check == n:
                    #print("n :{} ({},{},{})".format(n, x, y, z))
                    result += 1

                if check > n:
                    break

    return result


for i in range(1, N+1):
    print(func(i))


### FIXED CODE ###

from math import sqrt

N = int(input())
result = [0] * N

n = int(sqrt(N))

for x in range(1, n+1):
    for y in range(1, n+1):
        for z in range(1, n+1):
            check = x**2 + y**2 + z**2 + x * y + y * z + z * x

            if check <= N:
                result[check-1] += 1

for i in result:
    print(i)
### BUGGY CODE ###

N = int(input())
X = list(input())
es = [0,N,0]

def p(X):
    print(X)

def list_change(X):
    for i in range(N):
        if X[i] == 'W':
            es[0] = i
            for j in reversed(range(es[1])):
                if X[j] == 'R':
                    es[1] = j
                    if i<j :
                        X[i] = 'R'
                        X[j] = 'W'
                        es[2] +=1
                        break
                elif j == 0:
                    break


list_change(X)
p(es[2])


### FIXED CODE ###

N = int(input())
X = list(input())
es = [0,N,0]

def p(X):
    print(X)

def list_change(X):
    for i in range(N):
        if X[i] == 'W':
            es[0] = i
            for j in reversed(range(es[1])):
                if X[j] == 'R':
                    es[1] = j
                    if i<j :
                        X[i] = 'R'
                        X[j] = 'W'
                        es[2] +=1
                        break
                elif j == 0:
                    es[1] = 1
                


list_change(X)
p(es[2])
### BUGGY CODE ###

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

for _ in range(M):
  A.sort()
  A[-1] = A[-1]//2

print(sum(A))

### FIXED CODE ###

from heapq import heappop, heappush

N, M = map(int, input().split())
A = list(map(lambda x: (-1)*int(x), input().split()))

H = []

for i in A:
  heappush(H, i)

for _ in range(M):
  m = (-1) * heappop(H)
  m //= 2
  heappush(H, (-1)*m)

print((-1)*sum(H))
### BUGGY CODE ###

heap = []
tail = -1


def insert(k):
    global heap, tail
    heap.append(k)
    tail += 1
    bubble(tail)


def bubble(i):
    global heap
    if not i: return
    pi = (i - 1) // 2
    if heap[i] > heap[pi]:
        heap[i], heap[pi] = heap[pi], heap[i]
        bubble(pi)


def extract():
    global heap, tail
    tail -= 1
    if tail < 0:
        return heap.pop()
    else:
        ret = heap[0]
        heap[0] = heap.pop()
        anchor(0)
        return ret


def anchor(i):
    global heap, tail
    li, ri = i * 2 + 1, i * 2 + 2
    if li <= tail:
        largest = li
        if ri <= tail and heap[ri] > heap[li]:
            largest = ri
        if heap[largest] > heap[i]:
            heap[i], heap[largest] = heap[largest], heap[i]
            anchor(largest)


while True:
    l = input()
    if l.startswith('i'):
        insert(int(l.split()[1]))
    elif l[1] == 'x':
        print(extract())
    else:
        break

### FIXED CODE ###

from heapq import heappush, heappop

heap = []

while True:
    l = input()
    if l.startswith('i'):
        heappush(heap, -int(l.split()[1]))
    elif l[1] == 'x':
        print(-heappop(heap))
    else:
        break
### BUGGY CODE ###

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

for i in range(n):
    l = a[:i]+a[i+1:]
    pattern = 0
    for j in set(l):
        sum = l.count(j)
        pattern += sum*(sum-1)//2
    print(pattern)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
d = collections.Counter(a)
s = sum([i*(i-1)//2 for i in d.values()])

for j in a:
    print(s-d[j]+1)
### BUGGY CODE ###

N = int(input())

def CheckDigit(A, B):
    # A末とB先端 
    if A[0] != B[len(B) - 1]: return 0
    # A先端とB末
    if B[0] != A[len(A) - 1]: return 0
    return 1 

def ArrayRotation(n):
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += CheckDigit(str(i+1), str(j+1))
    return ans

if N <= 11:
    print(N)
else:
    print(ArrayRotation(N))

### FIXED CODE ###

N = int(input())
digit =[[0] * 10 for i in range(10)]

def CheckDigit():
    ans = 0
    for i in range(10):
        for j in range(10):
            ans += digit[i][j] * digit[j][i]
    return ans

def ArrayRotation(n):
    for i in range(1, n+1):
        tmp = str(i)
        digit[int(tmp[0])][int(tmp[-1])] += 1

if N <= 11:
    print(N)
else:
    ArrayRotation(N)
    print(CheckDigit())
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=a[i]^a[j]
print(ans%(10**9+7))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(62):
    c=0
    for ai in a:
        if ai&(1<<i):
            c+=1
    r=c*(n-c)
    ans+=(1<<i)*r
    ans%=(10**9+7)
print(ans)
### BUGGY CODE ###

N = int(input())
C = [int(input()) for _ in range(N)]
f = [0] * N

ans = 1
pre = 0
for i, c in enumerate(C):
    if pre == c:
        f[i] = ans
        continue
    else:
        pre = c

    flag = True
    for j in range(i - 1):
        if C[j] == c:
            if flag:
                if j == 0:
                    ans += 1
                else:
                    ans += f[j - 1]
                flag = False
            else:
                continue
        else:
            flag = True
    f[i] = ans

print(ans)

### FIXED CODE ###

import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))