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

h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]


dp = [10 ** 8 + 1 for i in range(h + 10**4 + 1)]
dp[0] = 0

for i in range(h+1):
  for j in range(n):
    if dp[i] == 10 ** 8 + 1:
      continue

    x = dp[i] + l[j][1]
    if dp[i + l[j][0]] > x:
      dp[i + l[j][0]] = x

print(min(dp[h:]))


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

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

def calc(n, a, m):
    x = 1
    y = 1
    if a > n//2:
        a = n-a
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

m = 10**9+7
if k >= n-1:
    print(calc(2*n-1, n-1, m))
else:
    s = 0
    for i in range(n-k-1):
        s += calc(n-1,i,m)*calc(n,i+1,m)
    print((calc(2*n-1, n-1, m)-s)%m)

### FIXED CODE ###

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

def calc(n,m):
    y = [1]*(n+1)
    for i in range(n):
        y[i+1] = (y[i]*(i+1))%m
        
    return y

def calc2(n,a,m,y):
    x = (y[a]*y[n-a])%m
    return (y[n]*pow(x, m-2, m))%m

m = 10**9+7
y = calc(2*n-1,m)
if k >= n-1:
    print(calc2(2*n-1, n-1, m, y))
else:
    s = 0
    for i in range(n-k-1):
        s += calc2(n-1,i,m,y)*calc2(n,i+1,m,y)
    print((calc2(2*n-1, n-1, m, y)-s)%m)
### BUGGY CODE ###

n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    ans += num.count(scan)

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ct = Counter(num)

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    if(ct[scan] != 0):
        ans += ct[scan]

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

n=int(input())
su=0
for i in range(n):
    su+=i
print(su)

### FIXED CODE ###

##################
n = int(input())
print((n*(n-1))//2)
### BUGGY CODE ###

n=int(input())
l=list(input())

for i in range(n-1):
    if l[i]==l[i+1]:
        l.pop(i)
        l.insert(i,1)

for i in range(n):
    if 1 in l:
        l.pop(l.index(1))

print(len(l))

### FIXED CODE ###

n=int(input())
l=list(input())

i=0
while i<(len(l)-1):
    if l[i]==l[i+1]:
        l.pop(i+1)

    else:
        i=i+1

print(len(l))
### BUGGY CODE ###

from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
for _ in range(M):
    a,b=map(int, input().split())
    alist.append(a)
    blist.append(b)
rdic = {}
d = deque()
def find_index(n):
    returnlist = []
    for indexa,i in enumerate(alist):
        if i == n:
            returnlist.append(blist[indexa])
    for indexb,i in enumerate(blist):
        if i == n:
            returnlist.append(alist[indexb])
    return returnlist
d.append(1)
rdic[1] = 0
c = 0
while True:
    getlist = find_index(d[0])
    for i in getlist:
        if i not in rdic:
            rdic[i] = d[0]
            d.append(i)
            c+=1
    if c == N-1:
        break
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n])

### FIXED CODE ###

from collections import deque
N,M=map(int, input().split())
alist = []
blist = []
T = [ [] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    T[a-1].append(b)
    T[b-1].append(a)
# T[i]にはi+1が接続してる数のリスト
rdic = [0]*(N)
d = deque()
d.append(1)
c = 0
ans = [0]*N
while len(d)>0:
    getlist = T[d[0]-1]
    for i in getlist:
        if rdic[i-1]==0:
            rdic[i-1] = d[0]
            d.append(i)
    d.popleft()
print('Yes')
for n in range(2,N+1):
    print(rdic[n-1])
### BUGGY CODE ###

#import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

#d = tuple(d)
n = 0
#t = time.clock()
for i in range(k1):
    for j in range(k1):
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n


### FIXED CODE ###

import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())
### BUGGY CODE ###

def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

    N = int(input())
    S = list(input())

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt_l = 1
    cnt_r = 0
    pre = 'B'
    pre_d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if pre_d:
                pre_d = 0
                ans *= (cnt_l - cnt_r)%mod
                cnt_r += 1
            else:
                pre_d = 1
                cnt_l += 1
        else:
            if pre_d:
                cnt_l += 1
            else:
                ans *= (cnt_l - cnt_r)%mod
                cnt_r += 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt_l!=N:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  count = 0
  for i in range(n-1):
    if not (any([a[i] % p == 0 for p in a[:i]+[a[i+1]]])):
      count += 1
  if not (any([a[-1] % p == 0 for p in a[:-1]])):
      count += 1
  print(count)
  

if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in range(1, n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
      db[a[i]-1] = 1
  if n == 1 or a[0] != a[1]:
    db[a[0]-1] = 1
  if n > 1 and a[-1] != a[-2]:
    db[-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

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


def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] > par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1]
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
points.sort(key=lambda x:x[2][0])
for i in range(N-1):
    edges.append((abs(points[i][2][0] - points[i+1][2][0]), points[i][1], points[i+1][1]))
points.sort(key=lambda x:x[2][1])
for i in range(N-1):
    edges.append((abs(points[i][2][1] - points[i+1][2][1]), points[i][1], points[i+1][1]))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
points.sort()
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
r = 1
for i in a:
    r *= i
r = -1 if r > 10 ** 18 else r
print(r)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
o = 10 ** 18
r = 1
if 0 not in a:
    for i in a:
        r *= i
        if r > o:
            r = -1
            break
else:
    r = 0
print(r)
### BUGGY CODE ###

def resolve():
    from scipy.sparse.csgraph import shortest_path
    import numpy as np
    inf = 10 ** 20
    n, m, l = map(int, input().split())
    if m == 0:
        q = int(input())
        for _ in range(q):
            print(-1)
        return
    ar = np.zeros((n, n))
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1, b - 1] = c
        ar[b - 1, a - 1] = c
    x = shortest_path(ar)
    br = np.zeros((n, n))
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i, j] = 1
                br[j, i] = 1
    y = shortest_path(br)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = map(int, input().split())
    inf = 10 ** 20
    ar = np.zeros((n, n))
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1, b - 1] = c
        ar[b - 1, a - 1] = c
    x = floyd_warshall(ar)
    br = np.zeros((n, n))
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i, j] = 1
                br[j, i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


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

import sys
from itertools import permutations

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(')
    r = x.count(')')
    if l != r: return 0

    return 1

def main():
    readline = sys.stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for i in range(n))
    comb_s = tuple(set(permutations(s)))

    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    plus, minus = [], []
    for c in s:
        if 2 * c.count('(') - len(c) > 0:
            plus.append(c)
        else:
            minus.append(c)

    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)
    sum = 0
    for v in plus:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

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

n, m = map(int, input().split())
l, r = map(int, input().split())
card = set(range(l, r + 1))
for _ in range(1, m):
    l, r = map(int, input().split())
    card &= set(range(l, r + 1))

print(len(card))

### FIXED CODE ###

n, m = map(int, input().split())
lr = [tuple(map(int, input().split())) for _ in range(m)]
maxl = max(_[0] for _ in lr)
minr = min(_[1] for _ in lr)
if minr - maxl >= 0:
    answer = minr - maxl + 1
else:
    answer = 0
print(answer)
### BUGGY CODE ###

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

from statistics import median 
for i in range(len(A)):
    tmp = A.pop(0)
    print(median(A))
    A.append(tmp)

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
copy_X = X.copy()
X.sort()
for i in copy_X:
    if(i<X[N//2]):
        print(X[N//2])
    else:
        print(X[(N//2)-1])
### BUGGY CODE ###

from collections import*
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

n,t=map(int,input().split())

x=[list(map(int,input().split()))for i in range(n)]

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(d[i],l[-1]))
    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(db[i],l[-1]))
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            if ans<dp[i][j]+dp2[i][t-j-1]:
                ans=dp[i][j]+dp2[i][t-j-1]
        else:
            if dp[i][j]+dp2[i][t-j-1]+x[i-1][1]>ans:
                ans=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

n,t=map(int,input().split())

x=[tuple(map(int,input().split()))for i in n*[0]]
x.sort()
dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)
### BUGGY CODE ###

n,x=map(int,input().split())
listl=list(map(int,input().split()))
sum=0
count=0
for k in range(2,n+1):
  sum+=listl[k-2]
  while sum<=x:
    count+=1
print(count+1)

### FIXED CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))
d=[0]
for i in range(n):
  d.append(d[i]+l[i])
cnt=0
for dd in d:
  if dd>x:
    break
  cnt+=1
print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()
t = []
for i in range(n):
    x = s[0:i]
    y = s[i+1:n]
    t.append(x.count('W')+y.count('E'))
print(min(t))

### FIXED CODE ###

n = int(input())
s = input()
t = []
x = 0
y = s.count('E')
for ch in s:
    if ch == 'E':
        y -= 1
    t.append(x+y)
    if ch == 'W':
        x += 1
print(min(t))
### BUGGY CODE ###

from functools import reduce

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

def cmb(n, r):
    INF = 998244353
    r = min(n - r, r)
    if r == 0:  return 1
    numer = reduce(lambda x, y: (x * y) % INF, range(n, n - r, -1))
    denom = reduce(lambda x, y: (x * y) % INF, range(1, r + 1))
    return (numer * pow(denom, INF - 2, INF)) % INF

N, M, K = cin()
ans = 0
for i in range(K + 1):
    ans += M * cmb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
    ans %= 998244353
print(ans)

### FIXED CODE ###

from functools import reduce

def cin():  return list(map(int,input().split()))
N, M, K = cin()
MOD = 998244353

fac = [1] * (N + 1)
inv = [1] * (N + 1)

for j in range(1, N + 1):  fac[j] = fac[j - 1] * j % MOD

inv[N] = pow(fac[N], MOD - 2, MOD)
for j in range(N - 1, -1, -1):  inv[j] = inv[j + 1] * (j + 1) % MOD
    
def cmb(n, r):
    if r > n or n < 0 or r < 0:  return 0
    return fac[n] * inv[n - r] * inv[r] % MOD

ans = 0
for i in range(K + 1):
    ans += M * cmb(N - 1, i) * pow(M - 1, N - 1 - i, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b+1):
    if i % x == 0:
        ans += 1
print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split())
ans = b//x - (a-1)//x
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(a) for a in input().split()]

is_over = False
count = 0
for i in range(1, n+1):
    # print('i:', i)
    while True:
        # print('    A:', A)
        # print('    count:', count)
        if len(A) == 0:
            is_over = True
            break
        if A[0] == i:
            A = A[1:]
            break
        else:
            A.pop(0)
            count += 1
    if is_over:
        break

if n == count:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())
A = [int(a) for a in input().split()]

is_over = False
now = 0

for a in A:
    if a == now+1:
        now += 1

if now == 0:
    print(-1)
else:
    print(n - now)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

H, W = map(int, input().split())

grid = []

count_w = [[0] * W for _ in range(H)]
count_h = [[0] * W for _ in range(H)]

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

print(max(
  count_h[h][w] + count_w[h][w] - 1
  for w in range(W)
  for h in range(H)      
))


### FIXED CODE ###

import sys

input = sys.stdin.readline

H, W = map(int, input().split())

grid = []

count_w = [[0] * W for _ in range(H)]
count_h = [[0] * W for _ in range(H)]

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

answer = 0

for h in range(H):
  for w in range(W):
    answer = max(answer, count_h[h][w] + count_w[h][w] - 1)

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

from collections import defaultdict
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def is_prime(n):
  for prime in prime_table:
    if n % prime == 0:
      return False
  else:
    return True

N, M = map(int, input().split())
p = 10 ** 9 + 7
prime_table = []
primes = defaultdict(int)
primes[1] = 0
n = 2
while n <= M:
  if is_prime(n):
    prime_table.append(n)
    while M % n == 0:
      primes[n] += 1
      M //= n
  n += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)

### FIXED CODE ###

from collections import defaultdict
import math
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def eratosthenes(limit):
  E = [1] * (limit + 1)
  E[0], E[1] = 0, 0
  prime_table = []
  for i, e in enumerate(E):
    if e:
      prime_table.append(i)
      for j in range(i, limit + 1, i):
        E[j] = 0
  return prime_table

N, M = map(int, input().split())
p = 10 ** 9 + 7
limit = int(math.sqrt(M)) + 1
prime_table = eratosthenes(limit)
primes = defaultdict(int)
primes[1] = 0
for prime in prime_table:
  if prime > M:
    break
  while M % prime == 0:
    primes[prime] += 1
    M //= prime
if M > 1:
  primes[M] += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)
### BUGGY CODE ###

import numpy as np
s=input()

ss=[]
for i in range(len(s)):
    ss.append(s[i])
arr=np.array(ss)

q=int(input())
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        arr=arr[::-1]
        
    else:
        if l[1]=="1":
            arr=np.hstack((l[2],arr))
        if l[1]=="2":
            arr=np.hstack((arr,[l[2]]))
        

a=arr.tolist()
for i in a:
    print(i,end="")

### FIXED CODE ###


s=input()
q=int(input())
p=0
a=""
b=""
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        p=(p+1)%2
    else:
        if p==0:
            if l[1]=="1":
                a+=l[2]
            else:
                b+=l[2]
        else:
            if l[1]=="1":
                b+=l[2]
            else:
                a+=l[2]
if p==1:
    print(b[::-1]+s[::-1]+a)
else:
    print(a[::-1]+s+b)