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

s = input()
q = int(input())

count = 0
for i in range(q):
    query = input()
    if query == "1":
        count += 1
    else:
        t,f,c = query.split()
        if f == "1":
            if count % 2 == 0:
                s = c + s
            else:
                s = s + c
        else:
            if count % 2 == 0:
                s = s + c
            else:
                s = c + s
if count % 2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()
q = int(input())

from collections import deque
s = deque(s)
count = 0
for i in range(q):
    query = input()
    if query == "1":
        count += 1
    else:
        t,f,c = query.split()
        if f == "1":
            if count % 2 == 0:
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if count % 2 == 0:
                s.append(c)
            else:
                s.appendleft(c)
s = "".join(s)
if count % 2 == 0:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

r,g,b,n=map(int,input().split())

count=0
for ri in range(int(n/r)+1):
    for gi in range(int(n/g)+1):
        if (n-ri*r-gi*g)%b==0 and (n-ri*r-gi*g)/b>=0:
            count+=1
        elif (n-ri*r-gi*g)<0:
            break

print(count)

### FIXED CODE ###

r,g,b,n=map(int,input().split())

count=0
for ri in range(int(n/r)+1):
    for gi in range(int((n-ri*r)/g)+1):
        sumc=n-ri*r-gi*g
        if sumc<0:
            break
        if sumc%b==0:
            count+=1

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

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

m = 10**9
def score(point = 0, n = 0, now=-1, done=[]):
    global m
    if m <= n: return
    elif point >= g:
        if m > n: m = n
    elif point+100*(now+1)*P[now] >= g:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    else:
        done.append(now)
        if now == -1:
            for i in range(d):
                score(point, n, i, done[:])
        elif m <= n+P[now]: return
        else:
            for i in range(d):
                if not d-1-i in done:
                    score(point+P[now]*100*(now+1) + C[now], n + P[now], d-1-i, done[:])

score()
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

import collections
N = int(input())
S = [collections.Counter(list(input())) for _ in range(0, N)]
result = 0
for i, s in enumerate(S):
    for j in range(i + 1, len(S)):
        if s == S[j]:
            result += 1
print(result)


### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(0, N)]
d = {}
result = 0
for s in S:
    if s in d.keys():
        result += d[s]
        d[s] += 1
    else:
        d[s] = 1
print(result)
### BUGGY CODE ###

n,p = map(int,input().split())
s = input()
ans = 0

for i in range(n):
  for j in range(i,n):
    if int(s[i:j+1])%p == 0:
      ans += 1
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sum = 0
  for i in range(n):
    sum = (sum+s[n-i-1]*pow(10,i,p))%p
    cnt[sum] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)
### BUGGY CODE ###

N=int(input())
P=1
for i in range(N):
   P=P*(i+1)
M=P%(10**9+7)
print(M)

### FIXED CODE ###

N=int(input())
P=1
for i in range(N):
   P=P*(i+1)
   P=P%(10**9+7)

print(P)
### BUGGY CODE ###

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

dp = [0] * n
dp[0] = 0

for i in range(min(k, n - 1)):
    dp[i+1] = abs(h[i + 1] - h[0])

for i in range(k, n - 1):
    dp[i+1] = min([dp[i - j] + abs(h[i - j] - h[i + 1]) for j in range(k)])

print(dp[n-1])


### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
    dp[i] = min([dp[j] + abs(h[j] - h[i]) for j in range(max(0, i-k), i)])

print(dp[-1])
### BUGGY CODE ###

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

print((1/2)*(max([sum(Pi[i:i+K]) for i in range(N-K+1)]) + K))

### FIXED CODE ###

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

Sim = [0]
for i in range(0,N):
  Sim.append(Sim[i]+Pi[i])
MAX = max(Sim[i+K] - Sim[i] for i in range(N+1-K))

print((MAX+K)/2)
### BUGGY CODE ###

n = int(input())
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
s = input()
for i in range(n):
    string = z_algo(s[i:])
    for j in range(1,len(string)):
        if j - i  + string[j] < n:
            ans = max(ans, string[j])
print(ans)

### FIXED CODE ###

n = int(input())
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
s = input()
for i in range(n):
    string = z_algo(s[i:])
    for j in range(len(string)):
        if j  >= string[j]:
            ans = max(ans, string[j])
print(ans)
### BUGGY CODE ###

import heapq

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)


AB = []

for i in range(x):
    for j in range(y):
        AB.append(A[i]+B[j])

AB = sorted(AB, reverse=True)
AB = AB[:min(k, x*y)]
# print(AB)

ABC = []
for l in range(min(k, x*y)):
    for m in range(z):
        ABC.append(AB[l] + C[m])

ABC = sorted(ABC, reverse=True)
for i in range(k):
    print(ABC[i])



# ------------優先度付きキュー----------

# hq = []
# heapq.heapify(hq)
# i, j, l = 0, 0, 0

# heapq.heappush(hq, [(A[i]+B[j]+C[l])*-1, i, j, l])
# Used = []

# for i in range(k):
#     now = heapq.heappop(hq)
#     print(now[0]*-1)
#     i = now[1]
#     j = now[2]
#     l = now[3]

#     if i >= x-1:
#         pass
#     elif [(A[i+1]+B[j]+C[l])*-1, i+1, j, l] not in Used:
#         Used.append([(A[i+1]+B[j]+C[l])*-1, i+1, j, l])
#         heapq.heappush(hq, [(A[i+1]+B[j]+C[l])*-1, i+1, j, l])
        
#     if j >= y-1:
#         pass
#     elif [(A[i]+B[j+1]+C[l])*-1, i, j+1, l] not in Used:
#         Used.append([(A[i]+B[j+1]+C[l])*-1, i, j+1, l])
#         heapq.heappush(hq, [(A[i]+B[j+1]+C[l])*-1, i, j+1, l])
        
#     if l >= z-1:
#         pass
#     elif [(A[i]+B[j]+C[l+1])*-1, i, j, l+1] not in Used:
#         Used.append([(A[i]+B[j]+C[l+1])*-1, i, j, l+1])
#         heapq.heappush(hq, [(A[i]+B[j]+C[l+1])*-1, i, j, l+1])
        
#     # print(hq)

### FIXED CODE ###

import heapq

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)

hq = []
heapq.heapify(hq)
i, j, l = 0, 0, 0

heapq.heappush(hq, [(A[i]+B[j]+C[l])*-1, i, j, l])
Used = []

for i in range(k):
    now = heapq.heappop(hq)
    print(now[0]*-1)
    i = now[1]
    j = now[2]
    l = now[3]

    if i >= x-1:
        pass
    elif [(A[i+1]+B[j]+C[l])*-1, i+1, j, l] not in Used:
        Used.append([(A[i+1]+B[j]+C[l])*-1, i+1, j, l])
        heapq.heappush(hq, [(A[i+1]+B[j]+C[l])*-1, i+1, j, l])
        
    if j >= y-1:
        pass
    elif [(A[i]+B[j+1]+C[l])*-1, i, j+1, l] not in Used:
        Used.append([(A[i]+B[j+1]+C[l])*-1, i, j+1, l])
        heapq.heappush(hq, [(A[i]+B[j+1]+C[l])*-1, i, j+1, l])
        
    if l >= z-1:
        pass
    elif [(A[i]+B[j]+C[l+1])*-1, i, j, l+1] not in Used:
        Used.append([(A[i]+B[j]+C[l+1])*-1, i, j, l+1])
        heapq.heappush(hq, [(A[i]+B[j]+C[l+1])*-1, i, j, l+1])
        
    # print(hq)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import itertools
from heapq import heappushpop, heappush

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

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(a,n)]
    m = n
    while m:
        bit = m & (-m)
        arr += B[n - bit]
        m -= bit
    se = set(arr)
    B.append(sorted(se, reverse=True)[:2])

answer = [0]
for (x,i),(y,j) in B[1:]:
    z = answer[-1]
    if z < x + y:
        z = x + y
    answer.append(z)
print('\n'.join(map(str,answer[1:])))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappushpop

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

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(0,0),(a,n)]
    m = n
    while m:
        bit = m & (-m)
        (x,i),(y,j) = B[n-bit]
        if (x,i) != arr[-1]:
            heappushpop(arr,(x,i))
        if (y,j) != arr[-1]:
            heappushpop(arr,(y,j))
        m -= bit
    B.append(arr)

answer = [0]
for (x,i),(y,j) in B[1:]:
    z = answer[-1]
    if z < x + y:
        z = x + y
    answer.append(z)
print('\n'.join(map(str,answer[1:])))
### BUGGY CODE ###

N=int(input())
List = list(map(int, input().split()))
AList = []

i=1
while i<=N:
    AList.append((List.index(i))+1)
    
    i+=1
    
print(*AList)




### FIXED CODE ###

N=int(input())
List = list(map(int, input().split()))
AList = [0]*N
for i in range(0,N):
    S=List[i]
    AList[S-1]=i+1
    
print(*AList)
### BUGGY CODE ###

N = int(input())

mod_list = []
if N % 2:
    i = 1
    while True:
        num = (7*((10**i)-1)//9) % N
        # print(num)
        if num == 0:
            print(i)
            break
        if num in mod_list:
            print(-1)
            break
        else:
            mod_list.append(num)
            i += 1

else:
    print(-1)


### FIXED CODE ###

N = int(input())
if N % 7:
    L = 9*N
else:
    L = 9*N//7
num = 1
if L % 2 and L % 5:
    i = 1
    while i <= L:
        num = (num*10) % L
        if num == 1:
            print(i)
            break

        else:

            i += 1

else:
    print(-1)
### BUGGY CODE ###

def A():
    w = ['Sunny', 'Cloudy', 'Rainy']
    today = input()
    index = w.index(today)
    if index == 2:
        index = -1
    print(w[index+1])

def B():
    odd = 'RUD'
    even = 'LUD'

    s = input()
    for i in range(len(s)):
        if (i+1)%2 == 0:
            if s[i] not in even:
                print('No')
                return
        else:
            if s[i] not in odd:
                print('No')
                return
        
    print('Yes')

def C():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    K = temp[1]
    Q = temp[2]
    points = {}
    for i in range(N):
        points[i] = K

    for i in range(Q):
        num = int(input())
        for j in range(N):
            if j+1 != num:
                points[j] -= 1

    for i in points.keys():
        if points[i] > 0:
            print('Yes')
        else:
            print('No')
    
C()


### FIXED CODE ###

def A():
    w = ['Sunny', 'Cloudy', 'Rainy']
    today = input()
    index = w.index(today)
    if index == 2:
        index = -1
    print(w[index+1])

def B():
    odd = 'RUD'
    even = 'LUD'

    s = input()
    for i in range(len(s)):
        if (i+1)%2 == 0:
            if s[i] not in even:
                print('No')
                return
        else:
            if s[i] not in odd:
                print('No')
                return
        
    print('Yes')

def C():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    K = temp[1]
    Q = temp[2]
    points = {}

    for i in range(N):
        points[i] = 0

    for i in range(Q):
        num = int(input())
        points[num-1] += 1

    for i in points.keys():
        if K - (Q - points[i]) > 0:
            print('Yes')
        else:
            print('No')
    
C()
### BUGGY CODE ###

n = int(input())
s = input()
ans = []
count = 0
for i in range(n):
	for j in range(i+1,n):
		if s[i] == s[j]:
			i_dash = i
			j_dash = j
			while True:
				if i_dash == j or j_dash == n:
					break
				elif s[i_dash] == s[j_dash]:
					count+=1
				else:
					break
				i_dash += 1
				j_dash += 1
			ans.append(count)
			count = 0

if not ans:
	print(0)
else:
	print(max(ans))


### FIXED CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

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

n = int(input())
L = []

for i in range(n):
    com = input()
    if com == "deleteFirst":
        del L[0]
    elif com == "deleteLast":
        del L[len(L)-1]
    else:
        c = com.split()
        if c[0] == "insert":
            L.insert(0, int(c[1]))
        elif c[0] == "delete":
            for i in range(len(L)):
                if L[i] == int(c[1]):
                    del L[i]
                    break
    #print(L)
        
for i in range(len(L)):
    if i == len(L)-1:
        print(L[i])
    else:
        print(L[i], end=' ')


### FIXED CODE ###

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    else:
        if com[6] == 'F':
            L.popleft()
        elif com[6] == 'L':
            L.pop()
        else:
            C = com.split()
            x = int(C[1])
            try:
                L.remove(x)
            except:
                pass

print(*L)
### BUGGY CODE ###

from collections import deque

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
con = [set() for _ in range(N+1)]
res = {}

for ab in AB:
    con[ab[0]].add(ab[1])
    con[ab[1]].add(ab[0])
    res[tuple(ab)] = 0

max_len = 0
for i, c in enumerate(con):
    if max_len <= len(c):
        max_len = len(c)
        max_ind = i

colors = [set() for i in range(N+1)]
all_colors = set([i for i in range(1, max_len+2)])
q = deque()
q.append(max_ind)
node_state = [0]*(N+1)

while q != deque():
    v = q.pop()
    node_state[v] = 1
    for next_v in con[v]:
        if node_state[next_v] == 0:
            q.appendleft(next_v)
        if v < next_v:
            va = v
            vb = next_v
        else:
            va = next_v
            vb = v
        if res[(va, vb)] == 0:
            color = list(all_colors.difference(colors[va].union(colors[vb])))[0]
            res[(va, vb)] = color
            colors[va].add(color)
            colors[vb].add(color)

print(max_len)
for i in range(N-1):
    print(res[tuple(AB[i])])

### FIXED CODE ###

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
sortedAB = sorted(AB)
con = {i: [] for i in range(1, N+1)}
color = [0] * (N + 1)
for a, b in sortedAB:
    con[a].append(b)

for i in range(1, N + 1):
    now_c = 1
    for c in con[i]:
        if color[i] == now_c:
            now_c += 1
        color[c] = now_c
        now_c += 1

print(max(color))
for i in range(N-1):
    print(color[AB[i][1]])

a = 0
### BUGGY CODE ###

import numpy as np

N, K = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([np.inf] * N)
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
    for j in range(0,K+1):
        if i - j >= 0:
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(int(dp[N-1]))

### FIXED CODE ###

import numpy as np

N, K = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([np.inf] * N)
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
        if i - K >= 0:
            dp[i] = min(dp[i-K:i]+abs(h[i]-h[i-K:i]))
        else:
            dp[i] = min(dp[0:i]+abs(h[i]-h[0:i]))
print(int(dp[N-1]))
### BUGGY CODE ###

def main():
    n,a,b,k=map(int,input().split())
    fact=[1]
    mod=998244353
    for i in range(1,n+1):fact.append(fact[-1]*i%mod)
    def inv_n(n):return pow(n,mod-2,mod)
    def nCr(n,r):return inv_n(fact[n-r]*fact[r]%mod)*fact[n]%mod
    ans=0
    ans_list=[]
    for i in range(n+1):
        j=(k-a*i)//b
        if i*a+j*b==k:
            if 0<=j<=n:
                ans_list.append([i,j])
    for p,q in ans_list:
        ans=(ans+nCr(n,p)*nCr(n,q))%mod
    print(ans)
main()

### FIXED CODE ###

def main():
    n,a,b,k=map(int,input().split())
    fact=[1]
    mod=998244353
    for i in range(1,n+1):fact.append(fact[-1]*i%mod)
    def inv_n(n):return pow(n,mod-2,mod)
    def nCr(n,r):return inv_n(fact[n-r]*fact[r]%mod)*fact[n]%mod
    ans=0
    ans_list=[]
    for i in range(n+1):
        j=(k-a*i)//b
        if i*a+j*b==k:
            if 0<=j<=n:
                ans_list.append([i,j])
    for p,q in ans_list:
        ans=(ans+nCr(n,p)*nCr(n,q))%mod
    print(ans)
main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[[[0]*(s+1) for _ in range(n+1)] for _ in range(n+1)]
  dp[0][0][0]=1
  for i in range(1,n+1):
    val=arr[i-1]
    for j in range(i,-1,-1):
      for k in range(s,-1,-1):
        dp[i][j][k]=dp[i-1][j][k]
        if k-val>=0 and dp[i-1][j-1][k-val]!=0:
          dp[i][j][k]+=dp[i-1][j-1][k-val]
  ans=0
  for i in range(1,n+1):
    ans+=dp[n][i][s]*pow(2,n-i,mod)
    ans%=mod
  print(ans)
calc()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[s]%mod)
calc()
### BUGGY CODE ###

import math
N=int(input())
xyzmax=int(math.sqrt(N))

for n in range(1,N+1):
    ans4n=0
    xmax=int(math.sqrt(n))
    for x in range(1,xmax+1):
        ymax=xmax+1-x
        for y in range(1,ymax+1):    
            zmax=ymax+1-y
            for z in range(1,zmax+1):
                if n==(x+y+z)**2-(x*y+y*z+z*x):
                    ans4n+=1

    print(ans4n)


### FIXED CODE ###

import math
N=int(input())
ans=[0]*(N+1)
tempn=0
xmax=int(math.sqrt(N)+1)
for x in range(1,xmax+1):
    ymax=xmax-x
    for y in range(1,xmax+1):    
        zmax=ymax-y
        for z in range(1,xmax+1):
            tempn=((x+y+z)**2-(x*y+y*z+z*x))
            if tempn <= N:
                ans[tempn]+=1
for i in range(1,(N+1)):
    print(ans[i])
### BUGGY CODE ###

import queue
a,b,c = map(int,input().split())
q = queue.LifoQueue()
for i in range(1,100):
  if(a%i == 0 and b%i == 0):
    q.put(i)
if c != 1:
  for i in range(c-1):
    q.get()
print(q.get())

### FIXED CODE ###

a,b,c = map(int,input().split())
if (a*c <= b):
  print(c)
else:
  print(int(b/a))
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from array import array
    from random import sample
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in sample(t[:n],n):
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted(z)[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

B = []
for _ in range(M):
    b, c = map(int, input().split())
    B += [c] * b
    
B.sort(reverse = True)

for i in range(min(N, len(B))):
    A[i] = max(A[i], B[i])
    
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])
C = sorted([[int(i) for i in input().split()] for i in range(M)], reverse = True, 
           key = lambda x: x[1])

cnt = 0
B = []
for i in range(M):
    if cnt > N:
        break
    B += [C[i][1]] * C[i][0]
    cnt += C[i][0]
    
B.sort(reverse = True)

x = min(N, len(B))

for i in range(x):
    A[i] = max(A[i], B[i])
    
print(sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from fractions import gcd


def lcd(x, y):
    g = gcd(x, y)
    return x * y // g


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

l = 1
for e in a:
    l = lcd(l, e)

ans = 0
for e in a:
    ans += l // e
    ans %= mod

print(ans)



### FIXED CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

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

n, k = map(int,input().split())
a = list(map(int,input().split()))
tmp = list(map(lambda x:x+n,a))
a = a + tmp
l = len(a)

b=[0]*(l-1)
for i in range(l-1):
  b[i] = a[i+1]-a[i]

ans = 10**9
for j in range(l-k+1):
  ans = min(ans,sum(b[j:j+k-1]))
print(ans)


### FIXED CODE ###

k,n=list(map(int,input().split()))
A=list(map(int,input().split()))
l=[]
for i in range(n-1):
  l.append(A[i+1]-A[i])
l.append(k-A[-1]+A[0])
print(sum(l)-max(l))