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

S = input()
Q = int(input())

for i in range(Q):
    q = input()
    if q == '1':
        S = S[::-1]
    else:
        _, f, c = q.split()
        if f == '1':
            S = c + S
        else:
            S = S + c
print(S)

### FIXED CODE ###

S = input()
Q = int(input())

prefix = ''
surfix = ''
cnt_reverse = 0

for i in range(Q):
    q = input()
    if q == '1':
        cnt_reverse += 1
    else:
        _, f, c = q.split()
        if (f=='1' and cnt_reverse%2==0):
            prefix = c + prefix
        elif (f=='2' and cnt_reverse%2==1):
            prefix = c + prefix
        elif (f=='1' and cnt_reverse%2==0):
            surfix = surfix + c
        else:
            surfix = surfix + c
if cnt_reverse % 2 == 0:
    S = prefix + S + surfix
else:
    S = surfix[::-1] + S[::-1] + prefix[::-1]
print(S)
### BUGGY CODE ###

H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  for a in range(len(q)-1):
    p.append(S[q[a]:q[a+1]:,:])
  
  t_a = len(q)-2
  l = [0]*len(p)
  judge = False
  for w in range(W):
    for x,a in enumerate(p):
      y = np.sum(a[:,w])
      if y>K:
        judge = True
        break
      else:
        l[x]+=y
        if l[x]>K:
          t_a+=1
          l = [0]*len(p)
          for z,b in enumerate(p):
            l[z] = np.sum(b[:,w])
          break
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

s = input()
t = input()
alp =list("abcdefghijklmnopqrstuvwxyz")
sl = [0] * 26
tl = [0] * 26
for i in s:
    for j in range(26):
        sl[j] = s.count(alp[j])
for i in t:
    for j in range(26):
        tl[j] = t.count(alp[j])
sl.sort()
tl.sort()
if(sl == tl):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
t = input()
alp =list("abcdefghijklmnopqrstuvwxyz")
sl = [0] * 26
tl = [0] * 26
for j in range(26):
        sl[j] = s.count(alp[j])
for j in range(26):
        tl[j] = t.count(alp[j])
sl.sort()
tl.sort()
if(sl == tl):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp =[0,1] + [0] * n
m = 10**9+7
for i in range(2,n+2):
    if i-1 not in a:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= m
    if dp[i-1] == 0 and dp[i-2] == 0:
        print(0)
        exit()
print(dp[-1])

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp =[0,1] + [0] * n
m = 10**9+7
for i in a:
    dp[i+1] = -1
for i in range(2,n+2):
    if dp[i] == 0:
        dp[i] = max(0,dp[i-1]) + max(0,dp[i-2])
        dp[i] %= m
    if dp[i-1] == 0 and dp[i-2] == 0:
        print(0)
        exit()
print(dp[-1])
### BUGGY CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
for i in range(len(a)):
    m+=a[i]
    if len(s)!=0:
        mins=min(s)
    s.append(abs(sum(a)-m*2))
    if len(s)>1 and mins<s[i]:
        break
print(min(s))


### FIXED CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
suma=sum(a)
for i in range(len(a)):
    m+=a[i]
    s.append(abs(suma-m*2))
print(min(s))
### BUGGY CODE ###

from collections import deque
import bisect
n,m,k = map(int, input().split())
a = deque(map(int, input().split()))
b = deque(map(int, input().split()))
ans = 0
a.appendleft(0)
b.appendleft(0)

for i in range(1,n+1):
    a[i]+=a[i-1]
for i in range(1,m+1):
    b[i]+=b[i-1]

for i in range(n+1):
    now = k-a[i]
    if now<0:
        continue
    idx = bisect.bisect_right(b,now)
    ans = max(ans,idx-1+i)

print(ans)

### FIXED CODE ###

from collections import deque
import bisect
n,m,k = map(int, input().split())
a = [0]
b = [0]
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))
# a1 = [1000000]*200000
# b1 = [1000000]*200000
ans = 0
a = a + a1
b = b + b1

for i in range(1,n+1):
    a[i]+=a[i-1]
for i in range(1,m+1):
    b[i]+=b[i-1]

for i in range(n+1):
    now = k-a[i]
    if now<0:
        break
    idx = bisect.bisect_right(b,now)
    ans = max(ans,idx-1+i)

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

# coding: utf-8
a = int(input())
b = list(map(int,input().split()))

n = 1
m = 1

aa = a/2

if a%2 == 1:
    aa = (aa*2+1)//2

for i in range(int(aa)):
  n = n * b[i]
  
for i in range(int(aa),a):
    m *= b[i]

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

### FIXED CODE ###

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

c = 0
d = 0

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()

for i in b:
  n *= i
  if n > 10**18:
    print(-1)
    exit()
print(n)
### BUGGY CODE ###

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

for l,r in LR:
    tmp=S[l-1:r]
    ans=0
    for i in range(len(tmp)-1):
        #print(tmp, tmp[i:i+2])
        if tmp[i:i+2]=='AC':
            ans+=1
    print(ans)

### FIXED CODE ###

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

F=[0]*len(S)
for i in range(N-1):
    F[i+1]+=F[i]+(1 if S[i:i+2]=='AC' else 0)
    #print(i,F,S[i:i+2])
for l,r in LR:
    print(F[r-1]-F[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


dfs(0, -1)
print(*counter)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


dfs(0, -1)
print(*counter)
### BUGGY CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    goukei=0
    l=[0]
    i=0
    x.sort()
    a=0
    b=0
    while i<m-1:
        a=x[i]
        b=x[i+1]
        goukei+=b-a
        l.append(b-a)
        i+=1
    for v in range(n-1):
        goukei-=max(l)
        l.remove(max(l))
    print(goukei)

### FIXED CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    x.sort()
    goukei=0
    l=[0]
    for i in range(m-1):
        goukei+=x[i+1]-x[i]
        l.append(x[i+1]-x[i])
    i=0
    l.sort()
    for i in range(n-1):
        goukei-=l[-1-i]
    print(goukei)
### BUGGY CODE ###

S = input()
n = 0
import re
re.sub('BB+',"BB",S)
re.sub("WW+",'WW',S)

while 'BW' in S:
    n += S.count('BW')
    S = S.replace('BW','WB')
print(n)

### FIXED CODE ###

S = input()
n = 0
k = 0
m = len(S)
for i in range(m):
    if S[i] == 'B':
        n += m - (i+1) -k
        k += 1
print(n)
### BUGGY CODE ###

import scipy.misc as scm

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

now = 0
ans = [0] * 2
for i in range(n):
    for j in range(i + 1, n):
        new = scm.comb(a[j], a[i])
        if new > now:
            ans[0] = a[i]
            ans[1] = a[j]
            now = new
print(ans[1], ans[0])

### FIXED CODE ###

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

a.sort()
a_max = a.pop(-1)
r = 0
for i in range(n-1):
    if abs((a_max/2) - a[i]) < abs((a_max/2) - r):
        r = a[i]
print(a_max, r)
### BUGGY CODE ###

from itertools import accumulate

n, m, k = map(int, input().split())
(*a,) = accumulate(map(int, input().split()))
(*b,) = accumulate(map(int, input().split()))
a = (0,) + tuple(i for i in a if i <= k)
b = (0,) + tuple(i for i in b if i <= k)
ans = 0
for i in range(len(a)):
    tmp = k - a[i]
    for j in range(len(b) - 1, -1, -1):
        if b[j] <= tmp:
            ans = max(ans, i + j)
            break
print(ans)

### FIXED CODE ###

from itertools import accumulate
from bisect import bisect

n, m, k = map(int, input().split())
(*a,) = accumulate(map(int, input().split()))
(*b,) = accumulate(map(int, input().split()))
a = (0,) + tuple(i for i in a if i <= k)
b = tuple(i for i in b if i <= k)
print(max(i + bisect(b, k - a[i]) for i in range(len(a))))
### BUGGY CODE ###

n,m=map(int,input().split())
H=list(map(int,input().split()))
A=[0]*m
B=[0]*m
for i in range(m):
    a,b=map(int,input().split())
    A[i]+=a
    B[i]+=b
for i in range(m):
    if H[A[i]-1]>H[B[i]-1]:
        A[i],B[i]=B[i],A[i]
C=list(A)
for i in range(m):
    if H[A[i]-1]==H[B[i]-1]:
        C.append(B[i])
S=n
for i in range(1,n+1):
    if i in C:
        S-=1
print(S)


### FIXED CODE ###

n, m = map(int, input().split())
H = list(map(int, input().split()))
bridge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    bridge[a - 1].append(b - 1)
    bridge[b - 1].append(a - 1)
s = 0
#print(bridge)
for i in range(len(bridge)):
    if not(bridge[i]):
        s += 1
    elif H[i] > max([H[j] for j in bridge[i]]):
        s += 1
print(s)
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
b = sorted(a)
d = []
for i in range (len(a)):
  c = a.index(b[i])
  print(c+1)
  

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
enumerate(a,1)
b=sorted(range(len(a)), key=lambda k: a[k])
for i in range(len(a)):
  print(b[i]+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)
### BUGGY CODE ###

s = input()
ans = 0
while len(set(s)) > 1:
    if s[-1] == "W":
        b = s.rfind("B") + 1
        s = s[:b] + "B" * (len(s[b:]) + 1)
    else:
        b = s.rfind("W") + 1
        s = s[:b] + "W" * (len(s[b:]) + 1)
    ans += 1
print(ans)

### FIXED CODE ###

s = input()
ans = 0
for i in range(len(s) - 1):
    if s[i] != s[i + 1]:
        ans += 1
print(ans)
### BUGGY CODE ###

def f(s):
    k = len(s)
    md = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(k + 1)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, c in enumerate(s[::-1]):
        dpi1 = dp[i + 1]
        if c == "?":
            for n in range(10):
                m = n * 10 ** i % 13
                for j in range(13):
                    dpi1[j] = (dpi1[j] + dpi[j - m]) % md
        else:
            m = int(c) * 10 ** i % 13
            for j in range(13):
                dpi1[j] = (dpi1[j] + dpi[j - m]) % md
        dpi = dpi1
    print(dp[k][5])

s = input()
f(s)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

def main():
    s = SI()
    n = len(s)
    dp = [[0] * 13 for _ in range(n + 1)]
    # dp[i][m]...iケタ目までみたときに、余りがmになる数の個数
    dp[0][0] = mint(1)
    e10 = 1
    for i, c in enumerate(s[::-1]):
        for m in range(13):
            pre = dp[i][m]
            if pre == 0: continue
            if c == "?":
                for d in range(10):
                    nm = (m + d * e10) % 13
                    dp[i + 1][nm] += pre
            else:
                nm = (m + int(c) * e10) % 13
                dp[i + 1][nm] += pre
        e10 = e10 * 10 % 13
    print(dp[n][5])

main()
### BUGGY CODE ###

def MI(): return map(int, input().split())
def LI(): return list(MI())

if __name__ == "__main__":
    N = int(input())
    A = LI()
    for i in range(1, N+1):
        print(A.count(i))

### FIXED CODE ###

import collections

def MI(): return map(int, input().split())
def LI(): return list(MI())

if __name__ == "__main__":
    N = int(input())
    A = dict(collections.Counter(LI()))
    for i in range(1, N+1):
        count = A.get(i)
        print(count if count is not None else 0)
### BUGGY CODE ###

import fractions
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: break
                P.add(f)
                while n%f == 0:
                    n //= f
            else:
                f += 2
        else:
            if n != 1:
                if n in P: break
                P.add(n)
            
            continue
        break
    else:
        return 0
        
    return 1 

def get_gcd(X):
	gcd = X[0]
	for x in X[1:]:
	    gcd = fractions.gcd(x, gcd)
	return gcd

def main():
    N=ii()
    A=list(mi())

    flag = solve(N,A)
    if flag == 0:
        print("pairwise coprime")
    else:
        gcd = get_gcd(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    fl = True
    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: 
            fl = False
            break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: 
                    fl = False
                    break
                
                P.add(f)
                while n % f == 0:
                    n //= f
            else:
                f += 2

        if n != 1:
            if n in P:
                fl = False
                break
            P.add(n)
            
        if not fl:
            break

        
    return fl



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()
### BUGGY CODE ###

def main():
    n, k, c = map(int,input().split())
    s = input()
    schedule = [w == "o" for w in s]
    left = []
    l_day = 0
    right = []
    r_day = n - 1
    while len(left) < k:
        if schedule[l_day]:
            left.append(l_day)
            l_day += c
        l_day += 1

    while len(right) < k:
        if schedule[r_day]:
            right = [r_day] + right
            r_day -= c
        r_day -= 1


    for i in range(k):
        if left[i] == right[i]:
            print(left[i] + 1)



if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k, c = map(int,input().split())
    s = input()
    schedule = [w == "o" for w in s]
    left = []
    l_day = 0
    right = []
    r_day = n - 1
    while len(left) < k:
        if schedule[l_day]:
            left.append(l_day)
            l_day += c
        l_day += 1

    while len(right) < k:
        if schedule[r_day]:
            right.append(r_day)
            r_day -= c
        r_day -= 1

    right.reverse()


    for i in range(k):
        if left[i] == right[i]:
            print(left[i] + 1)



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

# -*- coding: utf-8 -*-

import sys
from math import sqrt

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

# for i in range(N, 0, -1):
#     print(i, N//i, N%i)

m=N
ans=set()
while m>=sqrt(N):
    i=N//m
    while m>0:
        if i==N%m:
            ans.add(m)
            break
        elif i<N%m:
            break
        else:
            m-=1
    m=N//(i+1)

for m in range(1, int(sqrt(N))+1):
    if N//m==N%m:
        ans.add(m)

print(sum(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from math import sqrt

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

# for i in range(N, 0, -1):
#     print(i, N//i, N%i)

# 0除算対策
if N==1:
    print(0)
    exit()

m=N
ans=set()
while m>=sqrt(N):
    i=N//m
    j=N%m
    if (i-j)%i==0 and N//m==N//(m-1):
        ans.add(m-1)
    m=N//(i+1)

for m in range(1, int(sqrt(N))+1):
    if N//m==N%m:
        ans.add(m)

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

import collections
N = int(input())
S = [input() for i in range(N)]
D = collections.Counter(S)
print(*[j[0] for j in sorted(D.items()) if j[1] == max(D.values())], sep="\n")

### FIXED CODE ###

import collections
N = int(input())
D = collections.Counter(input() for i in range(N))
maximum = max(D.values())
sort = sorted(key for key,value in D.items() if value == maximum)
for s in sort:
    print(s)
### BUGGY CODE ###

# C と AB それぞれソートするのが遅い？そんなに？
N, M = list(map(int, input().split()))
C = list(map(int, input().split()))
#C = sorted(C)
AB = [list(map(int, input().split())) for i in range(M)]
AB = [ab[1] for ab in AB for i in range(ab[0])]
#AB = sorted(AB, key=lambda x: x[1], reverse=True)
C.extend(AB)
C = sorted(C, reverse=True)
print(sum(C[:N]))

### FIXED CODE ###

def main():
  N, M = list(map(int, input().split()))
  C = list(map(int, input().split()))
  C = sorted(C)
  AB = [list(map(int, input().split())) for i in range(M)]
  AB = sorted(AB, key=lambda x: x[1], reverse=True)
  
  result = 0
  i, j = 0, 0
  while i < N:
    A, B = AB[j] if j < M else (0, 0)
    j += 1
    if i+A < N and B >= C[i+A]:
      i += A
      result += A * B
    else:
      break
    
  while i < N:
    if C[i] > B:
      result += sum(C[i:])
      break
    else:
      result += B
      A -= 1      
      if j < M and A == 0:
        A, B = AB[j] if j < M else (0, 0)
        j += 1
    
    i += 1
  
  print(result)

if __name__ == "__main__":
  main()