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

s = input()

n = int(input())
l = []
for i in range(n):
  l=list(input().split())
  if l[0] == '1':
    s = ''.join(list(reversed(s)))
  else:
    if l[1] =='1':
      s = l[2]+s
    else:
      s = s+l[2]
      
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())

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

base = 1

for i in range(n):
  l=list(input().split())
  if l[0] == '1':
    base = base *-1
  else:
    if l[1] =='1' and base == 1 :
      s.appendleft(l[2])
    elif l[1] =='2' and base == 1 :
      s.append(l[2])
    elif l[1] =='1' and base == -1 :
      s.append(l[2])
    elif l[1] =='2' and base == -1 :
      s.appendleft(l[2])

if base ==-1:
  s=''.join(list(reversed(s)))
      
print("".join(s))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

s = input().rstrip()
q = int(input())

isRev = False

for i in range(q):
    query = list(input().split())
    if len(query) == 1:
        isRev = not isRev
    else:
        if isRev and query[1] == '1':
            s = s + query[2]
        elif query[1] == '1':
            s = query[2] + s
        elif isRev and query[1] == '2':
            s = query[2] + s
        elif query[1] == '2':
            s = s + query[2]
            
if isRev:
    s = s[::-1]
        
print(s)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

s = input().rstrip()
q = int(input())

isRev = False

head = ''

for i in range(q):
    query = list(input().split())
    if len(query) == 1:
        isRev = not isRev
    else:
        if isRev and query[1] == '1':
            s = s + query[2]
        elif query[1] == '1':
            head = head + query[2]
        elif isRev and query[1] == '2':
            head = head + query[2]
        elif query[1] == '2':
            s = s + query[2]
            
if isRev:
    s = s[::-1] + head
else:
    s = head[::-1] + s
        
print(s)
### BUGGY CODE ###

n = int(input())
s = input()
ans = n
for m in range(n+1) :
    r = s[:m].count("#")
    t = s[m:].count(".")
    ans = min(ans, r+t)
print(ans)

### FIXED CODE ###

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

t = s.count(".")
r = 0
ans = t
for m in range(n) :
    if s[m] == "." :
        t -= 1
    else :
        r += 1
    ans = min(ans, t+r)
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(input().split(), np.int32)
S = np.array([A[i] - i for i in range(N)])
T = np.array([-A[i] - i for i in range(N)])
# j > i
# S[j] == T[i]
ans = 0
for j in range(N):
    for i in range(j - 1, -1, -1):
        if S[j] == T[i]:
            ans += 1
print(ans)


### FIXED CODE ###

from _collections import defaultdict
import sys

read = sys.stdin.buffer.read
N = int(input())
A = [int(i) for i in input().split()]
D = defaultdict(int)

for i, a in enumerate(A, 1):
    D[i - a] += 1

ans = 0
for i, a in enumerate(A, 1):
    ans += D[i + a]
print(ans)
### BUGGY CODE ###

S = input()
K = int(input())
val = ''
A = set()
for i,s in enumerate(S):
    val = ''
    for j in range(i,len(S)):
        val += (S[j])
        A.add(val)
A_sort = sorted(list(A))
print(A_sort[K-1])

### FIXED CODE ###

S = input()
K = int(input())
val = ''
A = set()
for i,s in enumerate(S):
    val = ''
    for j in range(i,min(i+5,len(S))):
        val += (S[j])
        A.add(val)
A_sort = sorted(list(A))
print(A_sort[K-1])
### BUGGY CODE ###

N = int(input())
X = input()

dp = [0] * 200001


def popcount(n: int):
    bin_n = bin(n)
    return str(bin_n).count('1')


for i in range(N):
    count = 0
    if X[i] == '1':
        tmp = int(X)
        tmp -= 10 ** (N - i - 1)
    else:
        tmp = int(X)
        tmp += 10 ** (N - i - 1)

    tmp = int(str(tmp), 2)

    while True:
        if tmp == 0:
            print(count)
            break
        else:
            count += 1
            tmp = tmp % popcount(tmp)
            origin = tmp
            if tmp == 0:
                dp[origin] = count
                print(count)
                break
            elif tmp == 1:
                dp[origin] = count + 1
                print(count + 1)
                break
            elif tmp == 2:
                dp[origin] = count + 1
                print(count + 1)
                break
            elif dp[tmp] != 0:
                dp[origin] = count + dp[tmp]
                print(count + dp[tmp])
                break
            else:
                count += 1
                tmp = tmp % popcount(tmp)


### FIXED CODE ###

N = int(input())
S = input()
X = int(S, 2)
pcx = S.count('1')
# ビット反転で1が0になる場合
pc1 = X % (pcx - 1) if pcx > 1 else 0
# ビット反転で0が1になる場合
pc2 = X % (pcx + 1)


def f(j):
    cnt = 0
    while j:
        j %= bin(j).count('1')
        cnt += 1
    return cnt


for i, y in enumerate(S):
    k = N - i - 1
    if y == "0":  # modを分配するときは、分配してからもう１回modを作用させれば良い
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

n, x, y = map(int,input().split())
x -= 1
y -= 1

distance_dict = {}
for k in range(1,n):
    distance_dict[k] = set()

for i in range(n):
    for j in range(i+1,n):
        distance = min(abs(i-j),abs(i-x)+1+abs(j-y),abs(i-y)+1+abs(j-x))
        distance_dict[distance].add((i,j))

for keys,vals in distance_dict.items():
    print(len(vals))


### FIXED CODE ###

n, x, y = map(int,input().split())
x -= 1
y -= 1

distance_l = [0]*(n-1)

for i in range(n):
    for j in range(i+1,n):
        distance = min(abs(i-j),abs(i-x)+1+abs(j-y),abs(i-y)+1+abs(j-x))
        distance_l[distance-1] += 1

for val in distance_l:
    print(val)
### BUGGY CODE ###

k,s = map(int, input().split())
count = 0
for i in range(k+1):
    x = k - i
    for j in range(k+1):
        y = k - j
        for l in range(k+1):
            z = k - l
            ss = x+y+z
            if ss == s:
                count += 1
print(count)

### FIXED CODE ###

k,s = map(int, input().split())
count = 0
for i in range(k+1):
    x = k - i
    for j in range(k+1):
        y = k - j
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

s = input()
n = len(s)
ans = 0
for i in range(len(s) - 4):
  for j in range(i + 4, len(s) + 1):
    if int(s[i : j]) % 2019 == 0:
      ans += 1
      break
print(ans)

### FIXED CODE ###

s = input()[::-1]
current = 0
a = [0] * 2019
a[0] = 1
digit = 1
for i in s:
  current += int(i) * digit
  digit *= 10
  digit %= 2019
  current %= 2019
  a[current] += 1
ans = 0
for i in a:
  ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import bisect

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

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if l[i]<(l[j]+l[k]) and l[j]<(l[i]+l[k]) and l[k]<(l[j]+l[i]):
                ans+=1
print(ans)
#くそでは？

### FIXED CODE ###

# coding: utf-8
# Your code here!
import bisect

N=int(input())
l=list(map(int,input().split()))
l.sort()

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        insert_index = bisect.bisect_left(l,l[i]+l[j])
        ans+=(insert_index-j-1)
        
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
# from time import time

# start = time()

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

# print(time() - start)

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "#"
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)
# print(time() - start)


### FIXED CODE ###

from collections import deque
import sys
# from time import time

# start = time()

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

# print(time() - start)

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "#"
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)
# print(time() - start)
### BUGGY CODE ###

import collections
n=int(input())
a=[]
c=0
for _ in range(n):
    b = input()
    if b not in a:
        a.append(b)
        c+=1
print(c)

### FIXED CODE ###

import collections
n=int(input())
a=[]
for _ in range(n):
    a.append(input())
c = collections.Counter(a)
print(len(c))
### BUGGY CODE ###

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

def profit(values):
    sorted_values = sorted(values)
    minimum = sorted_values[0]
    maximum = sorted_values[-1]
    diff_list = []
    while values != []:
        diff = minimum - maximum
        start = values[0]
        for v in values[1:]:
            tmp_diff = v - start
            if tmp_diff > diff:
                diff = tmp_diff
        diff_list.append(diff)
        values.remove(values[0])
    diff_list.sort(reverse = True)
    return diff_list[0]


print(profit(values))

### FIXED CODE ###

n = int(input())
values = [int(input()) for i in range(n)]

maxv = -999999999
minimum = values[0]

for i in range(1, n):
    if values[i] - minimum > maxv:
        maxv = values[i] - minimum
    if values[i] < minimum:
        minimum = values[i]

print(maxv)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1
for i in sorted(set(A)):
    for j in range(-1, 2):
        ans = max(ans, sum([i + j - 1 <= a <= i + j + 1 for a in A]))
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = 1
for c in C.keys():
    for i in range(-1, 2):
        j = c + i
        ans = max(ans, sum([C[j - 1], C[j], C[j + 1]]))
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

for i in lr:
  cnt = 0
  ss = s[i[0] - 1:i[1]]
  for j in range(len(ss)-1):
    if (ss[j] == 'A') and (ss[j+1] == 'C'):
      cnt += 1
  print(cnt)

### FIXED CODE ###

n,q = map(int,input().split())
s = input() + '0'
lr = [list(map(int,input().split())) for _ in range(q)]
cnt = [0] * (n+1)

for i in range(n):
  if s[i] == 'A' and s[i+1] == 'C':
    cnt[i+1] = cnt[i] + 1
  else:
    cnt[i+1] = cnt[i]
for i in lr:
  print(cnt[i[1]-1] - cnt[i[0]-1])
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
n=[a,b,c]
for i in range(k):
  A=n[1]+n[2]
  B=n[0]+n[2]
  C=n[0]+n[1]
  n[0]=A
  n[1]=B
  n[2]=C
if n[0]-n[1]>10**18:
  print("Unfair")
else:
  print(n[0]-n[1])

### FIXED CODE ###

a,b,c,k=map(int,input().split())
if k%2==0:
  print(a-b)
else:
  print(b-a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
x,y = map(int,input().split())
mod = 10**9+7

def dfs(i,j):
    if i == 0 and j==0:
        return 1
    a = b = 0
    if i-2 >= 0 and j-1 >= 0:
        a = dfs(i-2,j-1)
    if i-1 >= 0 and j-2 >= 0:
        b = dfs(i-1,j-2)
    return (a+b)%mod

print(dfs(y,x))

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9+7
def comb(N,x):
    numerator = 1
    for i in range(N-x+1,N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator * j % mod
    d = pow(denominator,mod-2,mod)
    return numerator * d % mod

if (x+y) % 3 == 0:
    a = (2*y-x) //3
    b = (2*x-y) //3

    if a >= 0 and b >= 0:
        print(comb(a+b,a))
        exit()
print(0)
### BUGGY CODE ###

# given an array of Heights, jump from 1 to N with at most K sized jump to N
# each jump incurs abs(H[j] - H[i]) cost
# minimize cost of jumps from 1 to N
#
import collections

def frog(H, k):
    if k > len(H):
        k = len(H)
    K = collections.deque([0] * (k + 1))
    n = len(H)
    klen = len(K)
    for i in range(n):
        cost = 0
        if i > 0:
            maxjump = min(i, k)
            cost = float("inf")
            for j in range(1, maxjump + 1):
                jcost = abs(H[i] - H[i - j]) + K[klen - j]
                if jcost < cost:
                    cost = jcost
        K.popleft()
        K.append(cost)
    return cost

assert frog([40, 10, 20, 70, 80, 10, 20, 70, 80, 60], 4) == 40
assert frog([10, 10], 100) == 0
assert frog([10, 20, 10], 1) == 20

if __name__ == "__main__":
    import sys
    s = sys.stdin.read()
    N, k, *H = map(int, s.split())
    ans = frog(H, k)
    print(ans)


### FIXED CODE ###

# given an array of Heights, jump from 1 to N with at most K sized jump to N
# each jump incurs abs(H[j] - H[i]) cost
# minimize cost of jumps from 1 to N
#
def frog(H, k):
    if k > len(H):
        k = len(H)
    n = len(H)
    K = [0] * n
    inf = float("inf")
    for i in range(n):
        cost = 0
        if i > 0:
            maxjump = i if i < k else k # min(i, k)
            cost = inf
            hi = H[i]
            # jump source going backwards from i-1 (smallest 1 sized jump) to i - maxjumps
            for j in range(i - 1, i - maxjump - 1, -1):
                jcost = abs(hi - H[j]) + K[j]
                if jcost < cost:
                    cost = jcost
        K[i] = cost
    return cost

assert frog([40, 10, 20, 70, 80, 10, 20, 70, 80, 60], 4) == 40
assert frog([10, 10], 100) == 0
assert frog([10, 20, 10], 1) == 20

if __name__ == "__main__":
    import sys
    s = sys.stdin.read()
    N, k, *H = map(int, s.split())
    ans = frog(H, k)
    print(ans)
### BUGGY CODE ###

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

def binxor(x, y):
    x = x.lstrip('0b')
    y = y.lstrip('0b')
    n = max(len(x), len(y))
    x = x.zfill(n)
    y = y.zfill(n)
    z = ''.join(list(map(str, [int(xx)^int(yy) for xx, yy in zip(x, y)])))
    return '0b0'+z

A10sum = [0]
Abinsum = [bin(0)]
for i in range(1, N+1):
    A10sum.append(A10sum[i-1]+A[i-1])
    Abinsum.append(binxor(Abinsum[i-1], bin(A[i-1])))
# print(f'10sum : {A10sum}')
# print(f'binsum : {Abinsum}')

count = 0
for l in range(1, N+1):
    for r in range(l, N+1):
        if(A10sum[r]-A10sum[l-1] == int(binxor(Abinsum[r], Abinsum[l-1]), 2)):
            count+=1
print(count)


### FIXED CODE ###

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

r = 0
ans = 0
sum_a = 0
for l in range(n):
    while r < n and sum_a&a[r] == 0:
        sum_a += a[r]
        ans += r-l+1
        r += 1
    sum_a -= a[l]
print(ans)
### BUGGY CODE ###

from functools import cmp_to_key
import heapq


def func(a, b):
    if a[0] * b[1] == a[1] * b[0]:
        return 0
    elif a[0] * b[1] > a[1] * b[0]:
        return - 1
    else:
        return 1


n, k = map(int, input().split())
c = cmp_to_key(func)
hq = list(map(lambda x: c((int(x), 1)), input().split()))
heapq.heapify(hq)
for _ in range(k):
    t = heapq.heappop(hq).obj
    heapq.heappush(hq, c((t[0], t[1] + 1)))
t = heapq.heappop(hq).obj
print((t[0] - 1) // t[1] + 1)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l, r = 0, 10 ** 9 + 10
while r - l > 1:
    res = 0
    m = (l + r) // 2
    for x in a:
        res += (x - 1) // m
    if res <= k:
        r = m
    else:
        l = m
print(r)
### BUGGY CODE ###

from collections import defaultdict


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


def divisor(n):
    div_list = set()
    limit = int(n**0.5) + 1
    for div in range(1, limit):
        if n % div == 0:
            div2 = n // div
            div_list.add(div)
            div_list.add(div2)
    
    return list(div_list)


        
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

    
ans = n
for a in A:
    A_dict[a] -= 1
    divs = divisor(a)
    for div in divs:
        if A_dict[div] >= 1:
            ans -= 1
            break
            
    A_dict[a] += 1


print(ans)

### FIXED CODE ###

import numpy as np
from collections import Counter


n = int(input())
A = list(map(int, input().split()))
A.sort()
is_divisible = np.zeros(10**6+1, dtype=np.int64)


def update(num):
    nums = np.arange(num, 10**6+1, num)
    is_divisible[nums] = True

counter = Counter(A)
ans = 0
for a, count in counter.items():
    if count == 1 and not is_divisible[a]:
        ans += 1
        
    update(a)

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

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

b = list(set(a))

for i in b:
    if a.count(i) % 2 == 0:
        while i in a:
            a.remove(i)
    else:
        None
        
print(len(list(set(a))))

### FIXED CODE ###

n = int(input())

nlll = {}
    
for i in range(n):
    aaa = int(input())
    if aaa in nlll:
        del nlll[aaa]
    else:
        nlll.update({aaa:1})

sums = 0
for i in nlll.values():
    sums = sums + i
print(sums)
### BUGGY CODE ###

N, K = map(int, input().split())
L = [0] * K
R = [0] * K
S = set()
for k in range(K):
    L[k],R[k] = map(int,input().split())
for k in range(K):
    for n in range(L[k], R[k] + 1):
        S.add(n)
dp = [0] * (N+1)
dp[1] = 1
S = sorted(S)
for i in range(1,N+1):
    for s in S:
        if i-s <= 0:
            break
        dp[i] += dp[i-s]
    dp[i] %= 998244353
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
    dp_sums[i] %= 998244353
print(dp[N])
### BUGGY CODE ###

X = int(input())
A = [i for i in range(0, 10000)]
B = [-i for i in range(0, 10000)]
res = []
for i in range(len(A)):
  a = A[i]
  for j in range(len(B)):
    b = B[j]
    cal = a ** 5 - b ** 5
    if cal == X:
      print(a, b)
      exit()

### FIXED CODE ###

X = int(input())
A = [(i**5) for i in range(0, 1000)]
res = []
for i in range(len(A)):
  a = A[i]
  for j in range(len(A)):
    b = -A[j]
    cal = a - b
    cal2 = a + b
    if cal == X:
      print(i, -j)
      exit()
    elif cal2 == X:
      print(i, j)
      exit()
### BUGGY CODE ###


import itertools
import numpy as np

tmp = input()
N,K = tmp.split()
que = input()
try:
    N = int(N)
except:
    pass
try:
    K = int(K)
except:
    pass



que = [int(x) for x in que.split()]

#print(que)
"""
tmp = []
for x in que:
    for xx in range(K):
        tmp.append(x)
que = tmp
"""
min_val = 999999999

for x in itertools.combinations(que, K):
    tmp = np.sum(x)
    if tmp < min_val:
        min_val = tmp

print(min_val)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.

Author : Takeshi Saga

"""

import itertools
import numpy as np

tmp = input()
#tmp = "5 3"
N,K = tmp.split()
que = input()
#que = "50 100 80 120 80"
try:
    N = int(N)
except:
    pass
try:
    K = int(K)
except:
    pass



que = [int(x) for x in que.split()]

#print(que)
"""
tmp = []
for x in que:
    for xx in range(K):
        tmp.append(x)
que = tmp
"""
min_val = 999999999

que = sorted(que)

#for x in itertools.combinations(que, K):

x = [que[i] for i in range(K)]
min_val = np.sum(x)

print(min_val)
### BUGGY CODE ###

def solve(string):
    n, m, *a = map(int, string.split())
    for i in range(1, n):
        a[i] += a[i - 1]
    a=[0]+a
    ans = 0
    for i in range(1,n+1):
        for j in range(i):
            if (a[i]-a[j])%m==0:
                ans+=1
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


### FIXED CODE ###

from collections import defaultdict


def solve(string):
    n, m, *a = map(int, string.split())
    for i in range(1, n):
        a[i] += a[i - 1]

    d = defaultdict(int)
    for i in range(n):
        d[a[i] % m] += 1
    ans = d[0]
    for v in d.values():
        ans += v * (v - 1) // 2
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(a[i])
    b=list(reversed(b))


for j in b:
    print(j,end=' ')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a1=a[0:1]+a[1::2]
a2=a[2::2]

if n % 2 == 1 :
    a2=list(reversed(a2))
    a=a2+a1

elif n % 2 == 0 :
    a1=list(reversed(a1))
    a=a1+a2

for j in a:
    print(j,end=' ')
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a = sorted(a)

l = []
for i in range(m):
  b, c = map(int, input().split())
  x = [c]*b
  l += x
  
a = a+l
a = sorted(a)
a = a[-n:]
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a = sorted(a)

l = []
for i in range(m):
  l.append(list(map(int, input().split())))
  
l = sorted(l, reverse=True, key=lambda x: x[1])

b = []
for _ in range(n):
  b.append(l[0][1])
  l[0][0] -= 1
  if l[0][0] == 0:
    l.pop(0)
  if l == []:
    break

for i in range(len(b)):
  if a[i] < b[i]:
    a[i] = b[i]
  else:
    break
    
print(sum(a))
### BUGGY CODE ###


s = input()
t = input()

dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        if (s[i-1] == t[j-1]) :
            dp[i][j] = dp[i-1][j-1] + 1
        else :
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

kotae = []

while(i > 0 and j > 0):
    if(dp[i][j] == dp[i-1][j]):
        i -= 1
    elif(dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        i -= 1
        j -= 1
        kotae.append(s[i])

kotae.reverse()
kotae = "".join(kotae)
print(kotae)

### FIXED CODE ###


s = input()
t = input()

dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        if (s[i-1] == t[j-1]) :
            dp[i][j] = dp[i-1][j-1] + 1
        else :
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

kotae = []

while(i > 0 and j > 0):
    if(dp[i][j] == dp[i-1][j]):
        i -= 1
    elif(dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        i -= 1
        j -= 1
        kotae.append(s[i])

kotae.reverse()
kotae = "".join(kotae)
print(kotae)