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

H, W = map(int, input().split())
S = []
l1 = []
for i in range(H):
  s = str(input())
  S.append(s)
  tmp = []
  cnt = 0
  flag = False
  for j in s:
    if flag:
      if j == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if j == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l1.append(tmp)

l2 = []
for i in range(W):
  tmp = []
  cnt = 0
  flag = False
  for j in range(H):
    x = S[j][i]
    if flag:
      if x == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if x == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l2.append(tmp)

ans = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if (l1[i][j]>0) and (l2[j][i]>0):
      ans[i][j] = l1[i][j] + l2[j][i] - 1
    else:
      ans[i][j] = l1[i][j] + l2[j][i]
print(max(list(map(lambda x: max(x), ans))))

### FIXED CODE ###

H, W = map(int, input().split())
S = []
l1 = []
for i in range(H):
  s = str(input())
  S.append(s)
  tmp = []
  cnt = 0
  flag = False
  for j in s:
    if flag:
      if j == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if j == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l1.append(tmp)

l2 = []
for i in range(W):
  tmp = []
  cnt = 0
  flag = False
  for j in range(H):
    x = S[j][i]
    if flag:
      if x == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if x == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l2.append(tmp)

ans = [[0]*W for i in range(H)]
m = 0
for i in range(H):
  for j in range(W):
    if (l1[i][j]>0) and (l2[j][i]>0):
      ans[i][j] = l1[i][j] + l2[j][i] - 1
    else:
      ans[i][j] = l1[i][j] + l2[j][i]
    m = max(m, ans[i][j])
print(m)
### BUGGY CODE ###

k,s = map(int,input().split())
r=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                r+=1
print(r)

### FIXED CODE ###

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

import itertools
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

sum = 0
l = list(range(1, k+1))
for a, b, c in itertools.product(l, l, l):
    sum += gcd(a, b, c)

print(sum)

### FIXED CODE ###

k = int(input())

ans = [
1,
9,
30,
76,
141,
267,
400,
624,
885,
1249,
1590,
2208,
2689,
3411,
4248,
5248,
6081,
7485,
8530,
10248,
11889,
13687,
15228,
17988,
20053,
22569,
25242,
28588,
31053,
35463,
38284,
42540,
46581,
50893,
55362,
61824,
65857,
71247,
76884,
84388,
89349,
97881,
103342,
111528,
120141,
128047,
134580,
146316,
154177,
164817,
174438,
185836,
194157,
207927,
218812,
233268,
245277,
257857,
268182,
288216,
299257,
313635,
330204,
347836,
362973,
383709,
397042,
416448,
434025,
456967,
471948,
499740,
515581,
536073,
559758,
583960,
604833,
633651,
652216,
683712,
709065,
734233,
754734,
793188,
818917,
846603,
874512,
909496,
933081,
977145,
1006126,
1041504,
1073385,
1106467,
1138536,
1187112,
1215145,
1255101,
1295142,
1342852,
1373253,
1422195,
1453816,
1502376,
1553361,
1595437,
1629570,
1691292,
1726717,
1782111,
1827492,
1887772,
1925853,
1986837,
2033674,
2089776,
2145333,
2197483,
2246640,
2332104,
2379085,
2434833,
2490534,
2554600,
2609625,
2693919,
2742052,
2813988,
2875245,
2952085,
3003306,
3096024,
3157249,
3224511,
3306240,
3388576,
3444609,
3533637,
3591322,
3693924,
3767085,
3842623,
3912324,
4027884,
4102093,
4181949,
4270422,
4361548,
4427853,
4548003,
4616104,
4718640,
4812789,
4918561,
5003286,
5131848,
5205481,
5299011,
5392008,
5521384,
5610705,
5739009,
5818390,
5930196,
6052893,
6156139,
6239472,
6402720,
6493681,
6623853,
6741078,
6864016,
6953457,
7094451,
7215016,
7359936,
7475145,
7593865,
7689630,
7886244,
7984165,
8130747,
8253888,
8403448,
8523897,
8684853,
8802826,
8949612,
9105537,
9267595,
9376656,
9574704,
9686065,
9827097,
9997134,
10174780,
10290813,
10493367,
10611772,
10813692
]

print(ans[k-1])
### BUGGY CODE ###

x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        if i ** j < x + 1:
            li[i ** j] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break


### FIXED CODE ###

x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        if i ** j > x:
            break
        li[i ** j] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break
### BUGGY CODE ###

"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""
import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

s = input()
question_count = s.count("?")
max_str = {"point":0,"str":""}


for i in range(2**question_count):
    swap_str = ""
    for j in range(question_count):
        if ((i>>j)&1):
            swap_str += "P"
        else:
            swap_str += "D"
    check_str = ""
    count = 0
    for st in s:
        if st == "?":
            check_str+=swap_str[count]
            count+=1
        else:
            check_str+=st
    
    point = 0
    point += check_str.count("D")
    point += check_str.count("PD")
    if max_str["point"] < point:
        max_str["point"] = point
        max_str["str"] = check_str
print(max_str["str"])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

s = input()
# question_count = s.count("?")
# max_str = {"point":0,"str":""}

# for i in range(2**question_count):
#     swap_str = ""
#     for j in range(question_count):
#         if ((i>>j)&1):
#             swap_str += "P"
#         else:
#             swap_str += "D"
#     check_str = str(s)
#     for char in range(question_count):
#         check_str = check_str.replace("?",swap_str[char],1)
    
#     point = 0
#     point += check_str.count("D")
#     point += check_str.count("PD")
#     if max_str["point"] < point:
#         max_str["point"] = point
#         max_str["str"] = check_str
#     print(point,check_str)
# print(max_str["str"])
print(s.replace("?","D"))
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [0] * Q
for i in range(Q):
  A[i] = int(input())
B = [K] * (N+1)
for i in range(1, N+1):
  B[i] +=  A.count(i) - Q 
  if B[i] <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0] * Q
B = [K-Q] * (N+1)
for i in range(Q):
  A[i] = int(input())
  B[A[i]] += 1
for i in range(1, N+1):
  if B[i] <= 0:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

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

# dp[i] stores the minimum cost to reach step i (starting from step 1) i: 1->N
dp = [10**9]*(n+1)
dp[1] = 0

## TLE : backward fill
# for i in range(2, n+1):
#     for ss in range(1, k+1): # ss: step size
#         if i-ss >= 1:
#             dp[i] = min(dp[i], dp[i-ss] + abs(hlist[i-1] - hlist[i - ss - 1]))

## Forward fill
for i in range(n+1):
    for ss in range(i+1, i+k+1):
        if ss<=n:
            dp[ss] = min(dp[ss], dp[i] + abs(hlist[i-1] - hlist[ss - 1]))

print(dp[n])

### FIXED CODE ###

n, k = map(int, input().split())
heights = list(map(int, input().split()))
heights = [0] + heights
dp = [10**10]*(n+1)
dp[1] = 0

for i in range(1, n+1):
    for step in range(1, k+1):
        if (i + step) <= n:
            dp[i+step] = min(dp[i+step], abs(heights[i+step] - heights[i]) + dp[i])
print(dp[n])
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10**9+7
A = [list(map(int, input().split())) for _ in range(n)]

# A*B
def mul(a, b):
    c = [[0]*len(b[0]) for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j] = (c[i][j] + a[i][k]*b[k][j])%mod

    return c

#A**n
def pow(a, n):
    b = [[0]*len(a) for i in range(len(a))]
    for i in range(len(a)):
        b[i][i] = 1
    while n > 0:
        if n & 1 == 1:
            b = mul(a, b)
        a = mul(a, a)
        n = n>>1
    return b

B = pow(A, k)
#print(B)
ans = 0
for i in range(n):
    ans += sum(B[i])
    ans %= mod
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
mod = 10**9+7
A = [list(map(int, input().split())) for _ in range(n)]

# A*B
def mul(a, b):
    c = [[0]*len(b[0]) for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j] = (c[i][j] + a[i][k]*b[k][j])%mod

    return c

#A**n
def pow(a, n):
    b = [[0]*len(a) for i in range(len(a))]
    for i in range(len(a)):
        b[i][i] = 1
    while n > 0:
        if n & 1 == 1:
            b = mul(a, b)
        a = mul(a, a)
        n = n>>1
    return b

B = pow(A, k)
#print(B)
ans = 0
for i in range(n):
    ans += sum(B[i])
    ans %= mod
print(ans)
### BUGGY CODE ###

n_list = list(input())
n_len_o = len(n_list)
#print(n_list)
a = 0
while(1):
  flag = "ng"
  n_len = len(n_list)
  for i in range(a,n_len-1):
    if n_list[i] != n_list[i+1]:
      n_list.pop(i)
      n_list.pop(i)
      if a != 0:
        a = i - 1
      else:
        a = 0
      flag = "ok"
      break
  if flag == "ng":
    break
#print(n_list)
print(n_len_o-len(n_list))

### FIXED CODE ###

n_list = list(input())
n_len_o = len(n_list)
a = 0
while(1):
  flag = "ng"
  n_len = len(n_list)
  for i in range(a,n_len-1):
    if n_list[i] != n_list[i+1]:
      n_list.pop(i)
      n_list.pop(i)
      if i != 0:
        a = i - 1
      else:
        a = 0
      flag = "ok"
      break
  if flag == "ng":
    break
print(n_len_o-len(n_list))
### BUGGY CODE ###

a = int(input())
ans = 1
n = list(map(int, input().split()))
for i in range(a):
    ans = ans * n[i]
print(ans if ans<=10**18 else '-1')

### FIXED CODE ###

a = int(input())
ans = 1
n = list(map(int, input().split()))
for i in range(a):
    if ans <= 10**18:
        ans = ans * n[i]
    if n[i] == 0:
        ans = 0
        break
print(ans if ans <= 10**18 else -1)
### BUGGY CODE ###

def resolve():
	_ = int(input())
	A = sorted(list(map(int, input().split())))
	Y = 0
	while True:
		a = A[0]
		A = A[1:]
		if not a in A:
			Y+=1
		A = list(filter(lambda x: x%a>0, A))
		if len(A)<2:
			break
	print(Y+len(A))
resolve()

### FIXED CODE ###

from collections import defaultdict

def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	a_max = max(A)+1
	B = defaultdict(int)
	for i in range(N):
		a = A[i]
		if B[a]>1:
			B[a] = 2
		else:
			for j in range(a, a_max, a):
				B[j] += 1
	Y = 0
	for a in A:
		if B[a]==1:
			Y+=1
	print(Y)
resolve()
### BUGGY CODE ###

S = input()

count = 0

while True :
    length = len(S)
    S = S.replace("01", "")
    S = S.replace("10", "")
    if (length == len(S)) :
        break
    count += length - len(S)
print(count)

### FIXED CODE ###

S = input()

count = 0
index = -1

print(2 * min(S.count("0"), S.count("1")))
### BUGGY CODE ###



import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

uf = UnionFind()
tf = UnionFind()
n,k,l =  map(int, input().split())
dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.unite(x-1, y-1)  # (3)
for i in range(l):
    x,y =map(int, input().split())
    tf.unite(x-1, y-1)  # (3)
for i in range(n):
    for j in range(i+1,n):
        if uf.are_same(i,j) and tf.are_same(i,j):
            dp[i]+=1
            dp[j]+=1
print(" ".join(map(str, dp)))

### FIXED CODE ###

from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


D = defaultdict(int)
n,k,l =  map(int, input().split())
uf = UnionFind(n)
tf = UnionFind(n)

dp =[1]*n
for i in range(k):
    x,y =map(int, input().split())
    uf.union(x-1, y-1)  # (3)
for i in range(l):
    x,y =map(int, input().split())
    tf.union(x-1, y-1)  # (3)
tf.all_find()
uf.all_find()
D = defaultdict(int)
for r, t in zip(uf.par, tf.par):
    D[(r, t)] += 1
 
ans = [D[(r, t)] for r, t in zip(uf.par, tf.par)]
print(*ans, sep=' ')
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    dp = [[0]*(len(s)+1) for _ in range((len(t)+1))]
    ans = ""
    for i in range(len(t)):
        for j in range(len(s)):
            tmp1 = dp[i+1][j]
            tmp2 = dp[i][j+1]
            tmp3 = dp[i][j]
            if t[i] == s[j]:
                tmp3 += 1
            dp[i+1][j+1] = max(tmp1,tmp2,tmp3)
    i = len(t)
    j = len(s)
    for k in range(10**9):
        if i < 0 or j < 0:
            break
        if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
            ans += t[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
    # while i > 0 and j > 0:
    #     if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
    #         ans += t[i-1]
    #         i -= 1
    #         j -= 1
    #     elif dp[i-1][j] == dp[i][j]:
    #         i -= 1
    #     else:
    #         j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    t = input()
    dp = [[0]*(len(s)+1) for _ in range((len(t)+1))]
    ans = ""
    for i in range(len(t)):
        for j in range(len(s)):
            tmp1 = dp[i+1][j]
            tmp2 = dp[i][j+1]
            tmp3 = dp[i][j]
            if t[i] == s[j]:
                tmp3 += 1
            dp[i+1][j+1] = max(tmp1,tmp2,tmp3)
    i = len(t)
    j = len(s)
    while i > 0 and j > 0:
        if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
            ans += t[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
    print(ans[::-1])

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

n,k = map(int,input().split())
st = set([])
for i in range(k):
  x,y = map(int,input().split())
  for z in range(x,y+1):
    st.add(z)
ans = [1]
for i in range(1,n):
  s = 0
  for x in st:
    if i >= x:
      s = s + ans[i-x]
  ans.append(s % 998244353)   
  
print(ans[-1])  
  
  
    
  

### FIXED CODE ###

n,k = map(int,input().split())
st = []
for i in range(k):
  x,y = map(int,input().split())
  st.append((x,y))
total = [1]

for i in range(1,n):
  s = 0
  for (x,y) in st:
    if i > y:
      s = (s + total[i-x] - total[i-y-1]) % 998244353
    elif i >= x:
      s = (s + total[i-x]) % 998244353
  total.append((s+total[-1]) % 998244353)   
  
print((total[-1]-total[-2]) % 998244353)
### BUGGY CODE ###

#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
loop_start = 0
loop = 0
for i in range(n):
    ans.append(a[ans[i] - 1])
for j in ans:
    if j in ans[:loop_start] or j in ans[loop_start+1:]:
        break
    loop_start += 1
loop = ans[loop_start+1:].index(j) + 1
ans.clear()
ans = [1]
if k < loop_start:
    for l in range(k):
        ans.append(a[ans[l] - 1])
    print(ans[k])
else:
    for l in range(loop_start + loop):
        ans.append(a[ans[l] - 1])
    print(ans[((k-loop_start)%loop)+loop_start])


### FIXED CODE ###

#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
c = 1
for i in range(n):
    ans.append(a[ans[i] - 1])
b = ans.index(ans[n])
if k < b:
    for l in range(k):
        c = a[c - 1]
else:
    for l in range((k-b)%(n-b)+b):
        c = a[c - 1]
print(c)
### BUGGY CODE ###

def main():

    s = input()
    q = int(input())
    query = [input().split() for _ in range(q)]
    ctn = query.count(["1"]) % 2 == 1

    new_query = []
    flag = 0
    for q in query:
        if len(q) == 1:
            if flag == 0:
                flag = 1
            else:
                flag = 0
        else:
            new_query.append(q + [flag])

    for q in new_query:
        if q[-1] == 0:
            if q[1] == "1":
                s = q[2] + s
            else:
                s = s + q[2]
        else:
            if q[1] == "1":
                s = s + q[2]
            else:
                s = q[2] + s

    if ctn:
        print(s[::-1])
    else:
        print(s)

main()

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(int(input()) for i in range(N))
for i in range(N):
    p= A[i]

    M = max(A)
    del A[i]
    MM = max(A)
    if M == MM:
        print(M)
    else:
        print(MM)
    A.insert(i,p)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
B= sorted(A)

for i in range(N):
    if A[i] == B[N-1]:
        ans = B[N-2]
        print(ans)
    else:
        print(B[N-1])
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
ans=1
for x in a: ans*=x
if ans>1e18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
ans=1
for x in a:
    ans*=x
    if ans>1e18:
        break
if a.count(0)>0:
    print(0)
elif ans>1e18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

s = list(input())
q = int(input())
flip = False
for i in range(q):
    tfc = input()
    if tfc[0] == '1':
        flip = not flip
    else:
        if flip:
            if tfc[2] == '1':
                s.append(tfc[4])
            else:
                ｓ.insert(0, tfc[4])
        else:
            if tfc[2] == '1':
                ｓ.insert(0, tfc[4])
            else:
                s.append(tfc[4])
if flip:
    s.reverse()
print("".join(s))

### FIXED CODE ###

s = list(input())
q = int(input())
ss = list()
flip = False
for i in range(q):
    tfc = input()
    if tfc[0] == '1':
        flip = not flip
    else:
        if flip:
            if tfc[2] == '1':
                s.append(tfc[4])
            else:
                ss.append(tfc[4])
        else:
            if tfc[2] == '1':
                ss.append(tfc[4])
            else:
                s.append(tfc[4])
ss.reverse()
s = ss + s
if flip:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(H + 1):
    for a, b in ab:
        if i - a < 0:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i - a] + b)
print(dp[H])


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(H + 1):
    for a, b in ab:
        if i - a < 0:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i - a] + b)
print(dp[H])
### BUGGY CODE ###

N=int(input())

import math
factN=math.factorial(N)
count=0
for i in range(1, factN+1):
    if factN%i==0:
        count+=1
    else:
        count=count

count=count%(10**9+7)
print(count)


### FIXED CODE ###

def pfn(N):
    factor=[]
    N=int(N)
    if N==1:
        return []
    else:
        for num in range(2, N+1):
            while N % num==0:
                N //=num
                factor.append(num)
        return factor
            
N=int(input())
factor=[]
for i in range(1, N+1):
    factor+=pfn(i)
    
p=1
factor_set=list(set(factor))
for x in factor_set:
    p*=factor.count(x)+1
    
print(p%(10**9+7))
### BUGGY CODE ###

import math
n=int(input())
a=list(map(int, input().split()))
count=0
for i in range(1,n+1):
    for j in range (len(a)):
        if a[j] == i:
            count += 1
    else:
        print(count)
        count = 0

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split()))
ct=collections.Counter(a)
for i in range(n):
    print(ct[i+1])
### BUGGY CODE ###

import sys
from collections import deque

s = list(sys.stdin.readline().rstrip())
q = int(sys.stdin.readline())
s = deque(s)

for _ in range(q):
    query = sys.stdin.readline().split()
    if len(query) == 1:
        s.reverse()
    elif query[1] == '1':
        s.appendleft(query[2])
    else:
        s.append(query[2])

print(''.join(s))


### FIXED CODE ###

import sys
from collections import deque

s = list(sys.stdin.readline().rstrip())
q = int(sys.stdin.readline())
head = 0
s = deque(s)

for _ in range(q):
    query = sys.stdin.readline().split()
    if len(query) == 1:
        head = 1 if head == 0 else 0
    elif (query[1] == '1' and head == 1) or (query[1] == '2' and head == 0):
        s.append(query[2])
    else:
        s.appendleft(query[2])

if head == 1:
    s.reverse()

print(''.join(s))