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

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

#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b,c in ab:
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque([])
    q.append([v,p])
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=dis_l[V-1]+v1
            dis_l[v0-1]=dis
            q.append([v0,V])
            break
        else:
            q.pop()
    return dis_l


log=Graph(uvw)
ans=dfs(log,1,-1)

for i in ans:
    if i%2==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q.pop()
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))

    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')
### BUGGY CODE ###

def main():
    n=int(input())
    m=(n-1)//2+2
    x=tuple(map(int,input().split()))
    x = (0,) + x + (0,)
    for i in range(n):
        print(sorted(x[:i+1]+x[i+2:])[m])
main()

### FIXED CODE ###

# ABC094C - Many Medians (ARC095C)
def main():
    n = int(input())
    x = list(map(int, input().split()))
    # 偶数個の数から一つ数を取り除いたものの中央値はl,hのいずれか.
    l, h = sorted(x)[n // 2 - 1 : n // 2 + 1]
    ans = [h if e <= l else l for e in x] # l以下の値を取り除いたならば中央値はh
    print("\n".join(map(str, ans)))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = []
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            hw[h][w] = 0
            b.append([h, w])
        else:
            hw[h][w] = 1001

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
while len(b) > 0:
    h, w = b.pop(0)
    for y, x in d:
        nh, nw = h+y, w+x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == 1001:
            hw[nh][nw] = hw[h][w]+1
            b.append([nh, nw])
            if hw[nh][nw] > ans:
                ans = hw[nh][nw]
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.popleft()
    d += 1
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d])
            if ans < d:
                ans = d
            hw[nh][nw] = "#"
print(ans)
### BUGGY CODE ###

import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

dp=np.zeros((n+1,w+1),np.int64)
# dp[i][j]:重さjを超えないようにしながらi個目までの商品を取るか取らないか選んだ時の価値の最大
# dp[i][0]=0,dp[0][j]=0,dp[n][inf]=sum(v) 求めるのはdp[n][w]
# 重さの小さい方から探索
for j in range(1,w+1):
      for i in range(1,n+1):
            m1=dp[i-1][j]
            m2=dp[i-1][j-wv[i-1][0]]+wv[i-1][1] if j-wv[i-1][0]>=0 else 0
            dp[i][j]=max(m1,m2)
            
print(dp[n][w])

### FIXED CODE ###

import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1,np.int64)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])
### BUGGY CODE ###

#E問題
from bisect import bisect_left

N = int(input())
A = [int(input()) for i in range(N)]
B = [0]
for i in range(N):
    if i == 0:
        B[0]=A[i]
    else:
        if B[0] >= A[i]:
            B.insert(0,A[i])
        else:
            index = bisect_left(B,A[i])-1
            B[index] = A[i]
b=len(B)
print(b)

### FIXED CODE ###

#E問題
import heapq
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
A = A[::-1]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        li = bisect.bisect_right(C,A[i])
        if li == len(C):
            C.append(A[i])
        else:
            C[li] = A[i]
    
print(len(C))
### BUGGY CODE ###

#B-Frog2
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0

for i in range(1,n):
    
    for j in range(1,1+k):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
            
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
def ch_min(a,b):
    if a>b:
        return b
    
    return a
def solve():
    dp=[float('inf')]*n
    dp[0]=0

    for i in range(1,n):
    
        for j in range(1,1+k):
            if i-j>=0:
                dp[i]=ch_min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
                
                if dp[i]==0:
                    break
                
    print(dp[-1])
    

solve()
### BUGGY CODE ###

def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  for i in range(-4000,4001,1):
    for j in range(-4000,4001,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()

### FIXED CODE ###

def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  AB = A+B
  AC = A+C
  for i in range(-AC,AC,1):
    for j in range(-AB,AB,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0] = 0
mask1 = (1 << 10) - 1

for h in hhh:
    ndp = defaultdict(lambda: INF)
    h_key = h << 10
    for changed_prev_h, operate in dp.items():
        changed = changed_prev_h & mask1
        prev_h = changed_prev_h >> 10
        if h == prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
        elif h > prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate + h - prev_h)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
        else:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
    dp = ndp
print(min(dp.values()))


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0] = 0
mask1 = (1 << 10) - 1
mask2 = ((1 << 63) - 1) ^ mask1

for h in hhh:
    ndp = defaultdict(lambda: INF)
    h_key = h << 10
    for changed_prev_h, operate in dp.items():
        changed = changed_prev_h & mask1
        prev_h = changed_prev_h >> 10
        if h == prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
        elif h > prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate + h - prev_h)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
        else:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
    # print(h)
    # print(dict(dp))
    # print(dict(ndp))
    dp = ndp
print(min(dp.values()))
### BUGGY CODE ###


def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().rstrip().split()]

sum = 0

for i in range(N):
  for j in range(N-1-i):
    sum += A[i]*A[j+1+i]


ans = sum % (10**9+7)
print(ans) 

### FIXED CODE ###

from itertools import accumulate
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
Ac = list(accumulate(A))

ans = 0
for i in range(N):
  ans += A[i]*(Ac[-1]-Ac[i])
  ans = ans%MOD
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H
dp = [0] * (N + 1)
dp[1] = 0
dp[2] = abs(H[2] - H[1])

for i in range(3, N+1):
    dp[i] = 1000000000
    for j in range(max(1, i - K), i):
        dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]))
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H
dp = [0] * (N + 1)
dp[1] = 0
dp[2] = abs(H[2] - H[1])

for i in range(3, N+1):
    dp[i] = dp[i - 1] + abs(H[i] - H[i - 1])
    for j in range(1, K + 1):
        if i - j <= 0:
            break
        dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
print(dp[N])
### BUGGY CODE ###

S=input()
ans=0
for i in range(len(S)//2+1):
	ans += S.count('10')
	S = S.replace('10','')
	ans += S.count('01')
	S = S.replace('01','')
print(2*ans)

### FIXED CODE ###

S=input()
num0 = S.count('0')
num1 = S.count('1')
ans = 2*min(num0,num1)
print(ans)
### BUGGY CODE ###

import bisect
from itertools import accumulate
n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
cnt = 0
for i in range(m):
    b, c = map(int,input().split())
    bi = bisect.bisect(a, c)
    mb = min(bi, b)
    if mb <= 0:
        continue
    a += [c]*mb
    cnt += mb
a.sort()
ac = list(accumulate(a))
if cnt == 0:
    print(ac[-1])
else:
    print(ac[-1] - ac[cnt-1])

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(min(b, n-idx)):
        if a[idx+i] < c:
            continue
        else:
            ad += c*i
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    ad += c*min(b, n-idx)
    idx += min(b, n-idx)
print(ad + sum(a[idx:]))
### BUGGY CODE ###

from collections import Counter
n,k,*a = map(int,open(0).read().split())
a = Counter(a)
ans = 0
for i in range(max(0,len(a)-k)):
  ans += a.most_common()[-1-i][1]
print(ans)

### FIXED CODE ###

n,k,*a = map(int,open(0).read().split())
b = {}
for i in a:
  if i in b:
    b[i] += 1
  else:
    b[i] = 1
ans = 0
a = sorted(list(b.values()))
for i in range(max(0,len(a)-k)):
  ans += a[i]
print(ans)
### BUGGY CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
if not 2 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        if not ((i-1 in A) or (i-2 in A)):
            memo[i] = (memo[i - 1] + memo[i - 2])
        elif i-1 in A:
            memo[i] = memo[i - 2]
        elif i-2 in A:
            memo[i] = memo[i - 1]
        elif (i-1 in A) and (i-2 in A):
            print(0)
            sys.exit()
print(memo[-1] % lim)


### FIXED CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
memo = [0] * (N+1)
memo[0]=1

if not 1 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        memo[i] = (memo[i - 1] + memo[i - 2]) % lim
print(memo[-1])
### BUGGY CODE ###

import math
import numpy as np
from functools import reduce

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

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

K = int(input())

ans = 0

for a in range(1,K+1) :
    for b in range(1,K+1) :
        for c in range(1,K+1) :
            s = np.gcd.reduce([a, b, c])
            ans += s

print(ans)

### FIXED CODE ###

from math import gcd

K = int(input())

ans = 0

for a in range(1,K+1) :
    for b in range(1,K+1) :
        X = gcd(a, b)
        for c in range(1,K+1) :
           Y = gcd(X, c)
           ans += Y

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

N = int(input())
ans = 1
for num in range(1, N+1):
  ans *= num
print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
ans = 1
for num in range(1, N+1):
  ans = (ans*num)%(10**9+7)
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for kx in range(0, k+1):
    for ky in range(0, k+1):
        kz = s - kx -ky
        if 0 <= kz <= k and kx + ky + kz == s:
            count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for kx in range(0, k+1):
    for ky in range(0, k+1):
        kz = s - kx -ky
        if 0 <= kz <= k and kx + ky + kz == s:
            count += 1
print(count)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = [list(input()) for i in range(N)]
T = [[""] * (N*2) for i in range(2*N)]
for i in range(2*N):
    if i < N:
        T[i] = S[i] + S[i]
    else:
        T[i] = S[i - N] + S[i-N]
ans = 0
s = np.array(T)
for A in range(N):
    for B in range(N):
        tmp = s[A:A+N, B:B+N]
        if (tmp != tmp.T).any() == False:
            ans += 1


print(ans)


### FIXED CODE ###

import collections
import sys
import numpy as np
input = sys.stdin.readline
table = collections.defaultdict(set)
N = int(input())
S = [list(input().rstrip()) for i in range(N)]
T = [[""] * (N*2) for i in range(2*N)]
table2 = [[set() for j in range(N)] for i in range(N)]

for i in range(2*N):
    if i < N:
        T[i] = S[i] + S[i]
    else:
        T[i] = S[i - N] + S[i-N]
ans = 0
T = np.array(T)
for i in range(N):
    tmp = T[i:i+N, N-1-i:2*N-1-i]

    if (tmp == tmp.T).all():
        ans += N - (N // 2)

    tmp = T[i+1:i+N+1, N-1-i:2*N-1-i]

    if (tmp == tmp.T).all():
        ans += N // 2
print(ans)
### BUGGY CODE ###


N = int(input())
s = []
for n in range(N):
	line0 = input()
	line = ''.join(sorted(line0))
	s.append(line)

ans = 0
for n in range(len(s)):
	for m in range(n+1,len(s)):
		if s[n]==s[m]:
			ans += 1
print(ans)


### FIXED CODE ###


N = int(input())

data = {}
for n in range(N):
	s0 = input()
	s = ''.join(sorted(s0))
	if s in data:
		data[s] += 1
	else:
		data[s] = 1

ans = 0
for n in data.values():
	ans += (n-1)*n//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
#print(n,a)
res = 0
for i in range(n):
  for j in range(i+1,n):
    d = j-i
    h = a[i] + a[j]
    if d == h :
      res += 1

print(res)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 0
ia = []
ja = []
dia={}
dja={}
for i in range(n):
  dia[i+a[i]] = dia.get(i+a[i],0)+1
  dja[i-a[i]] = dja.get(i-a[i],0)+1
ans = 0
for di,nmi in dia.items():
  nmj = dja.get(di,0)
  ans += nmi*nmj

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

S = input()
Q = int(input())
S = [s for s in S]

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

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
reverse_cnt = 0
s = deque([i for i in S])

for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt += 1
    else:
        if query[1] == "1":
            if reverse_cnt % 2 == 0:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if reverse_cnt % 2 == 0:
                s.append(query[2])
            else:
                s.appendleft(query[2])

if reverse_cnt % 2 == 0:
    while s:
        print(s.popleft(), end="")
else:
     while s:
        print(s.pop(), end="")
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [0]*(w+1)

for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

print(max(dp))

### FIXED CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [0]*(w+1)

for i in range(n):
    for j in range(w, wv[i][0]-1, -1):
        dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])

print(max(dp))
### BUGGY CODE ###

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

while True:
    if (H + W == 0) : break
    
    for i in range(H):
        print('#' * W)

    print()



### FIXED CODE ###

while True:
    H, W = map(int, input().split())

    if (H + W == 0) : break
    
    for i in range(H):
        print('#' * W)

    print()
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import math
    import collections
    N = int(input())

    A_list = [int(item) for item in input().split()]    
    A_list.sort()

    cnt = 0

    while len(A_list) > 0:
        # print(A_list)
        cnt += 1
        temp = A_list[0]
        del A_list[0]

        is_same = False
        for item in A_list[:]:
            if item == temp:
                is_same = True
            if item % temp == 0:
                A_list.remove(item)
        
        if is_same:
            cnt -= 1

    print(cnt)





if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(item) for item in input().split()]

    A_list.sort()


    dp = [0 for item in range(A_list[-1]+1)]
    for item in A_list:

        temp = item
        while temp <= A_list[-1]:
            dp[temp] += 1
            temp += item

    cnt = 0
    for item in A_list:
        if dp[item] == 1:
            cnt += 1
    print(cnt)

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

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
#            KARI = []
            DP[i][j]=DP[i-1][j]
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
            r = j // Magic[i][0]
            for k in range(r):
                DP[i][j]=min(DP[i][j],(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

                
            
        


### FIXED CODE ###

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))
### BUGGY CODE ###

s = input()
q = int(input())
x = 0
for i in range(q):
    query = input()
    if query[0] == '1':
        x += 1
    else :
        if (x + int(query[2])) % 2 == 0:
            s = s + query[-1]
        else :
            s = query[-1] + s
if x % 2 == 0:
    print(s)
else :
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
flag = True
for i in range(q):
    x = input()
    if x == '1':
        flag = not flag
    else :
        if x[2] == '1' and flag :
            s.appendleft(x[4])
        elif x[2] == '2' and not flag :
            s.appendleft(x[4])
        else :
            s.append(x[4])
if flag:
    for i in s :
        print(i, end='')
else :
    for i in range(1, len(s)+1):
        print(s[-i], end='')
print('')