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

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

tfc = [[] for _ in range(Q)]


for i in range(Q):
    tfc[i] = input().split()
    
for i in range(Q):
    if int(tfc[i][0])==1:
        S = S[::-1]
    else:
        if int(tfc[i][1])==1:
            S.insert(0,tfc[i][2])
        else:
            S.append(tfc[i][2])
print("".join(S))

### FIXED CODE ###

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

from collections import deque

S = deque(S)

tfc = [[] for _ in range(Q)]

swich = 0
for i in range(Q):
    tfc[i] = input().split()
    
    if int(tfc[i][0])==1:
        swich += 1
    else:
        if swich%2==0:
            if int(tfc[i][1])==1:
                S.appendleft(tfc[i][2])
            else:
                S.append(tfc[i][2])
        else:
            if int(tfc[i][1])==1:
                S.append(tfc[i][2])
            else:
                S.appendleft(tfc[i][2])

if swich%2==1:
    S = reversed(S)
    print("".join(S))
else:
    print("".join(S))
### BUGGY CODE ###

import sys
from fractions import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    A = tuple(map(int, input().split()))
    gcd_v = reduce(lcm, A)

    ans = 0
    for i in A:
        ans += gcd_v // i
        ans %= MOD
    print(ans)

def lcm(n, m):
    return (n * m) // gcd(n, m)    

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from fractions import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    A = tuple(map(int, input().split()))
    gcd_v = reduce(lcm, A)

    ans = 0
    for i in A:
        ans += gcd_v * pow(i, MOD-2, MOD) % MOD
        ans %= MOD
    print(ans)

def lcm(n, m):
    return (n * m) // gcd(n, m)    

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

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
s = 0
for i in range(60):
  B = [((1<<i)&Ai)>0  for Ai in A]
  s += (1<<i) * B.count(True) * B.count(False)
print(s%MOD)

### FIXED CODE ###

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
s = 0
n = len(bin(max(A))[2:])
for i in range(n):
  b = 1<<i
  N_t = sum([1 for Ai in A if (b&Ai)>0])
  N_f = N-N_t
  s += (1<<i) * N_t * N_f
print(s%MOD)
### BUGGY CODE ###

k = int(input())

i = 0
n = 0
while n <= 10000:
  i += 1
  s = str(i)
  for j in range(len(s)-1):
    if (int(s[j]) - int(s[j+1])) not in [-1, 0, 1]:
      break
  else:
    n += 1
    if n == k:
      print(i)


### FIXED CODE ###

from collections import deque
 
k = int(input())
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
 
for i in range(k):
  a = q.popleft()
  if a % 10 == 0:
    q.append(10*a)
    q.append(10*a + 1)
  elif a % 10 == 9:
    q.append(10*a + 8)
    q.append(10*a + 9)
  else:
    q.append(10*a + a%10 - 1)
    q.append(10*a + a%10)
    q.append(10*a + a%10 + 1)
else:
  print(a)
### BUGGY CODE ###

import statistics
import copy

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    l=copy.deepcopy(a)
    l.pop(i)
    l.sort()
    ans=l[n//2-1]
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=sorted(a)
x=l[n//2-1]
y=l[n//2]
for z in a:
    if z<=x:
        print(y)
    else:
        print(x)
### BUGGY CODE ###

import sys

mod = 10**9 + 7

def solve():
    m, n = map(int, input().split())

    ans = modpow(m, n, mod)

    print(ans)

def modpow(x, y, mod):
    res = 1

    while y:
        if y & 1:
            res = (res * x) % mod

        x *= x
        y >>= 1

    return res

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys

mod = 10**9 + 7

def solve():
    m, n = map(int, input().split())
    print(pow(m, n, mod))

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

import sys
input = sys.stdin.readline
N = int(input())
A = tuple(map(int,input().split()))
b = 0
c = N-1
num = 1000000007
for i in range(c):
    for j in range(i+1,N):
        b += A[i] ^ A[j]
print(b%num)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
for k in range(60):
    A_0 = 0
    A_1 = 0
    for i in range(N):
        if A[i]>>k&1:
            A_1 += 1
        else:
            A_0 += 1
    num = A_1 * A_0
    ans += (num * 2 ** k)
ans %=  mod
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(x) for x in input().split()]
b=[0 for x in range(n+1)]

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

c=0
for i in range(1,n+1):
  for j in range(n-i+1):
    if (b[j+i]-b[j])%m == 0:
      c += 1

print(c)


### FIXED CODE ###

n,m=map(int,input().split())
a=[int(x) for x in input().split()]
b=[0 for x in range(n+1)]
l=list([0])

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

for i in range(1,n+1):
  l.append(b[i]%m)

d=list()
l.sort()
t,c=0,1
for i in range(1,n+1):
  if l[i]==l[i-1]:
    c+=1
  else:
    if c!=1:
      t += c*(c-1)//2
      c=1

if c!=1:
  t += c*(c-1)//2  

print(t)
### BUGGY CODE ###

class Dict(object):

    m1 = 1046527
    m2 = m1 - 1

    def __init__(self):
        self._dict = ["" for _ in range(self.m1)]

    def insert(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == "":
                self._dict[ix] = k
                return
            else:
                i += 1

    def find(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == k:
                return ix
            elif self._dict[ix] == "":
                return -1
            else:
                i += 1

    def _h(self, k, i):
        return (self._h1(k) + i * self._h2(k)) % self.m1

    def _h1(self, k):
        return k % self.m1

    def _h2(self, k):
        return k % self.m2 + 1


def to_int(s):
    _s = s[::]

    ret = 0
    i = 1
    for e in _s:
        if e == 'A':
            ret += 1 * i
        elif e == 'C':
            ret += 2 * i
        elif e == 'G':
            ret += 3 * i
        elif e == 'T':
            ret += 4 * i
        i *= 4

    return ret


if __name__ == '__main__':
    n = int(input())

    d = Dict()

    for _ in range(n):
        cmd, val = input().split()

        if cmd == "insert":
            d.insert(to_int(val))
        else:
            ans = "yes" if d.find(to_int(val)) != -1 else "no"
            print(ans)

### FIXED CODE ###

M = 1046527
L = 14
H = [""] * M
 
def getChar(ch):
    if ch == 'A':
        return 1
    elif ch == 'C':
        return 2
    elif ch == 'G':
        return 3
    elif ch == 'T':
        return 4
    else:
        return 0
 
def getKey(strings):
    Sum = 0
    p = 1
    for i in xrange(len(strings)):
        Sum += p * getChar(strings[i])
        p *= 5
 
    return Sum
 
def h1(key):
    return key % M
 
def h2(key):
    return 1 + (key % (M-1))
 
def find(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            return 0
        else:
            i += 1
    return 0
 
def insert(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            H[h] = strings
            return 0
        else:
            i += 1
    return 0
 
def main():
    n = input()
    for i in xrange(n):
        com = raw_input().split()
        if com[0][0] == 'i':
            insert(com[1])
        else:
            if find(com[1]):
                print 'yes'
            else:
                print 'no'
    return 0
 
main()
### BUGGY CODE ###

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b)):
            min = len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b))
    print(min)

### FIXED CODE ###

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b)):
            min = len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b))
    print(min)
### BUGGY CODE ###

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

maxP=-10**15

if N<100000000:
    for i in range(1,N+1):
        tmp=(A*i)//B-A*(i//B)
        if maxP<tmp:
            maxP=tmp
        
else:
    for i in range(1,10000000):
        tmp=(A*i)//B-A*(i//B)
        if maxP<tmp:
            maxP=tmp
    for i in range(N-10000000,N+1):
        tmp=(A*i)//B-A*(i//B)
        if maxP<tmp:
            maxP=tmp
print(maxP)

### FIXED CODE ###

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

i=min(B-1,N)


tmp=(A*i)//B-A*(i//B)

        
print(tmp)
### BUGGY CODE ###

K = int(input())

q = []
for i in range(1, 10):
    q.append(i)

for i in range(K):
    x = q.pop(0)
    if x % 10 != 0:
        q.append(10 * x - 1 + x % 10)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + 1 + x % 10)

print(x)


### FIXED CODE ###

from collections import deque
K = int(input())

q = deque()
for i in range(1, 10):
    q.append(i)

for i in range(K):
    x = q.popleft()
    if x % 10 != 0:
        q.append(10 * x - 1 + x % 10)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + 1 + x % 10)

print(x)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
result = 0
mod = 10 ** 9 +7
for i in range(N):
  for j in range(i+1, N):
    result = (result + A[i] * A[j] % mod) % mod
print(result)

### FIXED CODE ###

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

mod = 10 ** 9 +7
amount = sum(A)
calc = []
for i in range(N - 1):
  amount = amount - A[i]
  calc.append(amount)

for i in range(N - 1):
  calc[i] *= A[i]

print(sum(calc) % mod)
### BUGGY CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = [True] * N
    colors[pc] = False

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for idx_c, c in enumerate(colors):
                if c:
                    ec[idx] = idx_c
                    colors[idx_c] = False
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append((b - 1, i))
    edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)
### BUGGY CODE ###

import math

n = int(input())
count = 0
temp = True
z = []

if n == 1:
    print(0)
    exit()

for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
        temp = False
        z.append(i)

if temp == True:
    print(1)
    exit()

for j in range(7):
    for k in z:
        if k > 1000000:
            break
        z.append(k ** j)

for l in z:
    if n % l == 0:
        count += 1
        n = n // l

print(count)


### FIXED CODE ###

import math

n = int(input())
count = 0
p = n

for z in range(2, int(math.sqrt(n)) + 1):
    e = 1
    while n % z ** e == 0:
        n //= z ** e
        count += 1
        e += 1
    if n % z == 0: #これを行わなければ，素因数同士でかける場合も含んでしまう．
        while n % z == 0:
            n //= z

if n != 1:
    count += 1
if count == 0 and p != 1:
    count = 1

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

# ContestName
# URL
import sys
import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = np.array(ii2nnn(C))
    c = np.array(ii2nnn(N))
    E = np.array([[0] * C for _ in range(3)])
    for i in range(N):
        for j in range(N):
            before = c[i][j]
            e = (i+j) % 3
            for after in range(1, C+1):
                E[e][after-1] += D[before-1][after-1]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0][c1] + E[1][c2] + E[2][c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()


### FIXED CODE ###

# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    E = [[0] * C for _ in range(3)]
    for i in range(N):
        for j in range(N):
            before = c[i][j]
            e = (i+j) % 3
            for after in range(1, C+1):
                E[e][after-1] += D[before-1][after-1]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0][c1] + E[1][c2] + E[2][c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()
### BUGGY CODE ###

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

ptn = 0
for i in range(n+1):
    if i*r > n:
        break
    
    for j in range(n+1):
        if i*r + j*g > n:
            break
        
        if ((n - i*r - j*g)%b) == 0:
            ptn += 1
        
print(ptn)

### FIXED CODE ###

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

ptn = 0
for i in range(n+1):
    if i*r > n:
        break
    
    for j in range(n+1):
        if i*r + j*g > n:
            break
        
        if ((n - i*r - j*g)%b) == 0:
            ptn += 1
        
print(ptn)
### BUGGY CODE ###

n, m = map(int, input().split())
connections = [list(map(int, input().split())) for _ in range(m)]
weights = [2e5 + 10] * n
weights[0] = 1
directions = [1] * n
for _ in range(m):
    for con in connections:
        r1 = con[0]
        r2 = con[1]
        w1 = weights[r1 - 1]
        w2 = weights[r2 - 1]
        if w1 < 2e5 + 10 and w1 + 1 < w2:
            weights[r2 - 1] = w1 + 1
            directions[r2 - 1] = r1
        if w2 < 2e5 + 10 and w2 + 1 < w1:
            weights[r1 - 1] = w2 + 1
            directions[r1 - 1] = r2

if max(weights) > 2e5 + 5:
    print("No")
else:
    print("Yes")
    for d in directions[1:]:
        print(d)

### FIXED CODE ###

import sys
from collections import deque
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int, readline().split())
 
G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)
 
par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)
 
print('Yes')
print(*par[2:], sep='\n')
### BUGGY CODE ###

import numpy as np
import itertools

n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = np.array(list(itertools.combinations_with_replacement(range(1, m + 1), n)))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = list(itertools.combinations_with_replacement(range(1, m + 1), n))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split())))

ans = 0
for i in range(len(l)):
    for j in range(len(l))[i + 1:]:
        k = bisect_left(l[j:], l[i] + l[j]) + j
        ans += k - j - 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        k = bisect_left(l,l[i]+l[j])
        ans += k - j - 1

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

import numpy as np
import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    dp = [[0]*H for _ in range(N)]

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j+1 < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせか新しい魔法1回とで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], w[i])
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

    print(dp[N-1][H-1])


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    dp = [[0]*H for _ in range(N)]

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j+1 < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせか新しい魔法1回とで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], w[i])
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

    print(dp[N-1][H-1])


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

import math
N =int(input())
N_kfk = []
kfk = []
for j in range(1,N+1):
    #Nの約数の個数を求める
    N_k = []
    for i in range(1,j+1):
        if i>j**0.5:
            break
        if j % i == 0:
            N_k.append(i)
            N_k.append(j//i)
    set_n = len(set(N_k))
    #print(N_k)
    #Nの約数の個数求めるの終わり
    N_kfk.append(set_n*j)
    #kfk.append(set_n)
print(sum(N_kfk))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ans = 0
for i in range(1,N+1):
    n = N//i
    ans += i * n*(n+1)//2
print(ans)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [0 for _ in range(H*W)]
for i in range(H*W) :
    for h, l in enumerate(A) :
        try :
            w = l.index(i+1)
            break
        except ValueError:
            pass
    dp[i] = (h, w)

def f(p, q) :
    x, y = dp[p-1]
    i, j = dp[q-1]
    return abs(x-i)+abs(y-j)

for l, r in LR :
    print(sum(f(p, p+D) for p in range(l, r, D)))

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [None for _ in range(H*W)]
for i, l in enumerate(A) :
    for j, v in enumerate(l) :
        dp[v-1] = (i, j)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        pass
    else :
        distance[i] = f(i-D, i) + distance[i-D]

for l, r in LR :
    print(distance[r-1]-distance[l-1])
### BUGGY CODE ###

#5
#24 11 8 3 16

N = int(input())
num = list(map(int, input().split()))
divz = [0]*N

for i, n in enumerate(num):
    for k in range(N):
        if k != i:
            if num[k] % num[i] == 0:
                divz[k] += 1

            if num[i] % num[k] == 0:
                divz[i] += 1

count = 0
for k in range(N):
    if divz[k] == 0:
        count += 1

print(count)


### FIXED CODE ###

import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
    if mark[n] < 2:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

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

import numpy as np

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

ans = None

for i in range(1, n):
  temp_1 = a[:i]
  temp_2 = a[i:]
  
  abs_num = abs(temp_1.sum() - temp_2.sum())

  if ans == None or ans > abs_num:
    ans = abs_num
else:
  print(ans)

### FIXED CODE ###

import numpy as np

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

b = a[0]
c = a[1:].sum()
ans = abs(b - c)

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

  if ans > abs(b-c):
    ans = abs(b-c)
else:
  print(ans)
### BUGGY CODE ###

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

for i in range(m):
    b , c = map(int,input().split())
    a.extend([c for i in range(b)])

a.sort(reverse = True)

print(sum(a[:n]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(lambda x: [int(x),1], input().split()))

for i in range(m):
    b , c = map(int,input().split())
    a.append([c,b])
a.sort(reverse = True)

ans = 0
for x,y in a:
    if y < n:
        ans += x*y
        n = n-y
    elif y >=n:
        ans += x*n
        break
print(ans)