Harryxun/stf_run huggingface dataset:
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

dp = [[0 for w_sum in range(W)] for i in range(N)]

for i in range(N):
    for w_sum in range(W):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])


### FIXED CODE ###

# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])
import math

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

print(a * b / math.gcd(a,b))

### FIXED CODE ###

import math
def gcd (a,b):
    n = min(a,b)
    m = max(a,b)
    
    b = m % n
    
    while b > 0:
        m = n
        n = b
        b = m % n
    
    return n

a, b = map(int,input().split())
c = math.floor(a * b / gcd(a,b))
print(c)
def tax(p,x):
    return p*(100+x) // 100
def solve(X,Y,S):
    for a in range(1,S):
        for b in range(1,S):
            sum = tax(a,X)+tax(b,X)
            if sum == S: 
            if sum > S:
                break
    return best 
while True:
    X,Y,S = map(int, input().strip().split('')) 
    if X == 0:
        break
print(solve(X,Y,S))


### FIXED CODE ###

def tax(p,x):
    return p*(100+x) // 100

def solve(X,Y,S):
    A=0
    sum=0
    NS=0
    for a in range(1,S):
        for b in range(1,S-a+1):
            sum = tax(a,X)+tax(b,X)
            if sum == S:
                NS = tax(a,Y)+tax(b,Y)
                if NS > A:
                    A = NS
            if sum > S:
                break
    return A 

while True:
    X,Y,S = map(int, input().split()) 
    if X == 0:
        break
    print(solve(X,Y,S))
a, b, c, d = map(int,input().split())


if (-(-c // b)) >= (-(-a // d):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a, b, c, d = map(int,input().split())

tk_count = -(-c // b)
ao_count = -(-a // d)

if tk_count <= ao_count:
    print('Yes')
else:
    print('No')
N,A,B=map(int,input().split())
for i in range(1,N+1):
    ans=i%10+i/10%10+i/100%10+i/1000%10+i/10000%10
    if A<=ans and ans<=B:
        total.append(ans)
print(sum(total))

### FIXED CODE ###

N,A,B=map(int,input().split())
total=[]
for i in range(1,N+1):
    ans=i%10+i//10%10+i//100%10+i//1000%10+i//10000%10
    if A<=ans and ans<=B:
        total.append(i)
print(sum(total))
a,b,c = map(int, input().sprit())
ans = c-(a-b)

if ans < 0:
  print(0)
else:
  print(ans)

### FIXED CODE ###

a,b,c = map(int, input().split())
ans = c-(a-b)

if ans < 0:
  print(0)
else:
  print(ans)
s=input()
c=0
range(i, s):
    if i=="1":
        c++

print(c)

### FIXED CODE ###

s=str(input())
c=0
for i in range(0,3):
    if s[i]=="1":
        c+=1

print(c)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

al = [0, 5] + [0] * 49
bl = [0, 3] + [0] * 49


def solve2(ans, x, idx, cnt):
    if idx == 1:
        return ans + (0, 0, 1, 2, 3, 3)[x]
    if x >= al[idx - 1] + 1:
        ans += bl[idx - 1]
        x -= al[idx - 1] + 1
        if x >= 1:
            ans += 1
            x -= 1
    else:
        x -= 1
        if x <= 0:
            return ans
    return solve2(ans, x, idx - 1, cnt)


def solve():
    n, x = map(int, input().split())
    for i in range(2, n + 1):
        al[i] = al[i - 1] * 2 + 3
        bl[i] = bl[i - 1] * 2 + 1
    ans = solve2(0, x, n, 0)
    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

al = [0, 5] + [0] * 49
bl = [0, 3] + [0] * 49


def solve2(ans, x, idx, cnt):
    if idx == 1:
        if x >= 5:
            return ans + 3
        return ans + (0, 0, 1, 2, 3, 3)[x]
    if x >= al[idx - 1] + 1:
        ans += bl[idx - 1]
        x -= al[idx - 1] + 1
        if x >= 1:
            ans += 1
            x -= 1
    else:
        x -= 1
        if x <= 0:
            return ans
    return solve2(ans, x, idx - 1, cnt)


def solve(n, x):
    for i in range(2, n + 1):
        al[i] = al[i - 1] * 2 + 3
        bl[i] = bl[i - 1] * 2 + 1
    ans = solve2(0, x, n, 0)
    print(ans)


if __name__ == "__main__":
    n, x = map(int, input().split())
    solve(n, x)
N = int(input())
R = int(input())
if N < 10:
    print(R + 100*(10 - N))
else:
    print(R)

### FIXED CODE ###

N,R = map(int,input().split())
if N < 10:
    print(R + 100*(10 - N))
else:
    print(R)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def solve(string):
    string = string.split("\n")
    n, m = map(int, string[0].split())
    ans = {i + 1 for i in range(m)}
    for loves in string[1:]:
        ans &= set(map(int, loves.split()[1:]))
    return str(len(ans))


if __name__ == '__main__':
    base = input()
    n, m = map(int, base)
    tmp = [base]
    for _ in range(n):
        tmp.append(input())
    print(solve('\n'.join(tmp)))


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def solve(string):
    string = string.split("\n")
    n, m = map(int, string[0].split())
    ans = {i + 1 for i in range(m)}
    for loves in string[1:]:
        ans &= set(map(int, loves.split()[1:]))
    return str(len(ans))


if __name__ == '__main__':
    base = input()
    n, m = map(int, base.split())
    tmp = [base]
    for _ in range(n):
        tmp.append(input())
    print(solve('\n'.join(tmp)))
A, B, X = map(int, raw_input().split())
print("YES" if A<=X<=A+B else "NO")

### FIXED CODE ###

A, B, X = map(int, input().split())
print("YES" if A<=X<=A+B else "NO")
n, t = map(int, input().split()))
A = list(map(int, input().split()))

ans = 0
max_diff = 0
min_a = A[0]
for a in A:
    min_a = min(min_a, a)
    if (a - min_a) == max_diff:
        ans += 1
    elif (a - min_a) > max_diff:
        ans = 1
        max_diff = (a - min_a)
print(ans)


### FIXED CODE ###

# f = open('input', 'r')
# n, t = map(int, f.readline().split())
# A = list(map(int, f.readline().split()))
n, t = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
max_diff = 0
min_a = A[0]
for a in A:
    min_a = min(min_a, a)
    if (a - min_a) == max_diff:
        ans += 1
    elif (a - min_a) > max_diff:
        ans = 1
        max_diff = (a - min_a)
print(ans)
k = int(input())
sum = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      sum += gcd(a,b,c)
print(sum)

### FIXED CODE ###

k = int(input())
from math import gcd
sum = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      sum += gcd(a, gcd(b,c))
print(sum)
A,B,C = map(int,input().split())

if A == B:
  print(C)
else if A == C:
  print(B)
else:
  print(A)

### FIXED CODE ###

import sys as cghavcjhcbejwcbbsmbcjsdbcjdcadhbcjbdsjjcdjabjadbjsbcjdsbcsbcnsbcdnbcmbcmdabcdbjwhckfmknvskndleccdajbubcrjhebuoqbjhbjcdnaaayruegfubefruebhvy38bjhbvvbhcba
A,B,C = map(int,cghavcjhcbejwcbbsmbcjsdbcjdcadhbcjbdsjjcdjabjadbjsbcjdsbcsbcnsbcdnbcmbcmdabcdbjwhckfmknvskndleccdajbubcrjhebuoqbjhbjcdnaaayruegfubefruebhvy38bjhbvvbhcba.stdin.readline().split())

if A == B:
  print(C)
elif A == C:
  print(B)
else:
  print(A)
n,a,b,c,d = map(int,input().split())
s = input()

can_reach = True
bef = False
for i in range(a,c):
    if s[i] == "#":
        if bef:
            can_reach = False
        else:
            bef = True
    else:
        bef = False

bef = False
for i in range(b,d):
    if s[i] == "#":
        if bef == True:
            can_reach = False
        else:
            bef = True
    else:
        bef = False

if can_reach:
    if c < d:
        print("Yes")
    else:
        can_over = False
        bef1 = False
        bef2 = False
        for i in range(b-1,c+1):
            if s[i] == ".":
                if bef1:
                    if bef2:
                        can_over = True
                    else:
                        bef2 = True
                else:
                    bef1 = True
            else:
                bef1 = False
                bef2 = False
        if can_over:
            print("Yes")
        else:
            print("No")
else:
    print("No")





### FIXED CODE ###

import copy
N,A,B,C,D = map(int,input().split())
S = input()

for i in range(A,max(C,D)-1):
    if S[i:i+2] == "##":
        print("No")
        exit(0)

if C > D:
    flag = False
    for i in range(B-1,D):
        if S[i-1:i + 2] == "...":
            flag = True
            break

    if flag == False:
        print("No")
        exit(0)

print("Yes")
import math
N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=1
gcd=A[0]
for i in range(1,N):
    a=A[i]
    b=math.gcd(a,gcd)
    temp=gcd
    gcd=temp*a//b
    ans=ans*(a//b)+temp//b
    ans%=MOD
print(ans)

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=1
gcd=A[0]
for i in range(1,N):
    a=A[i]
    b=fractions.gcd(a,gcd)
    temp=gcd
    gcd=temp*a//b
    ans=ans*(a//b)+temp//b
    ans%=MOD
print(ans)
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(a[left + i])
    for j in range(n2):
        R.append(a[mid + j])
    L.append(500001)
    R.append(500001)
    i=0
    j=0
    for k in range(left, right):
        counter += 1
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergeSort(a, left, right):
    if(left+1 < right):
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

mergeSort(a, 0, n)
#print(" ".join([str(i) for i in a]))
print(*a)
print(counter)



### FIXED CODE ###

import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [sentinel]
    R = a[mid:right] + [sentinel]
    i,j = 0,0
    for k in range(left, right):
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    counter += right - left
def mergeSort(a, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)


n = int(input())
a = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

t = n*(n-1)//2

import bisect
import math
def ok(x):
    # x以上になる組み合わせがt-k+1個以上ある
    cnt = 0
    for a in A:
        if a > 0:
            b = math.ceil(x/a)
            c = n - bisect.bisect_left(A, b)
            if a >= b:
                c -= 1
        elif a == 0:
            if x <= 0:
                c = n-1
        else:
            b = math.floor(x/a)
            c = bisect.bisect_right(A, b)
            if a <= b:
                c -= 1
        cnt += c
    cnt //= 2
    if cnt >= t-k+1:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

### FIXED CODE ###

import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), np.int64)
A = np.sort(A)

P = A[A>0]
Z = A[A==0]
N = A[A<0]

#t = n*(n-1)//2

def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    #cnt += np.searchsorted(A, np.ceil(x/P), side='right').sum()
    cnt += np.searchsorted(A, x//P, side='right').sum()
    #cnt += n-np.searchsorted(A, np.floor(x/N), side='left').sum()
    cnt += (n-np.searchsorted(A, (-x-1)//(-N), side='right')).sum()
    if x >= 0:
        cnt += len(Z)*n
    cnt -= np.count_nonzero(A*A <= x)
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)
import math
a,b,X = map(int, input().split())
x = X/(a**2)

if x<=b/2:
        t = 2*a*x/(b**2)
        print(90-math.degrees(math.atan(t)))

else:
        if a**2*b==x:
                print(0)
        else:
                t = a/(2*b-2*x)
                print(90-math.degrees(math.atan(t)))


### FIXED CODE ###

import math
a,b,X = map(int, input().split())
x = X/(a**2)

if x<=b/2:
        t = 2*a*x/(b**2)
        print(90-math.degrees(math.atan(t)))

else:
        if a**2*b==X:
                print(0)
        else:
                t = a/(2*b-2*x)
                print(90-math.degrees(math.atan(t)))
import math
n = int(input())
s = int(input())
if n == s:
  print(n+1)
  exit()
ru = math.ceil(math.sqrt(n))+1
for i in range(2,ru+1):
  b = n+0
  a = []
  while b:
    a.append(b%i)
    b//=i
  kota = sum(a)
  if s == kota:
    print(i)
    exit()
for i in range(ru,0,-1):
  q = s-i
  if q <0:
    continue
  c = (n-q)// i
  b = n+0
  a = []
  while b:
    a.append(b%c)
    b//=c
  kota = sum(a)
  if kota == s:
    print(c)
    exit()
print(-1)

### FIXED CODE ###

import math
n = int(input())
s = int(input())
if n == s:
  print(n+1)
  exit()
ru = math.ceil(math.sqrt(n))+1
for i in range(2,ru+1):
  b = n+0
  a = 0
  while b:
    a +=b%i
    b//=i
  if s == a:
    print(i)
    exit()
for i in range(ru,0,-1):
  q = s-i
  if q <0:
    continue
  c = (n-q)// i
  if c <= ru-1:
    continue
  b = n+0
  a = 0
  while b:
    a+=b%c
    b//=c
  if a == s:
    print(c)
    exit()
print(-1)
n,l=map(int,input().split())
t=sorted([input() for i in range(n)])
print(*t,sep="")

### FIXED CODE ###

a, b, c = map(int, input().split())
if((a+b+c)-17 == 0):
	print("YES")
else:
	print("NO")
a, b = (int(x) for x in raw_input().split)
print "error" if a + b > 9 else str(a+b)

### FIXED CODE ###

a, b = (int(x) for x in raw_input().split())
print "error" if a + b > 9 else str(a+b)
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num)
    
    return cnt


while True:
    mid = (left + right) // 2
    tmp = count(mid)
    if tmp == K:
        break
    elif tmp > K:
        if left == mid:
            mid += 1
            break
        left = mid
    else:
        right = mid

if mid == 0:
    print(mid)
    exit()

right = mid
while True:
    tmp = count(mid)
    if tmp == K and tmp != count(mid-1):
        print(mid)
        break
    elif tmp == K:
        right = mid
    else:
        left = mid
    mid = (left + right) // 2

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
S = input()

num_r = S.count('R')
ans = num_r

for i in range(num_r):
    if S[i] == 'R':
        ans -= 1

print(ans)
from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
M = int(input())
T = Counter([input() for _ in range(M)])
G = S-T
print(max([a for a in G.values()]))

### FIXED CODE ###

from collections import Counter
N = int(input())
blue = []
for _ in range(N):
    blue.append(input())
blue = Counter(blue)

M = int(input())
red = []
for _ in range(M):
    red.append(input())
red = Counter(red)

diff = blue - red
if len(diff)==0:
    print(0)
else:
    print(max(diff.values()))
N = int(input())
A = list(map(int,input().split()))

ans = 1
pm = 1

i = 0
tmp = []
while i < N:

    if i == 0:
        if A[i] <= A[i+1]:
            pm = 1
        else:
            pm = -1

        i += 1
    else:
        if pm*(A[i] - A[i-1]) >= 0:
            i += 1
            if pm == 0 and A[i] != A[i-1]:
                if A[i-1] < A[i]:
                    pm = 1
                else:
                    pm = -1
        else:
            i += 1
            if N <= i:
                ans += 1
                break

            if A[i-1] == A[i]:
                pm = 0
            elif A[i-1] < A[i]:
                pm = 1
            else:
                pm = -1

            ans += 1


print(ans)


### FIXED CODE ###

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

if N == 1:
    print(1)
    exit()
ans = 1
pm = 1

i = 0
tmp = []
while i < N:

    if i == 0:
        if A[i] <= A[i+1]:
            pm = 1
        else:
            pm = -1

        i += 1
    else:
        if pm*(A[i] - A[i-1]) >= 0:
            i += 1
            if pm == 0 and A[i] != A[i-1]:
                if A[i-1] < A[i]:
                    pm = 1
                else:
                    pm = -1
        else:
            i += 1
            if N <= i:
                ans += 1
                break

            if A[i-1] == A[i]:
                pm = 0
            elif A[i-1] < A[i]:
                pm = 1
            else:
                pm = -1

            ans += 1


print(ans)
x,a=[int(X) for x in input().split(' ')]
if x<a:
  print(0)
else:
  print(10)

### FIXED CODE ###

x,a=[int(x) for x in input().split(' ')]
if x<a:
  print(0)
else:
  print(10)
n = int(input())
s = list(map(int,input().split()))
print(*s[::-2],*s[n%2::2])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n % 2 == 0:
    a = a[::-2]+a[0::2]
else: a = a[::-2] +a[1::2]
print(*a,sep=" ")
import math
a,b,c,d = [int(i) for i in input().split()]

x = (c-a) ** 2
y = (d-b) ** 2

total = (x + y)

i = math.sqrt(total)

print(i)

### FIXED CODE ###

import math

x,y,X,Y = [float(i) for i in input().split()]
print(math.sqrt((x-X)**2 + (y-Y)**2))
n = int(input())

q = deque()
for i in range(n):
    cmd = input().strip()
    if cmd == 'deleteFirst':
        q.popleft()
        continue
    if cmd == 'deleteLast':
        q.pop()
        continue
    cmd, x = cmd.split()
    x = int(x)
    if cmd == 'insert':
        q.appendleft(x)
        continue
    if cmd == 'delete':
        try:
            q.remove(x)
        except:
            pass
        continue

print(' '.join(q))

### FIXED CODE ###

import sys
from collections import deque

n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    cmd = sys.stdin.readline()[:-1]
    if cmd[0] == 'i':
        q.appendleft(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.remove(cmd[7:])
        except:
            pass
    elif cmd[6] == 'F':
        q.popleft()
    else:
        q.pop()

print(' '.join(q))
H, W, K = map(int, input().split())
dp = [[0 for i in range(W)] for j in range(H+1)]
mod = 10**9+7
dp[0][0] = 1

for k in range(H):
    for i in range(2**(W-1)):
        b = format(i, "0{}b".format(W-1))
        flag = 1
        for j in range(len(b)-1):
            if b[j+1] == "1" and b[j] == "1":
                flag = 0
                break
        if flag == 0:
            continue

        for j in range(len(b)):
            if flag == 0:
                flag = 1
                continue
            if b[j] == "1":
                dp[k+1][j+1] += dp[k][j]
                dp[k+1][j] += dp[k][j+1]
                dp[k+1][j+1] %= mod
                dp[k+1][j] %= mod
                flag = 0
            else:
                dp[k+1][j] += dp[k][j]
                dp[k+1][j] %= mod
                if j == len(b)-1:
                    dp[k+1][j+1] += dp[k][j+1]
                    dp[k+1][j+1] %= mod
                  
print(dp[H][K-1])


### FIXED CODE ###

H, W, K = map(int, input().split())
dp = [[0 for i in range(W)] for j in range(H+1)]
mod = 10**9+7
dp[0][0] = 1

if W == 1:
    print(1)
else:
    for k in range(H):
        for i in range(2**(W-1)):
            b = format(i, "0{}b".format(W-1))
            flag = 1
            for j in range(len(b)-1):
                if b[j+1] == "1" and b[j] == "1":
                    flag = 0
                    break
            if flag == 0:
                continue

            for j in range(len(b)):
                if flag == 0:
                    flag = 1
                    continue
                if b[j] == "1":
                    dp[k+1][j+1] += dp[k][j]
                    dp[k+1][j] += dp[k][j+1]
                    dp[k+1][j+1] %= mod
                    dp[k+1][j] %= mod
                    flag = 0
                else:
                    dp[k+1][j] += dp[k][j]
                    dp[k+1][j] %= mod
            if b[-1] == "0":
                dp[k+1][-1] += dp[k][-1]
                dp[k+1][-1] %= mod
    print(dp[H][K-1])
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
x=[[],[],[]]
for i in range(n):x[i%3]+=i+1,
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
a=[-1]*n
p=a[:]
p[0]=0
s=[0]
c=[1,0]
while s:
    v=s.pop()
    for w in e[v]:
        if p[w]<0:
            p[w]=p[v]^1
            c[p[w]]+=1
            s+=w,
if min(c)<=len(x[2]):
    x[0]+=x[1]
    f=c[0]<=len(x[2])
    for i,v in enumerate(p):a[i]=x[(v==f)-1].pop()
else:
    for i,v in enumerate(p):a[i]=x[v if x[v]else-1].pop()
print(*a)

### FIXED CODE ###

n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
x=[[],[],[]]
for i in range(n):
    x[i%3]+=i+1,
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
a=[-1]*n
p=a[:]
p[0]=0
s=[0]
c=[1,0]
while s:
    v=s.pop()
    for w in e[v]:
        if p[w]<0:
            p[w]=p[v]^1
            c[p[w]]+=1
            s+=w,
if min(c)<=n//3:
    x[0]+=x[1]
    f=c[0]<=n//3
    for i,v in enumerate(p):
        j=(v==f)-1
        a[i]=x[j if x[j]else-1].pop()
else:
    for i,v in enumerate(p):
        a[i]=x[v if x[v]else-1].pop()
print(*a)
A,B,K = map(int,input().split())
lists = list(range(A,B+1))
result = list(set(lists[:K] + lists[-K:]))
result.sort()
if K >= len(lists):
        for j in range(len(lists)):
                print(lists[j])
else:
        for i in range(len(result)):
                print(result[i])

### FIXED CODE ###

A,B,K = map(int,input().split())
if abs(B-A) < K:
    for i in range(A,B+1):
        print(i)
    exit()
min_list = list(range(A,A+K))
max_list = list(range(B-K+1,B+1))
lists = list(set(min_list) | set(max_list))
lists.sort()
for i in range(len(lists)):
    print(lists[i])
N, P = map(int, input().split())
d = list(map(int, input()))
ans =0
for k in range(0,N):
    for l in range(k+1,N+1):
        num = int("".join(map(str,d[k:l])))
        
        if num % P == 0:
            ans += 1

print(ans)


### FIXED CODE ###

S = list(map(str, input()))
q = int(input())
Q =[list(map(str, input().split())) for k in range(q)]
rev = False
f1 = []
f2 = []
def pls(n):
    global rev
    if n[0] == "1":
        rev = not rev
    else:
        if n[1] == "1":
            if rev:
                f2.append(n[2])
            else:
                f1.append(n[2])
        else:
            if rev:
                f1.append(n[2])
            else:
                f2.append(n[2])

for k in range(q):
    pls(Q[k])

if rev:
    S.reverse()
    f2.reverse()
    ans = f2 + S + f1
else:
    f1.reverse()
    ans = f1 + S + f2

print("".join(map(str, ans)))