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

mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!='?':
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]
print(dp1[5])


### FIXED CODE ###

mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!='?':
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]
print(dp1[5])
### BUGGY CODE ###

from collections import deque

def main():
  N=int(input())
  S=list(map(int,input().split()))
  count=0
  P=[0]*(N*N+1)
  for j in range(N*N):
    P[S[j]]=j+1
  d=[-1]*(N*N+1)
  que=deque()
  for i in range(N*N):
    player=S[i]
    hayasa=P[player]
    que.clear()
    que.append((player,0))
    d[player]=i

    finish=-1
    while que:
      kouho,j=que.popleft()
      if kouho%N==0:
        finish=1
        break
      if kouho%N==1:
        finish=1
        break
      if kouho+N>N*N:
        finish=1
        break
      if kouho<N:
        finish=1
        break

      if d[kouho+N]<i:
        if P[kouho+N]>hayasa:
          que.append((kouho+N,j+1))
          d[kouho+N]=i
        else:
          que.appendleft((kouho+N,j))
          d[kouho+N]=i

      if d[kouho-N]<i:
        if P[kouho-N]>hayasa:
          que.append((kouho-N,j+1))
          d[kouho-N]=i
        else:
          que.appendleft((kouho-N,j))
          d[kouho-N]=i

      if d[kouho+1]<i:
        if P[kouho+1]>hayasa:
          que.append((kouho+1,j+1))
          d[kouho+1]=i
        else:
          que.appendleft((kouho+1,j))
          d[kouho+1]=i

      if d[kouho-1]<i:
        if P[kouho-1]>hayasa:
          que.append((kouho-1,j+1))
          d[kouho-1]=i
        else:
          que.appendleft((kouho-1,j))
          d[kouho-1]=i
    count+=j

  print(count)

main()


### FIXED CODE ###

from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)
### BUGGY CODE ###

L,R=map(int,input().split())
li=[]
for i in range(L,R):
  for j in range(i+1,R+1):
    mod=(i*j)%2019
    li.append(mod)
    if mod==0:
      break
print(min(li))


### FIXED CODE ###

L,R=map(int,input().split())
R=min(R, L+2019)
li=[]
for i in range(L,R):
  for j in range(i+1,R+1):
      mod=(i*j)%2019
      li.append(mod)
      if mod==0:
        break
print(min(li))
### BUGGY CODE ###

def main():
    s = input()
    m = 2019
    dp = [0]*m
    ans = 0
    for i in s:
        i = int(i)
        dp[0] += 1
        dp2 = [0]*m
        for j in range(m):
            dp2[(j*10+i) % m] += dp[j]
        dp = dp2
        ans += dp[0]
    print(ans)


main()

### FIXED CODE ###

def main():
    s = input()
    d = [0]*2019
    d[0] += 1
    now = 0
    for j, i in enumerate(s[::-1]):
        now = (int(i)*pow(10, j, 2019)+now) % 2019
        d[now] += 1
    print(sum([i*(i-1)//2 for i in d]))


main()
### BUGGY CODE ###

# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H]) 

### FIXED CODE ###

# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
from collections import *
cmn = defaultdict(int)

def prime_factorization(n):
    d = defaultdict(int)
    k = 2
    def check(k):
        nonlocal d, n
        while n % k == 0:
            d[k] += 1
            n //= k
    check(2)
    k = 3
    while (n != 1):
        check(k)
        k += 2
    return d
P = [prime_factorization(a) for a in A]

for p in P:
    for k in p.keys():
        cmn[k] = max(cmn[k], p[k])

ans = 0

for p in P:
    t = 1
    for k in cmn.keys():
        t *= pow(k, max(cmn[k] - p[k], 0), 10 ** 9 + 7)

    ans += t
    ans %= 10 ** 9 + 7

print(ans)


### FIXED CODE ###

from functools import reduce
import fractions


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % int(1e9+7)
print(ans)
# print(l)
# print(a)
### BUGGY CODE ###

import math
n=math.factorial(int(input()))
a=i=1
while i*i<=n:
  c=1
  while n%i==0:
    c+=1
    n//=i
  a*=c
  i+=1
print(a*2**(n!=1)%(10**9+7))

### FIXED CODE ###

import math
n=math.factorial(int(input()))
a,i=1,2
while i*i<=n:
  c=1
  while n%i==0:
    c+=1
    n//=i
  a*=c
  i+=1
print(a*2**(n!=1)%(10**9+7))
### BUGGY CODE ###

import math

MOD = 10**9+7


def mod_combination(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    ans = 0
    a.sort()
    for i in range(n):
        ans = (ans + a[i] * mod_combination(i, k-1)) % MOD

    a.sort(reverse=True)
    for i in range(n):
        ans = (ans-a[i] * mod_combination(i, k-1)) % MOD

    print(ans)


main()


### FIXED CODE ###

import math

MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    c_table = make_combination_table(n)

    a.sort()
    a_max = 0
    for i in range(n):
        a_max += a[i] * mod_combination(i, k-1, c_table) % MOD

    a.sort(reverse=True)
    a_min = 0
    for i in range(n):
        a_min += a[i] * mod_combination(i, k-1, c_table) % MOD

    print((a_max - a_min) % MOD)


main()
### BUGGY CODE ###

# E - Gluttony

import numpy as np

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

lower = 0
upper = A[-1] * F[0]

# 達成可能な最高成績を二分探索する
while lower <= upper:
    result = (lower + upper) // 2
    if sum(np.clip(A - result//F, 0, None)) <= K: # resultを達成可能なAと実際のAの差異の総和が必要な修行コスト
        ans = result
        upper = result - 1
    else:
        lower = result + 1

print(ans)

### FIXED CODE ###

# E - Gluttony

import numpy as np

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

lower = 0
upper = A[-1] * F[0]

# 達成可能な最高成績を二分探索する
while lower <= upper:
    result = (lower + upper) // 2
    # resultを達成可能なAと実際のAの差異の総和が必要な修行コスト
    # np.arrayの和を求める場合、sum(array)よりarray.sum()の方が速い(使わないとTLE)
    if np.clip(A - result//F, 0, None).sum() <= K:
        ans = result
        upper = result - 1
    else:
        lower = result + 1

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

a = list(input())
a = [int(s) for s in a]
a = a[::-1]
s = [0]
ans = [1] + [0] * 2018

for i in range(len(a)):
    add = s[i] + a[i] * 10 ** i
    add = add % 2019
    ans[add] += 1
    s.append(add)

ans_int = 0

for i in range(2019):
    if ans[i] > 1:
        ans_int += (ans[i] - 1)

print(ans_int)

### FIXED CODE ###

a = input()[::-1]
add = 0
ans = [1] + [0] * 2018
ans_int = 0
d = 1

for i in range(len(a)):
    add = (add + int(a[i]) * d) % 2019
    d = (10 * d) %2019
    ans[add] += 1

for i in range(len(ans)):
    a =((ans[i] - 1) * ans[i]) /2
    ans_int += a

print(int(ans_int))
### BUGGY CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
#S[0]は使わない
S = [[0]*60 for _ in range(N)]

tmp = A[-1]
idx = 0
while tmp > 0:
    if tmp%2:
        S[-1][idx] += 1
    idx += 1
    tmp //= 2

for i in range(N-2, 0, -1):
    for j in range(60):
        S[i][j] = S[i+1][j]
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            S[i][idx] += 1
        idx += 1
        tmp //= 2

ans = 0
for i in range(N-1):
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            ans += ((N-1-i)-S[i+1][idx])*2**idx

        else:
            ans += S[i+1][idx]*2**idx

        idx += 1
        tmp //= 2

    rest = S[i+1][idx:]
    for x in rest:
        ans += x*2**idx
        idx += 1

    ans %= mod

print(ans)

### FIXED CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*pow(2, i, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())

if K >= A+B:
    print(str(0)+' '+str(0))

else:
    for i in range(K):
        if A > 0:
            A -= 1
        elif B > 0:
            B -= 1
    print(str(A)+' '+str(B))

### FIXED CODE ###

A,B,K = map(int,input().split())

if K >= A+B:
    print(str(0)+' '+str(0))

elif K < A:
    print(str(A-K)+' '+str(B))

elif K >= A:
    print(str(0)+' '+str(B-(K-A)))
### BUGGY CODE ###

n , m = map(int, input().split())
keys = []
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    keys.append([a] + c)
inf = 10 ** 10
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i-1][0]
    can_open = keys[i-1][1:]
    for j in range(2**n):
        next = j | trans(can_open)
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

from collections import deque
n , m = map(int, input().split())
keys = deque()
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = deque(list(map(int, input().split())))
    c.appendleft(a)
    keys.append(c)
inf = 10 ** 8
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i].popleft()
    can_open = keys[i]
    p = trans(can_open)
    for j in range(2**n):
        next = j | p
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    for k in K:
        if 4*t-k<=0:
            continue
        x = bisect_left(L,2*t-k)-bisect_left(L,t-k)
        y = bisect_left(L,4*t-k)-bisect_left(L,3*t-k)
        #print(x,y)
        a =(a+x+y)%2
    num[i]=a
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)



### FIXED CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    #尺取り法,i*tより小さい整数を数える
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        #print(count,a)
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)
### BUGGY CODE ###

n = int(input())
lists = []
count = 0
while count < n:
    lists.append(input())
    count += 1

new_lists = []
for i in lists:
    new_lists.append(''.join(sorted(i)))

answer = 0
x = 1
for i in new_lists:
    if i in new_lists[x:]:
        answer += new_lists[x:].count(i)
    x += 1

print(answer)

### FIXED CODE ###

n = int(input())
lists = [input() for _ in range(n)]

for i in range(n):
    lists[i] = ''.join(sorted(lists[i]))

d = {}
for i in range(n):
    if lists[i] in d:
        d[lists[i]] += 1
    else:
        d[lists[i]] = 1

answer = 0
for i in d:
    answer += d[i] * (d[i]-1) // 2

print(answer)
### BUGGY CODE ###

def main():
    n,k,c=map(int,input().split())
    s=list(input())[::-1]
    sl=[0 if i=='x' else 1 for i in s]
    chk=int(''.join(map(str,sl)),2)
    ans=0
    for i in range(2**(n+1)):
        ocnt,cnt,bcnt,f=0,0,0,0
        for j in range(len(bin(i))-1):
            cnt+=1
            if i>>j&1:
                ocnt+=1
                if bcnt!=0:
                    if cnt-bcnt<=c:
                        f=1
                        break
                if ocnt>k:
                    f=1
                    break
                bcnt=cnt
        if f==0 and ocnt==k:
            if chk&i==i:
                if ans==0:
                    ans=i
                else:
                    ans=ans&i
                    if ans==0:
                        exit()
    for i in range(len(bin(ans))-1):
        if ans>>i&1:
            print(i+1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,k,c=map(int,input().split())
    s=list(input())
    l,r=[0]*(k+1),[0]*(k+1)
    x,i=1,0
    while i<=n-1:
        if s[i]=='o':
            l[x]=i+1
            i+=c+1
            x+=1
            if x==k+1:
                break
        else:
            i+=1
    x,i=k,n-1
    while 0<=i:
        if s[i]=='o':
            r[x]=i+1
            x-=1
            i-=c+1
            if x==0:
                break
        else:
            i-=1
    for i in range(1,k+1):
        if l[i]==r[i]:
            print(l[i])

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

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for i in range(n+1):
    for a, b in zip(A, B):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)
### BUGGY CODE ###

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

def calc_comb(lst_A):

    elem_A = list(set(lst_A))
    sum_comb = 0
    dct_A = {}

    for A in elem_A:
        numA  = lst_A.count(A)
        combA = (numA * (numA-1)) // 2
        dct_A[A] = numA
        sum_comb += combA

    return sum_comb, dct_A



def main(N, lst_A):

    sum_comb_all, dct_A = calc_comb(lst_A)

    for A in lst_A:
        numA = dct_A[A]
        prev_combA = (numA * (numA-1)) // 2
        new_combA  = ((numA-1) * (numA-2)) // 2

        sum_comb = sum_comb_all - prev_combA + new_combA
        print(sum_comb)

    return 0

if __name__ == "__main__":

    main(N, lst_A)
    

### FIXED CODE ###

from collections import Counter

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

def main(N, lst_A):

    dct_cntA = Counter(lst_A)
    sum_comb = 0

    for cntA in dct_cntA.values():
        comb = (cntA * (cntA - 1)) // 2
        sum_comb += comb

    for A in lst_A:
        print(sum_comb - (dct_cntA[A] - 1))

    return 0

if __name__ == "__main__":

    main(N, lst_A)
### BUGGY CODE ###

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*99*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=b,
for i in v[:M]:
 for j in i:heappush(q,-j)
 z-=heappop(q)
print(z)

### FIXED CODE ###

from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
q = [0] * 10**5
v = [[] for _ in q]
for a, b in t:
    v[a - 1] += b,
z = 0
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    z += -heappop(q)
print(z)
### BUGGY CODE ###

T = int(input())
a = []
for i in range(T):
    a.append(list(map(int, input().split())))
for r in a:
    s, b, c, d = r[0], r[1], r[2], r[3]
    mod_list = []
    if (s < b) or (b>d):
        print('No')
        continue
    if (c>b):
        print('Yes')
        continue
    while True:
        s = s%b
        if s > c:
            print('No')
            break
        s += d
        if s in mod_list:
            print('Yes')
            break
        mod_list.append(s)

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


T = int(input())
a = []
for i in range(T):
    a.append(list(map(int, input().split())))
for r in a:
    s, b, c, d = r[0], r[1], r[2], r[3]
    mod_list = []
    if (s < b) or (b>d):
        print('No')
        continue
    if (c>b):
        print('Yes')
        continue

    g = gcd(b,d)

    if b- g + s%g > c:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###


def want_p(n):

    Q = []

    while n != p[n]:
        Q.append(n)
        n = p[n]

    for i in Q:
        p[i] = n

    return n


N = int(input())

xyi = []
yxi = []

for i in range(N):

    x,y = map(int,input().split())
    xyi.append([x,y,i])
    yxi.append([y,x,i])

xyi.sort()
yxi.sort()

line = []


for i in range(N-1):

    line.append([ xyi[i+1][0]-xyi[i][0] , xyi[i][2] , xyi[i+1][2] ])
    line.append([ yxi[i+1][0]-yxi[i][0] , yxi[i][2] , yxi[i+1][2] ])

line.sort()

p = [i for i in range(N)]
rank = [1] * N
ans = 0

for j in range(len(line)):

    e = line[j]
    cost = e[0]
    a = e[1]
    b = e[2]

    ap = want_p(a)
    bp = want_p(b)

    #print (a,b,cost,p,ans)

    if ap != bp:
        ans += cost

        if rank[ap] > rank[bp]:
            p[bp] = ap

        elif rank[ap] == rank[bp]:
            p[bp] = ap
            rank[ap] += 1

        else:
            p[ap] = bp

print (ans)

### FIXED CODE ###

def want_p(n):
 
    Q = []
 
    while n != p[n]:
        Q.append(n)
        n = p[n]
 
    for i in Q:
        p[i] = n
 
    return n
 
 
N = int(input())
 
xyi = []
yxi = []
 
for i in range(N):
 
    x,y = map(int,input().split())
    xyi.append([x,y,i])
    yxi.append([y,x,i])
 
xyi.sort()
yxi.sort()
 
line = []
 
 
for i in range(N-1):
 
    line.append([ xyi[i+1][0]-xyi[i][0] , xyi[i][2] , xyi[i+1][2] ])
    line.append([ yxi[i+1][0]-yxi[i][0] , yxi[i][2] , yxi[i+1][2] ])
 
line.sort()
 
p = [i for i in range(N)]
rank = [1] * N
num = [1] * N
ans = 0
 
for j in range(len(line)):
 
    e = line[j]
    cost = e[0]
    a = e[1]
    b = e[2]
 
    ap = want_p(a)
    bp = want_p(b)
 
    if ap != bp:
        ans += cost

        k = num[ap]
        num[ap] += num[bp]
        num[bp] += k

        if num[ap] == N or num[bp] == N:
            break
 
        if rank[ap] > rank[bp]:
            p[bp] = ap
 
        elif rank[ap] == rank[bp]:
            p[bp] = ap
            rank[ap] += 1
 
        else:
            p[ap] = bp
 
print (ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
listBC=[]
for _ in range(M):
  B,C=map(int,input().split())
  listBC+=[[C,B]]  
listBC.sort(reverse=True)
i=0
while min(list1)<listBC[i][0]:  
  list1+=[listBC[i][0]]*listBC[i][1]  
  i+=1
  if i==len(listBC):
    break
for k in range(len(list1)-N):
  list1.remove(min(list1))
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

N = int(input())
S = list(input())
Q = []
for i in range(0,N) :
    A = S[0:i]
    B = S[i+1:N]
    a = "".join(A)
    b = "".join(B)
    Q.append(A.count("W")+B.count("E"))
print(min(Q))



### FIXED CODE ###

N = int(input())
S = list(input())
ANS = []
ans = 0
for i in range(0,N) :
    if i == 0 :
        ans += S[1:].count("E")
        ANS.append(ans)
    elif S[i-1] == "E" and S[i] == "E" :
        ans -= 1
        ANS.append(ans)
    elif S[i-1] == "W" and S[i] == "W" :
        ans += 1
        ANS.append(ans)
print(min(ANS))
### BUGGY CODE ###

s = input()
q = int(input())
quest = [0]*q
state = 0
# former, latter = '', ''
for i in range(q):
    que = input().split()
# for que in quest:
    if (que[0] == '1'):
        # 反転は計算量が多いので一度だけする。
        state = 1 - state
        continue
    else:
        if (state == 0 and que[1] == '1'):
            s = que[2] + s
        elif(state == 0 and que[1] == '2'):
            s = s + que[2]
        elif (state == 1 and que[1] == '1'):
            s = s + que[2]
        else:
            s = que[2] + s

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


### FIXED CODE ###

s = input()
q = int(input())
quest = [0]*q
state = 0
former, latter = '', ''
for i in range(q):
    que = input().split()
# for que in quest:
    if (que[0] == '1'):
        # 反転は計算量が多いので一度だけする。
        state = 1 - state
        continue
    else:
        if (state == 0 and que[1] == '1'):
            former = que[2] + former
        elif(state == 0 and que[1] == '2'):
            latter = latter + que[2]
        elif (state == 1 and que[1] == '1'):
            latter = latter + que[2]
        else:
            former = que[2] + former

if (state == 1):
    print(latter[::-1] + s[::-1] + former[::-1])
else:
    print(former + s + latter)