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

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if (j - i) <= (N - j):
            l1 = S[i:j]
            l2 = S[j:]
            if l1 in l2:
                ans = max(ans, len(l1))

print(ans)


### FIXED CODE ###

def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


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

ans = 0
for i in range(N):
    A = z_algo(S[i:])
    for idx, ls in enumerate(A):
        if idx - ls >= 0:
            ans = max(ans, ls)

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

import numpy as np
N = int(input())
H = list(map(int,input().split()))
k = np.zeros(N,dtype="int64")
for i in range (0,N-1):
  for j in range (i,N-1):
    if H[j] < H[j+1]:
      break
    k[i] = k[i] + 1
print(max(k))

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ans =  0
x = 0
for i in range (0,N-1):
  if H[i] >= H[i+1]:
    x = x + 1
  else:
    x = 0
  ans = max(ans,x)
print(ans)
### BUGGY CODE ###

def main():
    (l, r) = list(map(int, input().split()))

    min = 2020
    for i in range(l, r + 1):
        for j in range(i + 1, r + 1):
            mod = i * j % 2019
            if mod <= min:
                min = mod

            if min == 0:
                break

        else:
            if min == 0:
                break

    print(min)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    (l, r) = list(map(int, input().split()))

    ans = 2020
    for i in range(l, min(r + 1, l + 2019)):
        for j in range(i + 1, min(r + 1, i + 2020)):
            mod = i * j % 2019
            if mod <= ans:
                ans = mod

    print(ans)

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

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx,-1)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        oy,ox,turn = q.popleft()
        for i,dy,dx in zip(range(4),Dy,Dx):
            if i == turn:
                continue
            y,x = oy,ox
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0 and dist[y][x] <= dist[oy][ox]:
                    break
                dist[y][x] = dist[oy][ox] + 1
                q.append((y,x,(i + 2)%4))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        ny,nx = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = ny,nx
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0 and dist[y][x] <= dist[ny][nx]:
                    break
                if dist[y][x] < 0:
                    dist[y][x] = dist[ny][nx] + 1
                    q.append((y,x))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)

    
    return dp[n][c]

n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
print(knapsackBottomUp(wt,price,c,n))

### FIXED CODE ###

inf=10**10
def knapsackBottomUp(wt,price,c,n,m):
    dp=[[inf for x in range(m+1)] for y in range(n+1)]
    for l in range(n+1):
        dp[l][0]=0


    for i in range(1,n+1):
        wi=wt[i];vi=price[i]
        for V in range(1,m+1):
            if vi <= V:
                dp[i][V]=min(wi+dp[i-1][V-vi],dp[i-1][V])
            else:
                dp[i][V]=dp[i-1][V]

    res=0
    for i in range(m+1):
        if dp[n][i]<=c:
            res=i
    print(res)
n,c=map(int,input().split())
wt=[]
price=[]
wt.append(0)
price.append(0)
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
max_val=sum(price)
knapsackBottomUp(wt,price,c,n,max_val)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = [0] * 13, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, pre
        for i in range(13): # 再生成を避ける
            cur[i] = 0
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
 
MOD = 1000000007  # type: int
 
 
def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = [0] * 13, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, pre
        for i in range(13): # 再生成を避ける
            cur[i] = 0
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]
 
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))
 
def test():
    import doctest
    doctest.testmod()
 
if __name__ == '__main__':
    #test()
    main()
### BUGGY CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split())) for i in range(M)]
ans_1=0
ans_2=0
ans=0
num_1=0
num_2=0
for i in range(M):
  ans_1=10**12+PY[i][0]*10**6
  num_1=PY[i][0]
  num_2=PY[i][1]
  for i in range(M):
    if num_1==PY[i][0] and num_2>=PY[i][1]:
      ans_2+=1
  ans=ans_1+ans_2
  ans=str(ans)
  print(ans.lstrip('1'))
  ans_2=0

### FIXED CODE ###

N,M=map(int,input().split())
li=[]

for i in range(M):
  P,Y=map(int,input().split())
  li.append([P,Y,i])
li.sort(key=lambda x:x[1])
li.sort(key=lambda x:x[0])
pre=li[0][0]
cnt=1
ans=[]

for p,y,i in li:
  if p==pre:
    ans.append([str(p).zfill(6)+str(cnt).zfill(6),i])
    cnt+=1
  else:
    pre=p
    ans.append([str(p).zfill(6)+str(1).zfill(6),i])
    cnt=2
ans.sort(key=lambda x:x[1])

for a,i in ans:
  print(a)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
ahead = 0
back = max(a[1:])
result = [back]
for i in range(1,n-1):
    ahead = max(ahead,a[i-1])
    if back == a[i]:
        back = max(a[(i+1):])
    result.append(max(ahead,back))
ahead = max(ahead,a[n-2])
result.append(ahead)
for j in range(n):
    print(result[j])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a2 = sorted(a)
ma = a2[-1]
se = a2[-2]
result = []
for i in range(n):
    if a[i] == ma:
        result.append(se)
    else:
        result.append(ma)
for j in range(n):
    print(result[j])
### BUGGY CODE ###

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

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

Swap=[None]*M

for i in range(M):
    Swap[i]=set(map(int,input().split()))


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break

        if judge_2==0:
            i+=1
        else:
            judge_2=0


Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

count=0

for i in range(finish):
    for j in Swap[i]:
        if P[j-1] in Swap[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)


### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


print(count)
### BUGGY CODE ###

import copy
import sys
sys.setrecursionlimit(10**9)

def dfs(G, v, p, d, depth):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1, depth)
    return G, depth


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
GT, dt = dfs(GT, T, -1, 0, depth)

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
GA, da = dfs(GA, A, -1, 0, depth)

def dfs2(G, v, p, md):
    for nv in G[v]:
        if nv == p:
            continue
        if dt[nv] <= da[nv]:
            md[0] = max(md[0], da[nv])
        else:
            continue
        dfs2(G, nv, v, md)
    return md


maxd = dfs2(GT, T, -1, [da[T]])
print(maxd[0]-1)

### FIXED CODE ###

import copy
import sys
sys.setrecursionlimit(10**9)

def dfs(G, v, p, d, depth):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1, depth)
    return G, depth


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
GT, dt = dfs(GT, T, -1, 0, depth)

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
GA, da = dfs(GA, A, -1, 0, depth)

ans = 0
for t, a in zip(dt, da):
    if t <= a:
        ans = max(ans, a)
print(ans-1)
### BUGGY CODE ###

n = input()
s = input()

n = int(n)

allnum = set(range(0, 1000))
ans = []
counts = 0


checked_i = []
for i in range(n - 2):
    if i in checked_i:
        continue
    else:
        checked_i.append(i)
    
    checked_j = []
    for j in range(i + 1, n - 1):
        if j in checked_j:
            continue
        else:
            checked_j.append(j)
        # checked_j.append(j)

        num = int(s[i]) * 100 + int(s[j]) * 10

        if num in ans:
            continue
        else:
            ans.append(num)

            saigo_cnt = len(set([int(s[k]) for k in range(j + 1, n)]))
            counts += saigo_cnt

print(counts)


### FIXED CODE ###

n = input()
s = str(input())
n = int(n)

ans_count =0

for i in range(10):
    for j in range(10):
        for k in range(10):
            i_pos = s.find(str(i))

            if i_pos < 0:
                continue

            j_pos = s.find(str(j),i_pos+1)

            if j_pos < 0:
                continue

            k_pos = s.find(str(k), j_pos +1)

            if k_pos < 0:
                continue

            ans_count += 1

print(ans_count)
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(input())
quiz = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
    cnt_ac = 0
    for j in range(max(1,quiz[i][0]), quiz[i][1]):
        if s[j] == "C" and s[j-1] == "A":
            cnt_ac += 1
    print(cnt_ac)

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
quiz = [list(map(int, input().split())) for _ in range(q)]

cnt_list = [0]*n
judge = 0

for i in range(n):
    if s[i] == "A":
        judge = 1
        cnt_list[i] = cnt_list[i-1]
    elif judge == 1 and s[i] == "C":
        judge = 0
        cnt_list[i] = cnt_list[i-1] + 1
    else:
        judge = 0
        cnt_list[i] = cnt_list[i-1]

for i in range(q):
    print(cnt_list[quiz[i][1] - 1] - cnt_list[quiz[i][0]-1])
### BUGGY CODE ###

import sys
import heapq
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

h=[]
for i in range(n):
    if b[i]>a[i]:
        h.append([-1*b[i],i])
heapq.heapify(h)

loop=0
idx=0
while(loop<10**9):
    if not h:
        break
    loop+=1
    buf,idx=heapq.heappop(h)
    buf=-1*buf

    buf-=b[(idx-1)%n]+b[(idx+1)%n]
    b[idx]=buf
    if buf<a[idx]:
        print(-1)
        sys.exit()
    elif buf>a[idx]:
        heapq.heappush(h,[buf*-1,idx])

print(loop)

### FIXED CODE ###

import sys
import heapq

def main():
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))

    h=[]
    for i in range(n):
        if b[i]>a[i]:
            heapq.heappush(h,(b[i]*-1,i))

    loop=0
    idx=0
    while(1):
    #print(b)
        if not h:
            break
        buf,idx=heapq.heappop(h)
        buf=-1*buf

        x=(buf-a[idx])//(b[(idx-1)%n]+b[(idx+1)%n])
        buf-=x*(b[(idx-1)%n]+b[(idx+1)%n])
        loop+=x
        b[idx]=buf
        if x==0:
            #print(b)
            print(-1)
            sys.exit()
        elif buf>a[idx]:
            heapq.heappush(h,(buf*-1,idx))

    print(loop)

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

R, G, B, N = map(int, input().split())

cnt = 0

for i in range(N//R + 1):
    for j in range(N//G + 1):
        sum = N - i * R - j * G
        if sum >= 0 and sum % B == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

cnt = 0

for i in range(N//R + 1):
    for j in range(N//G + 1):
        sum = N - i * R - j * G
        if sum >= 0 and sum % B == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
input= sys.stdin.readline

N,M = map(int,input().split())
g=max(M//N,M**0.5)#最大公約数になる可能性のある最大値
for i in range(M-N+1):
  if M%(N+i)==0:
    print(M//(N+i))
    exit()

### FIXED CODE ###

import sys
input= sys.stdin.readline

N,M = map(int,input().split())
g=M//N#最大公約数になる可能性のある最大値
for i in range(g):
  if M%(g-i)==0:
    print(g-i)
    exit()
  if M%(N+i)==0:
    print(M//(N+i))
    exit()
### BUGGY CODE ###

def telepo_test(start, goal, delta, board):
    c_s = get_coordinate(start, board)
    c_g = get_coordinate(goal, board)

    mp = 0
    while c_s != c_g:
        target = board[c_s[0]][c_s[1]] + delta
        c_t = get_coordinate(target, board)
        mp += abs(c_t[0] - c_s[0]) + abs(c_t[1] - c_s[1])
        c_s = c_t
    return mp


def get_coordinate(n, board):
    for c, r in enumerate(board):
        if n not in r:
            continue
        return (c, r.index(n))
    else:
        return None


H, W, D = tuple(map(int, input().split()))
board = [tuple(map(int, input().split())) for _ in range(H)]
Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [telepo_test(LR[0], LR[1], D, board) for LR in LRs]
for r in result:
    print(r)

### FIXED CODE ###

def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [board[r] for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        print(s,t)
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
delta = dict([(i, 0) for i in range(1, D+1)])
for d in range(D+1, H*W+1):
    delta[d] = delta[d-D] + abs(board[d][0] - board[d-D][0]) + abs(board[d][1] - board[d-D][1])

Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [delta[LR[1]] - delta[LR[0]] for LR in LRs]

for r in result:
    print(r)
### BUGGY CODE ###

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

for i in range(M):
    A[A.index(max(A))] //= 2

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = []
for i in A:
    heapq.heappush(a, -i)

for i in range(M):
    heapq.heappush(a, -(-heapq.heappop(a) // 2))

print(-sum(a))
### BUGGY CODE ###

n = int(input())

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

ans = 1
for i in a:
    ans *= i

if ans >= 1000000000000000001:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))
if 0 in a:
    print(0)
    exit()
ans = 1
for i in a:
    ans *= i

    if ans >= 1000000000000000001:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import itertools
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    hoge = tuple(map(int, input().split()))
    sumn = 0
    mod = 10 ** 9 + 7
    for pair in list(itertools.combinations(hoge, 2)):
        sumn += (pair[0] * pair[1])
        sumn %= mod
    print(sumn)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    nums = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    num_sum = sum(nums)
    part_sum = sum(map(lambda x: x**2, nums)) # naname

    print((num_sum**2 - part_sum) // 2 % mod)


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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
        t %= m

    return s - (len(bin(t)) - 3)


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1) - 1
    for c in a:
        t |= t << c
    t &= m

    return s - (t.bit_length() - 1)


print(main())
### BUGGY CODE ###

import sys
a = sys.stdin.read().split('\n')[:-1]
s = list(a[0])
q = int(a[1])
f = 1
for i in range(2, q + 2):
    if a[i][0] == '1':
        f = 1 - f
    else:
        if a[i][2] == '21'[f]:
            s.insert(0, a[i][4])
        else:
            s.append(a[i][4])
if f == 1:
    print(''.join(s))
else:
    print(''.join(reversed(s)))

### FIXED CODE ###

import sys
a = sys.stdin.read().split('\n')[:-1]
q = int(a[1])
f = 1
l = [[], []]
for i in range(2, q + 2):
    if a[i][0] == '1':
        f = 1 - f
    else:
        l[0 if a[i][2] == '21'[f] else 1].append(a[i][4])
if f != 1:
    l[1].reverse()
    print(''.join(l[1]) + ''.join(reversed(list(a[0]))) + ''.join(l[0]))
else:
    l[0].reverse()
    print(''.join(l[0]) + a[0] + ''.join(l[1]))
### BUGGY CODE ###

S = input()
N = len(S)

l = [0] * 2019
for i in range(N):
    l[int(S[i:N])%2019] += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)

l = [0] * 2019
temp = 0
e = 1
for i in range(N-1, -1, -1):
    temp += int(S[i]) * e
    temp %= 2019
    l[temp] += 1
    e *= 10
    e %= 2019

ans = l[0]

for i in range(0, 2019):
    ans += l[i] * (l[i]-1) // 2

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

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
ans=0
for x in a:
  ans+=lcm//x
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
ans=0
for x in a:
  ans+=lcm//x
print(ans%mod)
### BUGGY CODE ###

import math
n=int(input())
def divisor(n): 
    i = 1
    c=0
    table = []
    while i * i <= n:
        if n%i == 0:
            if i==n//i:
                c+=1
            else:
                c+=2
        i += 1
    return c
n=n-1
ans=0
while n>=1:
    ans+=divisor(n)
    n-=1

print(ans)

### FIXED CODE ###

import math

n=int(input())
c=0

for a in range(1,n):
    c+=math.floor((n-1)/a)

print(c)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
for i in range(Q):
    l,r = map(int,input().split())
    s = S[l-1:r]
    c = 0
    for j in range(len(s)-1):
        if s[j] == "A" and s[j+1] == "C":
            c += 1
    print(c)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
c = []
count = 0
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        count += 1
    c.append(count)
for i in range(Q):
    l,r = map(int,input().split())
    if l == 1:
        print(c[r-2]-0)
    else:
        print(c[r-2]-c[l-2])
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
ans=0
for i in range(N):
    C=True
    for j in range(i):
        if P[j]<P[i]:
            C=False
    if C:
        ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
ans=1
m=P[0]
for i in range(1,N):
    if m>P[i]:
        m=P[i]
        ans+=1
print(ans)