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

import copy
import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
res1=[-1]*n
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(n):
    if res1[A[i]-1]==-1:
        ac=copy.deepcopy(A)
        del ac[i]
        ak=collections.Counter(ac)
        aj=list( ak.values() )
        s=0
        for j in range(len(aj)):
            s=s+com(aj[j],2)
        res[i]=s
        res1[A[i]-1]=s
    else:
        res[i]=res1[A[i]-1]
for j in range(n):
    print(res[j])

### FIXED CODE ###

import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

af=collections.Counter(A)
res2=list(af.items())
res3=[0]*n
s=0
for i in range(0,len(res2)):
    s=s+com(res2[i][1],2)
for j in range(0,len(res2)):
    res3[res2[j][0]-1]=s-res2[j][1]+1
for i in range(n):
    res[i]=res3[A[i]-1]

for j in range(n):
    print(res[j])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
 
cnt=0
cnt= cnt + sum([(L[i+x]+L[i])==x for i in range(N) for x in range(N-i)  if (L[i+x]+L[i])<=x ])
    
print(cnt)

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()
### BUGGY CODE ###

# 1行目は入力ワード数
# word を1行ずつ入力し、最も投票数が多かったwordを出力

def check(input_list):
    vote_dict = {}
    
    for a in input_list:
        if(a in vote_dict.keys()):
            vote_dict[a] += 1
        else:
            vote_dict[a] = 1
            
    result_list = [k for k, v in vote_dict.items() if v == max(vote_dict.values())]
    result_list.sort()
    
    return result_list

if __name__ == '__main__':
    num = int(input())
    input_list = [input() for a in range(num)]

    for str in check(input_list):
        print(str)


### FIXED CODE ###

import collections

def check(input_list):

    vote_dict = collections.Counter(input_list)
    max_value = max(vote_dict.values())

    result_list = [k for k, v in vote_dict.items() if v == max_value]
    result_list.sort()
    
    return result_list

if __name__ == '__main__':
    num = int(input())
    input_list = [input() for a in range(num)]

    for str in check(input_list):
        print(str)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr_list = [list(map(int, input().split())) for i in range(Q)]

for lr in lr_list:
    print(S[lr[0] - 1:lr[1]].count("AC")) 


### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr_list = [list(map(int, input().split())) for i in range(Q)]

ac_list  = [0]*N
cnt = 0
for i in range(N-1):
    if i < len(S) and S[i:i+2] == "AC":
        cnt += 1
    ac_list[i+1] = cnt
        
for lr in lr_list:
    print(ac_list[lr[1]-1] - ac_list[lr[0]-1])
### BUGGY CODE ###

import itertools
from functools import reduce

N = int(input())
distance = []
C = []

def prime_f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a  
A = prime_f(N)

if len(A) == 1:
  print(N - 1)
else:
  for i in range(1,len(A)):
    C = list(set(itertools.combinations(A,i)))
    for j in range(0,len(C)):
      totalC = reduce(lambda x,y:x*y,C[j])
      div = int(N / totalC)
      distance.append(div + totalC)

  print(min(distance) - 2)

### FIXED CODE ###

n = int(input())

distance = 10 ** 12

i = 1

while i * i <= n:
  if n % i == 0:
    m = int(n / i)
    move = (m - 1) + (i - 1)
    if move < distance:
      distance = move
  i += 1

print(distance)
### BUGGY CODE ###

num = int(input())
words = []
answer = 0

for i in range(num):
  words.append(sorted(list(input())))
words.sort(key=lambda x:(x[9],x[8],x[7],x[6],x[5],x[4],x[3],x[2],x[1],x[0]))
for i in range(num - 1):
  q = 0
  for j in range(num -i - 1):
    if q >0 and words[i][9] != words[j + 1 + i][9]:
      break
    if words[i] == words[j + 1 + i]:
      answer += 1
      q += 1
    
    
print(answer)


### FIXED CODE ###

import math
num = int(input())
words = {}

for i in range(num):
  a = str(sorted(list(input())))
  
  if a in words:
    words[a] += 1
  else:
  	words[a] = 1

points = list(words.values())
sum = 0
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(len(points)):
  if points[i] > 1:
  	sum += combinations_count(points[i], 2)
print(sum)
### BUGGY CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()
A = inintl()

MOD = 1000000007

ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        ans += A[i]*A[j] % MOD
        ans %= MOD

print(ans)

### FIXED CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()
A = inintl()

S = [0]*(n+1)
ans = 0

for i in range(n):
    S[i+1] = S[i] + A[i]

for i in range(1,n):
    ans += A[i-1]*(S[-1] - S[i])
    ans %= (10**9 + 7)

print(ans % (10**9 + 7))
### BUGGY CODE ###

class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

    def find(self, x):
        if self.par[x] == x: return x
        p = self.find(self.par[x])
        self.diff_w[x] += self.diff_w[self.par[x]]
        self.par[x] = p
        return self.par[x]

    def weight(self, x):
        self.find(x)
        return self.diff_w[x]

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True

n,m = map(int, input().split())
uf = UF_weighed(n+1)
for _ in range(m):
  a, b, c = map(int, input().split())
  if uf.same(a, b) and uf.diff(a, b) != c:
    print('No')
    break
  uf.merge(a, b, c)
else:
  print('Yes')

### FIXED CODE ###

n,m = map(int,input().split())
l = dict()
tl = []
for i in range(n+1):
  l[i] = []
for _ in range(m):
  a,b,c = map(int,input().split())
  l[a].append((b,c))
  l[b].append((a,-c))
  tl.append((a,b,c))
pos = [None]*(n+1)

def dfs(v,p,pos):
  q = [(v,p)]
  while q:
    cv,cp = q.pop()
    if pos[cv] != None:
      continue
    pos[cv] = cp
    for i,d in l[cv]:
      if pos[i] == None:
        q.append((i,cp+d))
  return

for i in range(1,n+1):
  if pos[i] == None:
    dfs(i,0,pos)
for a,b,c in tl:
  if pos[b] - pos[a] != c:
    print("No")
    break
else:
  print("Yes")
### BUGGY CODE ###

a = []
a = input().split()
N = int(a[0])
K = int(a[1])
Q = int(a[2])

A = []

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

Point = [K for i in range(N)]

for i in range(Q) :
  for j in range(N) :
    if j+1 == A[i] :
      Point[j] = Point[j]
    else :
      Point[j] = Point[j] - 1
#  print('Point', Point)

for i in range(N) :
  if Point[i] > 0 :
    print('Yes')
  else :
    print('No')

#print('N', N)
#print('K', K)
#print('Q', Q)
#print('A', A)
#print('Point', Point)


### FIXED CODE ###

a = []
a = input().split()
N = int(a[0])
K = int(a[1])
Q = int(a[2])

A = []
for i in range(Q) :
  A.append(int(input()))

point = [K-Q for i in range(N)]

for i in range(Q) :
  point[A[i]-1] = point[A[i]-1] + 1

for i in range(N) :
  if point[i] > 0 :
    print('Yes')
  else :
    print('No')
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect
from fractions import Fraction
from collections import defaultdict


def mode(a, b):
    # retrun dict_key, arr_key
    if a == 0 and b == 0:
        return 0, 0
    if a == 0:
        return 'ab', 0
    if b == 0:
        return 'ab', 1
    x = Fraction(a, b)
    y = Fraction(-1 * b, a)
    if x > y:
        return x, 0
    else:
        return y, 1

MOD = 1000000007

if __name__ == '__main__':

    n = int(input())

    d = defaultdict(lambda: [0, 0])
    zero = 0
    for _ in range(n):
        a, b = list(map(int, input().split()))
        dkey, akey = mode(a, b)
        if dkey == 0:
            zero += 1
        else:
            d[dkey][akey] += 1
    #print('d') # debug
    #pp(d) # debug

    ans = 1
    for pair in d.values():
        tmp = pow(2, pair[0], MOD) - 1 + pow(2, pair[1], MOD) - 1 + 1
        ans *= tmp
    ans += zero - 1
    ans %= MOD
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect
from fractions import Fraction
from collections import defaultdict

def is_same_sign(a, b):
    if a > 0 and b > 0:
        return True
    if a < 0 and b < 0:
        return True
    return False

def fraction_taple(a, b):
    g = math.gcd(a, b)
    if is_same_sign(a, b):
        s = 1
    else:
        s = -1
    a = abs(a) // g
    b = abs(b) // g
    return (s, a, b)

def mode(a, b):
    # retrun dict_key, arr_key
    if a == 0 and b == 0:
        return 0, 0
    if a == 0:
        return 'ab', 0
    if b == 0:
        return 'ab', 1
    x = fraction_taple(a, b)
    y = fraction_taple(-1 * b, a)
    if x > y:
        return x, 0
    else:
        return y, 1

MOD = 1000000007

if __name__ == '__main__':

    n = int(input())

    d = defaultdict(lambda: [0, 0])
    zero = 0
    for _ in range(n):
        a, b = list(map(int, input().split()))
        dkey, akey = mode(a, b)
        if dkey == 0:
            zero += 1
        else:
            d[dkey][akey] += 1
    #print('d') # debug
    #pp(d) # debug

    ans = 1
    for pair in d.values():
        tmp = pow(2, pair[0], MOD) - 1 + pow(2, pair[1], MOD) - 1 + 1
        ans *= tmp
    ans += zero - 1
    ans %= MOD
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug
### BUGGY CODE ###

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

for i in range(N):
  if abs(N-K)<N:
    N=abs(N-K)
print(N)


### FIXED CODE ###

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

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
sys.setrecursionlimit(10**6)
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    il = [0]*N
    ol = [0]*N
    cnt = [-1]
    def dfs(u, p):
        cnt[0] += 1
        il[u] = cnt[0]
        for i in ab[u]:
            if i != p:
                dfs(i, u)
        ol[u] = cnt[0]
    dfs(0, -1)
    vs = [[] for i in range(N)]
    for i in range(N):
        vs[c[i]-1].append(i)
    for i in range(N):
        ans = tot
        sl = [1]*N
        tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
        for v in tvs:
            n = 1
            for j in ab[v]:
                if il[j] > il[v]:
                    tmp = sum(sl[il[j]:ol[j]+1])
                    ans -= tmp*(tmp+1)//2
                    n += tmp
            sl[il[v]] -= n
        tmp = sum(sl[0:ol[0]+1])
        ans -= tmp*(tmp+1)//2
        print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
sys.setrecursionlimit(10**6)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    il = [0]*N
    ol = [0]*N
    cnt = [0]
    def dfs(u, p):
        cnt[0] += 1
        il[u] = cnt[0]
        for i in ab[u]:
            if i != p:
                dfs(i, u)
        ol[u] = cnt[0]
    dfs(0, -1)
    vs = [[] for i in range(N)]
    for i in range(N):
        vs[c[i]-1].append(i)
    sl = Bit(N)
    for i in range(1, N+1):
        sl.add(i, 1)
    for i in range(N):
        his = []
        ans = tot
        tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
        for v in tvs:
            n = 1
            for j in ab[v]:
                if il[j] > il[v]:
                    tmp = sl.sum(ol[j])-sl.sum(il[j]-1)
                    ans -= tmp*(tmp+1)//2
                    n += tmp
            sl.add(il[v], -n)
            his.append([il[v], n])
        tmp = sl.sum(ol[0])-sl.sum(0)
        ans -= tmp*(tmp+1)//2
        for h in his:
            sl.add(h[0], h[1])
        print(ans)
resolve()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N, M = [int(i) for i in input().split(" ")]
p = list()
y = list()
yd = {}
for i in range(0, M):
    pi, yi = [int(i) for i in input().split(" ")]
    p.append(pi)
    y.append(yi)
    if pi in yd.keys():
        yd[pi].append(yi)
    else:
        yd[pi] = [yi]

ydid = {}
for i in yd.keys():
    num = 1
    for j in sorted(yd[i]):
        ydid[j] = num
        num = num + 1

for i in range(0, M):
    print("{:06}{:06}".format(p[i], ydid[y[i]]))


### FIXED CODE ###

N, M = [int(i) for i in input().split(" ")]
p = list()
y = list()
yd = {}
for i in range(0, M):
    pi, yi = [int(i) for i in input().split(" ")]
    p.append(pi)
    y.append(yi)
    if pi in yd.keys():
        yd[pi].append(yi)
    else:
        yd[pi] = [yi]

ydid = {}
for i in yd.keys():
    num = 1
    for j in sorted(yd[i]):
        ydid[j] = num
        num = num + 1

for i in range(0, M):
    print("{:06}{:06}".format(p[i], ydid[y[i]]))
### BUGGY CODE ###

#C
#入力
N=int(input())
A=list(map(int,input().split()))
#処理
for i in range(N):
    print(A.index(i+1)+1, end=" ")

### FIXED CODE ###

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

#処理
B=[0 for i in range(N)]

for i in range(N):
    B[A[i]-1]=i+1
    

for i in B:
    print(i,end=" ")
### BUGGY CODE ###

# D - Friend Suggestions
from collections import deque
N,M,K = map(int,input().split())
friend = [set() for _ in range(N+1)]
block = [{i} for i in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    friend[x].add(y)
    friend[y].add(x)
for _ in range(K):
    x,y = map(int,input().split())
    block[x].add(y)
    block[y].add(x)
connect = [{i} for i in range(N+1)]
for i in range(1,N+1):
    if connect[i]!={i}:
        continue
    que = deque([i])
    con = {i}
    while len(que)>0:
        j = que.popleft()
        for x in friend[j]:
            if x not in con:
                que.append(x)
                con.add(x)
    for x in con:
        connect[x] = set(con)
ans = [len(connect[i].difference(friend[i],block[i])) for i in range(1,N+1)]
print(*ans)

### FIXED CODE ###

# D - Friend Suggestions

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parents[self.root(x)]

N,M,K = map(int,input().split())
friend = UnionFind(N+1)
block = [1]*(N+1)
for _ in range(M):
    x,y = map(int,input().split())
    block[x] += 1
    block[y] += 1
    friend.union(x,y)
for _ in range(K):
    x,y = map(int,input().split())
    if friend.same(x,y):
        block[x] += 1
        block[y] += 1
ans = [friend.size(i)-block[i] for i in range(1,N+1)]
print(*ans)
### BUGGY CODE ###

import bisect
import math
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

if n == 1:
    ans = max((a[0] - k) * f[0], 0)
    print(ans)

else:
    a.sort()
    f.sort(reverse=True)
    s = []
    t = []
    for x,y in zip(a,f):
        s.append((x*y, y))
    s.sort()

    while len(s) > 1:
        t.append(s[-1])
        tmp = 0
        for l, y in t:
            tmp += math.ceil((l - s[-2][0]) / y)
        if k <= tmp:
            t = t[:-1]
            break
        s = s[:-1]
    
    for l, y in t:
        tmp = math.ceil((l - s[-1][0]) / y)
        k -= tmp
        l -= tmp * y
        bisect.insort(s, (l, y))
    
    while k > 0 and s[-1][0] > 0:
        l, y = s[-1]
        s = s[:-1]
        tmp = math.ceil((l - s[-1][0]) / y)
        if tmp == 0:
            tmp = 1
        if k > tmp:
            k -= tmp
        else:
            tmp = k
            k = 0
        l = l - tmp * y
        bisect.insort(s, (l, y))
    print(s[-1][0])


### FIXED CODE ###

import math
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

a.sort()
f.sort(reverse=True)

low = 0
high = 0
for x, y in zip(a,f):
    high = max(high, x*y)

while high != low:
    test = int((high + low) // 2)
    tmp = 0
    for x, y in zip(a,f):
        tmp += max(0, x - math.floor(test / y))
        if tmp > k:
            low = test + 1
            break
    else:
        high = test
print(high)
### BUGGY CODE ###

k=int(input())
ans=1
mod=7%k
mod1=7%k
while mod1!=0:
  mod=(mod*10)%k
  mod1=mod1+mod
  if mod1>=k:
    mod1=mod1%k
  ans+=1
  
print(ans)
    

### FIXED CODE ###

import sys
k=int(input())
d={}
ans=1
mod=7%k
mod1=7%k
d[mod1]=1
ch=0
  
while mod1!=0:
  mod=(mod*10)%k
  mod1=mod1+mod
  if mod1>=k:
    mod1=mod1%k
  if mod1 in d:
    ch+=1
    break
  if mod1 not in d:
    d[mod1]=1
  ans+=1
  
if ch==0:
  print(ans)
else:
  print(-1)
### BUGGY CODE ###

N = int(input())
numbers = [int(n) for n in input().split(' ')]
distances = []
initialIndex = 0
for i in range(0, len(numbers)):
    if i < initialIndex:
        continue
    counter = 0
    for j in range(i, len(numbers)):
        if j == i:
            continue
        if numbers[j - 1] >= numbers[j]:
            counter += 1
        else:
            initialIndex = j
            break
    distances.append(counter)
print(max(distances))

### FIXED CODE ###

N = int(input())
numbers = [int(n) for n in input().split(' ')]
distances = []
if N == 1:
    print(0)
else:
    counter = 0
    for i in range(0, len(numbers)):
        if i == len(numbers) - 1:
            distances.append(counter)
            break
        if numbers[i] >= numbers[i + 1]:
            counter += 1
        else:
            distances.append(counter)
            counter = 0

    print(max(distances))
### BUGGY CODE ###

N, M = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(M)]

ab_list.sort()

start_list = list(filter(lambda x: x[0] == 1, ab_list))

res = False

if M > 1:
    for start in start_list:
        for ab in list(filter(lambda x: x[0] == start[1], ab_list)):
            if ab[1] == N:
                res = True
else:
    for start in start_list:
        if start[1] == N:
            res = True

if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

from heapq import heappush, heappushpop, heappop

N, K = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort()


hq = []
for a, f in zip(A, F):
    heappush(hq, (a * f, f))

c, f = heappop(hq)
while K > 0:
    c += f
    K -= 1
    c, f = heappushpop(hq, (c, f))

print(-c)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse=True)
F.sort()

C = [None] * N
for i, (a, f) in enumerate(zip(A, F)):
    C[i] = (a * f, f)


def solve(x):
    global K, N
    t = 0
    for c, f in C:
        temp = ((c - x) + f - 1) // f
        t += max(0, temp)
        if t > K:
            result = False
            break
    else:
        result = True
    return result


ok = A[0] * F[N - 1]
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)
### BUGGY CODE ###

n = int(input())
p=1
for i in range(1,n+1):
  p *=i
print(p%((10**9) + 7))

### FIXED CODE ###

n = int(input())
p=1
def cal(a,b):
  return a*b%1000000007

for i in range(1,n+1):
  p = cal(p,i)
  
print(p)
### BUGGY CODE ###

from collections import deque
s = deque(input())
q = int(input())
work = deque()
workappendleft = work.appendleft
appendleft=s.appendleft
append=s.append
for i in range(q):
    temp = input().split()
    if temp[0] == "1":
        for el in s:
            workappendleft(el)
        s.clear()
        for el in work:
            append(el)
        work.clear()
    else:
        if temp[1] == "1":
            appendleft(temp[2])
        else:
            append(temp[2])
print("".join(list(s)))

### FIXED CODE ###

from collections import deque
def main():
    s = deque(input())
    q = int(input())
    appendleft=s.appendleft
    append=s.append
    flag = False
    for i in range(q):
        temp = input().split()
        if temp[0] == "1":
            flag = not flag
        else:
            if temp[1] == "1":
                if flag:
                    append(temp[2])
                else:
                    appendleft(temp[2])
            else:
                if flag:
                    appendleft(temp[2])
                else:
                    append(temp[2])
    if flag:
        s.reverse()
    print("".join(list(s)))
if __name__=="__main__":
    main()