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

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

items = [list(map(int, input().split())) for _ in range(N)]

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

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

print(dp[N][W])


### FIXED CODE ###

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

items = [list(map(int, input().split())) for _ in range(N)]

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

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

print(dp[N][W])
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
final=[0]*n

for i in range(1,n):

  mini=10**9+1



  if i<=k:
    x=i
  else:
    x=k
  for j in range(1,x+1):

     mini=min(mini,final[i-j]+abs(l[i]-l[i-j]))
  final[i]=mini
print(final[-1])


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
final=[0]*n
if k>=n:
  print(abs(l[n-1]-l[0]))
else:   
   for i in range(1,k+1):
      final[i]=abs(l[i]-l[0])
  
   for i in range(k+1,n):

      li=[abs(l[i]-l[ik])+final[ik] for ik in range(i-1,i-k-1,-1) ]
      final[i]=min(li)
   print(final[-1])
### BUGGY CODE ###

from statistics import mode
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1)
O = factorial(outside) % MOD

L = list(range(1, N+2))
l1 = 1
l2 = X

X %= MOD

for k in range(1, len(A)+1):
    l1 *= k
    l2 //= L[-k]
    if k > outside + 1:
        Y = pow((l1 * l2) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        Y = pow(l1 * l2 % MOD, MOD - 2, MOD)
        Y2 = pow((factorial(k-1)) * factorial(outside - k + 1) % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))


### FIXED CODE ###

from statistics import mode

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

# 階乗・逆元の値を保存
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1]*i % MOD)
    inverse.append((pow(factorial[i], MOD-2, MOD)))

# combination計算
def nCr(n, r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % MOD


print(N)
for i in range(2, N+2):
    print(int(nCr(N+1, i) - nCr(outside, i-1)) % MOD)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*(n)
m=1
for i in range(n):
    if i>=k:
        m*=l[i]
        if m//dp[i-k] > cur:
            print("Yes")
        else:
            print("No")
        dp[i]=m
        cur=m//dp[i-k]

    else:
        m*=l[i]
        cur=m
        dp[i]=m



### FIXED CODE ###

n,k = map(int,input().split())
a=list(map(int,input().split()))
 
for i in range(k,n):
    if(a[i] > a[i-k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [[[0,0,0] for _ in range(M+1)] for _ in range(2)]
    k = 0
    for s in S:
        k ^= 1
        sum__ = 0
        for i, t in enumerate(T):
            sum_ = sum(dp[k^1][i+1])%(10**9+7)
            dp[k][i+1] = [sum_, sum(dp[k][i][1:])%(10**9+7), sum__ + 1 if t == s else 0]
            sum__ = sum_
    res = (sum(dp[k][-1]) + 1)%(10**9+7)

    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

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

import sys
input = sys.stdin.readline
import copy

N=int(input())
S=input().strip()

SUB={""}
ANS=set()

for s in S:
    NSUB=copy.deepcopy(SUB)
    for t in SUB:
        x=t+s
        if len(x)<=2:
            NSUB.add(x)
        else:
            ANS.add(x)

    SUB=NSUB

print(len(ANS))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
S=input().strip()

SUB={""}
ANS=set()

for s in S:
    N=set()
    for t in SUB:
        x=t+s
        if len(x)<=2:
            N.add(x)
        else:
            ANS.add(x)

    SUB|=N

print(len(ANS))
### BUGGY CODE ###

s_l = list(input())
n = len(s_l)

# 公式解説参照
dp = [0]
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp.append(t)

ans = 0
for i in range(2019):
    m = dp.count(i)
    ans += m*(m-1)//2

print(ans)


### FIXED CODE ###

s_l = list(input())
n = len(s_l)

# 公式解説参照
dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

ans = 0
for val in dp_dict.values():
    ans += val*(val-1)//2

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

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

s = 1
for i in range(1,N):
    if P[i] <= min(P[0:i]):
        s = s +1
print(s)

### FIXED CODE ###

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

s = 1
m = P[0]
for i in range(1,N):
    if P[i] <= m:
        s = s +1
        m = P[i]
print(s)
### BUGGY CODE ###

N,K = map(int,input().split())
if(K==1 and N>1):
    print(int(0))
elif(N==0 and K>=1):
    print(int(0))
else:
    i = 0
    l = 100000000000000000
    r = []
    while(i==0):
        r.append(N)
        s = abs(N-K)
        if(l>s):
            l = s
        N = s
        if(N in r):
            i+=1
    print(l)

### FIXED CODE ###

N,K = map(int,input().split())
if(N==0):
    print(int(0))
else:
    r = N%K
    print(min(r,K-r))
### BUGGY CODE ###

from collections import defaultdict
from itertools import product, combinations

INF = float('inf')
def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return (None, prev), where prev is
        the table, whose (i, j)-element is the previous vertices in the shortest (i, j)-path
        Otherwise return (dist, prev), where dist is the table of the minimum cost
        between arbitrary vertex u, v in the given graph
    '''
    dist = {u: {v: INF for v in V} for u in V}
    prev = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; prev[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; prev[v][u] = v;
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                prev[i][j] = prev[k][j]
    for v in V:
        if dist[v][v] < 0: return None, prev
    return dist, prev

N, M, L = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c

dist, _ = floyd_warshall(V, E)
E_charge = defaultdict(dict)
for u, v in combinations(V, 2):
    if dist[u][v] <= L: E_charge[u][v] = 1; E_charge[v][u] = 1;
charge, _ = floyd_warshall(V, E_charge)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    n = charge[s-1][t-1]
    print(n - 1 if n != INF else -1)

### FIXED CODE ###

from itertools import product, combinations

INF = float('inf')
def floyd_warshall(E):
    N = len(E)
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for v in range(N):
        dist[v][v] = 0
        for u, c in E[v]: dist[v][u] = c
    for k in range(N):        
        for i, j in product(range(N), repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))
dist = floyd_warshall(E)

E_charge = [[] for _ in range(N)]
for u, v in combinations(range(N), 2):
    if dist[u][v] <= L:
        E_charge[u].append((v, 1))
        E_charge[v].append((u, 1))
charge = floyd_warshall(E_charge)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    n = charge[s-1][t-1]
    print(n - 1 if n != INF else -1)
### BUGGY CODE ###

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

ans=1
for i in range(n):
    ans*=a[i]
if ans>10**18:
    print(-1)
    exit()
print(ans)


### FIXED CODE ###

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

ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000)
n, m = map(int, input().split())
bridge = list(map(int, sys.stdin.read().split()))
total = n*(n-1)//2
ans =[total]
u = [i for i in range(n+1)]
size = [1 for i in range(n+1)]
rank = [1 for i in range(n+1)]
def check(x, y):
    return find(x) != find(y)

def find(x):
    if x == u[x]:
        return x
    else:
        return u[x]

for x , y in zip(bridge[-2::-2],bridge[::-2]):
    if check(x, y):
        X = u[x]
        Y = u[y]
        total -= size[X] * size[Y]
        ans += [total]
        if rank[X] == rank[Y]:
            X, Y = sorted([X,Y])
            u = [Y if i == X else i for i in u]
            rank =[x+1 if u[i] == u[Y] else x for i, x in enumerate(rank)]
        else:
            if rank[X] > rank[Y]:
                X, Y = sorted([X,Y])
            rank =[x+1 if u[i] == u[Y] else x for i, x in enumerate(rank)]
            u = [Y if i == u[X] else i for i in u]
        size[Y] += size[X]

    else:
        ans += [total]

print(*ans[-2::-1], sep="\n")

### FIXED CODE ###

import sys
n , m, *e = map(int,sys.stdin.read().split())
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)

def find(x):
    if u[x] < 0 :
        return x
    else:
        return find(u[x])

for x , y in zip(e[-2:1:-2],e[:1:-2]):
    x = find(x)
    y = find(y)
    x, y = sorted((x, y))
    if x != y:
        total -= u[x] * u[y]
        u[x] += u[y]
        u[y] = x
    ans += [total]

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A = np.array([int(input()) for i in range(Q)])
  
points = K - Q
for i in range(1, N+1):
  correct_num = len(np.where(A==i)[0])
  fin_point = points + correct_num
  
  if fin_point > 0:
    print("Yes")
  else:
    print("No")  

### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A = np.array([int(input()) for i in range(Q)])
  
points = np.full(N, K-Q)

for i in range(0, Q):
  points[A[i]-1] += 1
 
for i in points:
  if i > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

for i in range(n):
    s = s * a[i]
if s > 10 ** 18:
    s = -1
print(s)

### FIXED CODE ###

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

if 0 in a:
    s = 0
else:
    for i in range(n):
        s = s * a[i]
        if s > 10 ** 18:
            s = -1
            break
print(s)
### BUGGY CODE ###

from collections import Counter

def mapdict(n, dictionary):
    return dict(map(lambda t:(t[0]-n,t[1]), dictionary.items()))

def count(dic):
    count = 0
    for k,v in dic.items():
        count += abs(k*v)
    return count

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

A2 = sorted([A[i-1]-i for i in range(1,N+1)])


Adic = Counter(A2)
Ax  = A2[N//2]
Adic = mapdict(Ax, Adic)

res = count(Adic)
pl = count(mapdict(1,Adic))
mn = count(mapdict(-1,Adic))


if pl<=res:
    tmp = res
    while tmp <= res:
        res = tmp
        Adic = mapdict(1, Adic)
        tmp = count(Adic)

elif mn<=res:
    tmp = res
    while tmp <= res:
        res = tmp
        Adic = mapdict(-1, Adic)
        tmp = count(Adic)

print(res)

### FIXED CODE ###

from collections import Counter

def mapdict(n, dictionary):
    return dict(map(lambda t:(t[0]-n,t[1]), dictionary.items()))

def count(dic):
    count = 0
    for k,v in dic.items():
        count += abs(k*v)
    return count

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

A2 = sorted([A[i-1]-i for i in range(1,N+1)])


Adic = Counter(A2)
Ax  = A2[N//2]
Adic = mapdict(Ax, Adic)

res = count(Adic)

if N==1:
    print(0)

elif N==2:
    print(sum(map(abs,map(lambda x:x-min(A2),A2))))

else:
    pl = count(mapdict(A2[N//2 +1],Adic))
    mn = count(mapdict(A2[N//2 -1],Adic))
    if pl<=res:
        tmp = pl
        tmpc = 1
        while tmp <= res:
            tmpc += 1
            if N//2 + tmpc > N-1:
                break
            res = tmp
            Adic = mapdict(A2[N//2 +tmpc], Adic)
            tmp = count(Adic)
    elif mn<=res:
        tmp = mn
        tmpc = 1
        while tmp <= res:
            tmpc += 1
            if N//2 - tmpc < 0:
                break
            res = tmp
            Adic = mapdict(A2[N//2 -tmpc], Adic)
            tmp = count(Adic)

    print(res)
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
ans = sum(A)
for _ in range(M):
    b, c = map(int, input().split())
    index = bisect.bisect_left(A, c)
    index = min(index, b)
    for i in range(index):
        ans += c - A[i]
        A[i] = c
    if index > 0:
        A.sort()

print(ans)



### FIXED CODE ###

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

bc = [list(map(int, input().split())) for _ in range(M)]

ans = sum(A)

bc = sorted(bc, key=lambda i: i[1], reverse=True)

i = 0
for b, c in bc:
    for _ in range(b):
        if A[i] > c:
            break
        ans += c - A[i]
        i += 1
        if i >= N:
            break
    else:
        continue
    break

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

from collections import deque


def main():
    S = deque(list(input()))
    Q = int(input())
    for _ in range(Q):
        query = list(input().split())
        if query[0] == "1":
            S.reverse()
        if query[0] == "2":
            if query[1] == "1":
                S.appendleft(query[2])
            elif query[1] == "2":
                S.append(query[2])
    ans = "".join(S)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    S = deque(list(input()))
    Q = int(input())
    count = 0
    for _ in range(Q):
        query = list(input().split())
        if query[0] == "1":
            count += 1
        if query[0] == "2":
            if count % 2 == 0:
                if query[1] == "1":
                    S.appendleft(query[2])
                elif query[1] == "2":
                    S.append(query[2])
            else:
                if query[1] == "1":
                    S.append(query[2])
                elif query[1] == "2":
                    S.appendleft(query[2])
    if count % 2 == 0:
        ans = "".join(S)
        print(ans)
    else:
        S.reverse()
        ans = "".join(S)
        print(ans)


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

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
l_1 = 1
l_2 = 1
mod = 10**9+7
def lcm(x,y):
    return x*y//gcd(x,y)
for i in A[:N//2]:
    l_1 = lcm(l_1,i)
for j in A[N//2:]:
    l_2 = lcm(l_2,j)
l = lcm(l_1,l_2)

print(sum([l//i%mod for i in A])%mod)

### FIXED CODE ###

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
l_1 = 1
l_2 = 1
mod = 10**9+7
def lcm(x,y):
    return x*y//gcd(x,y)
for i in A[:N//2]:
    l_1 = lcm(l_1,i)
for j in A[N//2:]:
    l_2 = lcm(l_2,j)
l = lcm(l_1,l_2)
out1 = sum([l_1//i for i in A[:N//2]])
out2 = sum([l_2//i for i in A[N//2:]])
out1 *= l//l_1
out2 *= l//l_2
print((out1+out2)%mod)
### BUGGY CODE ###

import sys
def fact(n):
    ret = [1]
    if n%2==0:
        ret.append(2)
        return ret
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            ret.append(i)
            return ret
    return ret
def isPrime(n):
    if n<=1:
        return False
    if n==2:
        return True
    if fact(n)==[1]:
        return True
    else:
        return False
lines = sys.stdin.readlines()
for line in lines:
    inp = int(line)
    s=0
    for i in range(2,inp+1):
        if isPrime(i):
            s+=1
    print (s)

### FIXED CODE ###

import sys

def primeTable(n):
    list = [True for _ in range(n+1)]
    i = 2
    while i * i <= n:
        if list[i]:
            j = i+i
            while j<= n:
                list[j] = False
                j += i
        i += 1

    table = [i for i in range(n+1) if list[i] and i >= 2]
    return table

lines = sys.stdin.readlines()
primeList = primeTable(999999)

for line in lines:
    inp = int(line)
    primes = list(filter(lambda n:n>=2 and n<=inp, primeList))
    num = len(primes)
    print (num)
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
dict_A = Counter(A)
sum_list = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b not in dict_A:
        print(sum_list)
    else:
        dict_A[c] += dict_A[b]
        dict_A[b] = 0
        sum_list = 0
        for key, value in dict_A.items():
            sum_list += key * value
        print(sum_list)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
dict_A = Counter(A)
sum_list = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b not in dict_A:
        print(sum_list)
    else:
        b_num = dict_A[b]
        dict_A[c] += dict_A[b]
        dict_A[b] = 0
        sum_list = sum_list + (c - b) * b_num
        print(sum_list)
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split(' ')))
    Ai = list(map(int, input().split(' ')))
    # print(Ai)
    P = []
    prev = 0
    now = 0
    # for i, n in enumerate(range(K-1, N)):
        
        
        # if i > 0:
        #     # print('a', n)
        #     prev = now
        #     now = sum(Ai[n-K+1:n+1])
        #     # print(now, prev)
        #     if now > prev:
        #         print('Yes')
        #     else:
        #         print('No')
        # else:
        #     # print('b', n)
        #     now = sum(Ai[n-K+1:n+1])
            
            
    # # print(P)
    # for i in range(len(P)-1):
    #     if P[i+1] > P[i]:
    #         print('Yes')
    #     else:
    #         print("No")
    
    S = [1]
    for i in range(len(Ai)):
        S.append(S[i] * Ai[i])
    # print(S, len(S))
    
    for n in range(K,N):
        # print(n, S[n], n-K, S[n-K])
        a1 = S[n] // S[n-K]
        a2 = S[n+1] // S[n-K+1]
        
        if a2 > a1:
            print('Yes')
        else:
            print('No')
        

main()

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
 
for i in range(N - K):
  score_2 = A[i+K]
  score_1 = A[i]
  print('Yes' if score_1 < score_2 else 'No')
### BUGGY CODE ###

def print_ans(s):
    """Print substring of s, odd_th char
    >>> print_ans([1])
    1
    >>> print_ans([1,4])
    1
    >>> print_ans([0,3,4,5])
    3
    >>> print_ans([1,2,3,2,5,6])
    4
    
    """
    b = list(set(s))
    ans = 1
    """TLE 
    for i in range(b[0],b[-1]+1):
        ans = max(b.count(i)+b.count(i+1)+b.count(i+2),ans)
    """
    
    for i in range(len(b)):
        ans = max(ans,s.count(b[i])+s.count(b[i]+1)+s.count(b[i]+2))
    print(ans)

if __name__ == '__main__':
    N = input()
    a = list(map(int,input().split()))
    print_ans(a)



### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
cnt = [0]*(10**5)
for i in a:
    cnt[i] += 1
ans_max =0
for i in range(100000-2):
    #ans_max = max(ans_max,sum(cnt[i:i+3]))
        ans_max = max(ans_max,cnt[i]+cnt[i+1]+cnt[i+2])

print(ans_max)
### BUGGY CODE ###

m, n = map(int, input().split())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append(set(range(a,b+1)))
if n >= 2:
  for i in range(1,n):
    d = l[0].intersection(l[i])
else:
  d = l[0]
print(len(d))

### FIXED CODE ###

m, n = map(int, input().split())
a, b = map(int, input().split())
for i in range(n-1):
  c, d = map(int, input().split())
  a = max(a,c)
  b = min(b,d)
if b - a >=0 :
  print(b-a +1)
else:
  print(0)
### BUGGY CODE ###

n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
mi = 10000000000000
res = []
res.append(dat[0])
import bisect
for i in range(1, n):
    a = bisect.bisect_left(res, dat[i])
    if a == 0:
        res = [dat[i]] + res
    else:
        res[a-1] = dat[i]
    #print(res)
print(len(res))

### FIXED CODE ###

def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

import collections
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
res = collections.deque([])

res.append(dat[0])
import bisect

for i in range(1, n):
    a = bisect_right(res, dat[i])
    #print("2 : {0}".format(a))

    if a == len(res):
        res.append(dat[i])
    else:
        res[a] = dat[i]
print(len(res))
#print(res)
### BUGGY CODE ###

n = int(input())

ans = 0
for a in range(1,n):
    for b in range(1,(n//a)+1):
        if a*b < n:
            ans += 1

print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
for a in range(1,n):
    for b in range(1,(n//a)+1):
        if a*b < n:
            ans += 1

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

n,m = map(int,input().split())
numSet = set(range(1,n+1))
for i in range(m):
  l,r = map(int,input().split())
  numSet &= set(range(l,r+1))
print(len(numSet))

### FIXED CODE ###

n,m = map(int,input().split())
numSet = set(range(1,n+1))
L,R = [],[]
for i in range(m):
  l,r = map(int,input().split())
  L.append(l)
  R.append(r)
if min(R) >= max(L):
  print(min(R)-max(L)+1)
else:
  print(0)
### BUGGY CODE ###

s=input()
q=int(input())
queri=[]
rv=0

for i in range(q):
    tmp=list(map(lambda x: x,input().split()))
    queri.append(tmp)
    if tmp[0]=="1": rv+=1
rv=rv%2

if rv==1: s=s[::-1]
ans=[s]

for i in range(q):
    if queri[i][0]=="2":
        rvt=(rv+int(queri[i][1]))%2
        if rvt==1: ans=[queri[i][2]]+ans
        else: s=ans.append(queri[i][2])

    else: rv=(rv+1)%2

for i in range(len(ans)):
    print(ans[i],end="")

### FIXED CODE ###

s=input()
q=int(input())
queri=[]
rv=0
forward=[]
back=[]
for i in range(q):
    queri=list(map(lambda x:x,input().split()))
    if queri[0]=="2":
        rvt=(rv+int(queri[1]))%2
        if rvt==1: forward.append(queri[2])
        else: back.append(queri[2])

    else: rv=(rv+1)%2

if rv==0:
    for i in range(len(forward)-1,-1,-1):
        print(forward[i],end="")
    print(s,end="")
    for i in range(len(back)):
        print(back[i],end="")
        
if rv==1:
    for i in range(len(back)-1,-1,-1):
        print(back[i],end="")
    print(s[::-1],end="")
    for i in range(len(forward)):
        print(forward[i],end="")