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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

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
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v):
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return d

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

ans = 0
for v in range(ls):
  tmp = max(dfs(pt,v))
  if tmp>ans:
    ans = tmp

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

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
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

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

h,n = list(map(int, input().split()))
ab = []
a = []
b = []
aonb = []
for _ in range(n):
    this_ab = list(map(int, input().split()))
    ab.append(this_ab)
    a.append(this_ab[0])
    b.append(this_ab[1])
    aonb.append(this_ab[0]/this_ab[1])

maxa = max(a)
mina = min(a)
maxn = h//mina + 1
dp = [float("inf") for _ in range(maxa + h)]
dp[0] = 0

for i in range(maxn):
    for j in range(maxa + h):
        for k in range(n):
            if a[k] <= j:
                dp[j] = min(dp[j-a[k]]+b[k], dp[j])

print(min(dp[h:]))

### FIXED CODE ###

h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [0 for _ in range(hmaxa)]

for i in range(1, hmaxa):
    ab_child = [dp[i-a]+b for a,b in ab]
    dp[i] = min(ab_child)

print(min(dp[h:]))
### BUGGY CODE ###

s=input()
t=input()

cs={}
for i,c in enumerate(s):
    cs[c] = cs.get(c,[])+[i]

ct={}
for i,c in enumerate(t):
    ct[c] = ct.get(c,[])+[i]

print('Yes' if sorted(list(ct.values()))==sorted(list(cs.values())) else 'No')

### FIXED CODE ###

import collections

s=input()
t=input()

cs = collections.Counter(s)
ct = collections.Counter(t)

print('Yes' if sorted(list(ct.values()))==sorted(list(cs.values())) else 'No')
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
squares = np.zeros(N+2, np.bool)
squares[0] = 1; squares[N+1] = 1
S = np.array(list('-' + sr() + '-'))
TD = [sr().split() for _ in range(Q)]
for t, d in TD[::-1]:
    index = np.where(S==t)[0]
    if d == 'L':
        i = -1
    else:
        i = 1
    squares[index] = squares[index] + squares[index+i]

answer = N + 2 - np.count_nonzero(squares)
print(answer)
# 49


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
S = '-' + sr() + '-'
TD = [sr().split() for _ in range(Q)]

L = 1
for t, d in TD[::-1]:
    if d == 'L':
        if L <= N and S[L] == t:
            L += 1
    if d == 'R':
        if L >= 1 and S[L-1] == t:
            L -= 1
R = N
for t, d in TD[::-1]:
    if d == 'L':
        if R <= N and S[R+1] == t:
            R += 1
    if d == 'R':
        if R >= 1 and S[R] == t:
            R -= 1

answer = max(0, R - L + 1)
print(answer)
# 34
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    a = l[n-1-i]
    for j in range(i+1,n-1):
        b = l[n-1-j]
        #print(a,b)
        mn = a - b
        ng = -1
        ok = n-1-j
        if mn >= b:
            continue
        while abs(ok - ng) > 1:
            hf = (ng + ok) // 2
            #print(a,b,l[hf])
            if l[hf] > mn:
                ok = hf
            else:
                ng = hf
        ans += n-1-j - ok
        #print(a,b,l[ok],mn,ok)


print(ans)



### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    a = l[n-1-i]
    for j in range(i+1,n-1):
        b = l[n-1-j]
        #print(a,b)
        mn = a - b
        ng = -1
        ok = n-1-j
        if mn >= b:
            continue
        while abs(ok - ng) > 1:
            hf = (ng + ok) // 2
            #print(a,b,l[hf])
            if l[hf] > mn:
                ok = hf
            else:
                ng = hf
        ans += n-1-j - ok
        #print(a,b,l[ok],mn,ok)


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

n, m = map(int, input().split())
array = [list(map(int, input().split())) for i in range(m)]
result = set([i for i in range(1, n+1)])
for el in array:
    L, R = el[0], el[1]
    work = set([i for i in range(L, R+1)])
    result = work & result
print(len(result))

### FIXED CODE ###

n, m = map(int, input().split())
array = [list(map(int, input().split())) for i in range(m)]
result = [1, n]
for el in array:
    if el[0] > result[1] or result[0] > el[1]:
        result = [1, 0]
        break
    else:
        work = sorted(result + el)
        result = [work[1], work[2]]
print(result[1]-result[0]+1)
### BUGGY CODE ###

n = int(input())
res = []

for i in range(n):
    s = str(input())
    if (s in res) == False:
        res.append(s)

print(len(res))

### FIXED CODE ###

n = int(input())
res = []

for i in range(n):
    s = str(input())
    #if (s in res) == False:
    res.append(s)

#print(len(res))
print(len(set(res)))
### BUGGY CODE ###

N = int(input())

s = input().split()
A = []
for i in range(N):
  A.append(int(s[i]))
  
result = 0
for i in range(N-1):
  if i == 0 or i%2 == 1:
    m = max(A)
    result += m
    A.remove(m)
  else:
    result += m
    
print(result)

### FIXED CODE ###

N = int(input())

s = input().split()
A = []
for i in range(N):
  A.append(int(s[i]))
  
result = 0
A.sort(reverse=True)
result += A[0]
A.pop(0)
if N % 2 == 0:
  result += sum(A[:(int(N/2)-1)])*2
else:
  result += (sum(A[:(int((N-1)/2)-1)])*2 + A[int((N-1)/2)-1])
    
print(result)
### BUGGY CODE ###

import numpy as np
import math 
N, K=map(int,input().split())
A2 = np.zeros(N)
A = list(map(int,input().split()))
A = list(map(lambda x: x -1 , A))
current_town = 0

K2 = K % math.factorial(N)



for i in range(K2):
    current_town = A[current_town]
    if  A2[current_town] != 0:
        cycle = i - A2[current_town] 
        i = K2 - (K2-i) % cycle
    else:
        A2[current_town] = i

print(current_town+1)


### FIXED CODE ###

import numpy as np
n, k=map(int,input().split())

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

 
s = list()
ord = np.full(n+1, -1)
c=1
l=0

v=1
while ord[v]==-1:
    ord[v]=len(s)
    s.append(v)
    v=a[v-1]
c=len(s)-ord[v]
l=ord[v]

if k<l:
    print(s[k])  
else:
    k-=l
    k%=c
    print(s[l+k])
### BUGGY CODE ###

N,K=map(int,input().split())
T=list(map(int,input().split()))

for _ in range(K):
    A=T[::]
    L=[0 for _ in range(N)]
    R=[0 for _ in range(N)]
    for i in range(N):
        l=(i+1)-A[i]-0.5
        r=(i+1)+A[i]+0.5
        l=int(l+0.999)
        r=int(r)
        l-=1
        if l<0:
            l=0
        L[l]+=1
        if r>=N:
            continue
        R[r]+=1

    #print(L)
    #print(R)
    T=[0 for _ in range(N)]
    T[0]=L[0]
    for i in range(N-1):
        T[i+1]=T[i]+L[i+1]-R[i+1]
    #print(T)

print(*T)

### FIXED CODE ###

import numpy as np
from numba import jit
N,K=map(int,input().split())
A=list(map(int,input().split()))

@jit
def imos(A):
    B=np.zeros_like(A)
    for i,x in enumerate(A):
        a=max(0,i-x)
        b=min(i+x,N-1)
        B[a]+=1
        if b+1<=N-1:
            B[b+1]-=1
    B=np.cumsum(B)
    return B

for i in range(K):
    if i>=50:
        break
    A=imos(A)
print(*A)
### BUGGY CODE ###

import bisect
N = int(input())
A_arr = list(map(int,input().split()))
A_arr.sort()
B_arr = list(map(int,input().split()))
B_arr.sort()
C_arr = list(map(int,input().split()))
ans = 0
for i in C_arr:
    B_index = bisect.bisect_left(B_arr,i)
    for k in range(B_index):
        ans += bisect.bisect_left(A_arr,B_arr[k])
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A_arr = list(map(int,input().split()))
A_arr.sort()
B_arr = list(map(int,input().split()))
B_arr.sort()
C_arr = list(map(int,input().split()))
ans = 0
check_array = [0] * N
for i in range(N):
    check_array[i] = check_array[i-1]+bisect.bisect_left(A_arr,B_arr[i])
for i in C_arr:
    B_index = bisect.bisect_left(B_arr,i)
    if B_index == 0:
        continue
    ans += check_array[B_index-1]
print(ans)
### BUGGY CODE ###

n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 1 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY:
        if M[u][v] < d[v]:
          d[v] = M[u][v]
          p[v] = u
          color[v] = 1

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]] 
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] != -1:
     M[i][j] = G[j]

print MST()

### FIXED CODE ###

n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 2 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY and M[u][v] < d[v]:
        d[v] = M[u][v]
        p[v] = u
        color[v] = 1

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]]
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] != -1:
     M[i][j] = G[j]

print MST()
### BUGGY CODE ###

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

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

max_len = len(bin(max(a))[2:])
l = [0] * max_len

for a in a:
    temp = bin(a)[2:][::-1]
    # print(temp)
    for i in range(max_len):
        if i < len(temp):
            l[i] += int(temp[i])
        else:
            l[i] += 0

# print(l)

ans = 0
mod = 10**9 + 7

for i in range(max_len):
    ans += ((2**i) % mod) * l[i] * (N-l[i])
    ans = ans % mod

print(ans)


### FIXED CODE ###

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

max_len = len(bin(max(a))[2:])
l = [0] * max_len

ans = 0
mod = 10**9 + 7

for i in range(max_len):
    for x in a:
        l[i] += x >> i & 1
    ans += pow(2, i, mod) * l[i] * (N-l[i])

print(ans % mod)
### BUGGY CODE ###

def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    l = []
    flg = 1
    while True:
        l.append(a.index(flg)+1)
        flg += 1
        if len(l) == n:
          break
    print(*l)
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    l = [0]*n
    for i in range(n):
        l[a[i]-1] = i+1
    print(*l)
resolve()
### BUGGY CODE ###

k,s=map(int,input().split())
c=0
#x>=y>=z
for i in range(k+1):
    for j in range(i+1):
        for k in range(j+1):
            if i+j+k==s:
                if i==j==k:
                    c+=1
                elif i!=j and j!=k:
                    c+=6
                else:
                    c+=3
                
print(c)

### FIXED CODE ###

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

n=int(input())
i=list(map(int,input().split()))
s=1
for a in i:
    s=s*a
if s>10**18:
    print(-1)
else:
    print(s)

### FIXED CODE ###

n=int(input())
i=list(map(int,input().split()))
s=1
i=sorted(i,reverse=True)
for a in i:
    s=s*a
    if s>10**18:
        s=-1
        break
if i[-1]==0:
    print("0")
else:
    print(s)
### BUGGY CODE ###

import fractions
from functools import reduce
n=int(input())
numbers=list(map(int,input().split()))
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
l=[]
for i in range(n):
    l.append(lcm_list(numbers)//numbers[i])
print(sum(l)%(10**9+7))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in a[1:]:
    div = div*i//fractions.gcd(div, i)

ans = 0
for i in a:
    ans += div//i

print(ans%mod)
### BUGGY CODE ###

H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    S.append(Sh)
    
L=[[0 for w in range(W)] for h in range(H)]
R=[[0 for w in range(W)] for h in range(H)]
U=[[0 for w in range(W)] for h in range(H)]
D=[[0 for w in range(W)] for h in range(H)]

for h in range(H):
    a=0
    b=0
    for w in range(W):
        if S[h][w]=='.':
            a+=1
        if S[h][w]=='#':
            a=0
        if S[h][-(1+w)]=='.':
            b+=1
        if S[h][-(1+w)]=='#':
            b=0
        L[h][w]+=a
        R[h][-(1+w)]+=b

for w in range(W):
    a=0
    b=0
    for h in range(H):
        if S[h][w]=='.':
            a+=1
        if S[h][w]=='#':
            a=0
        if S[-(1+h)][w]=='.':
            b+=1
        if S[-(1+h)][w]=='#':
            b=0
        U[h][w]+=a
        D[-(1+h)][w]+=b

maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score

print(maxScore)

### FIXED CODE ###

import numpy as np
H,W=map(int,input().split())
S=[list(input()) for h in range(H)]
S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]
S=np.array(S)
L=S.copy()
R=S.copy()
U=S.copy()
D=S.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*S[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*S[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*S[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*S[-(1+h),:]
print(int((L+R+U+D).max())-3)
### BUGGY CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

numbers = S[:]

def dps(numbers, x):
    if len(numbers) == 1:
        return x % numbers[0]
    
    ret = 0
    for i, n in enumerate(numbers):
        ret += dps(numbers[0:i] + numbers[i+1:], x % n)
    return ret
        
ans = dps(numbers, X)
ans = ans % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

s = input()
ans = 0
while s.count("ABC") != 0:
    ans += s.count("ABC")
    s = s.replace("ABC", "BCA")
print(ans)

### FIXED CODE ###

s = input().replace("BC", "D")
ans = 0
a = 0
for i in range(len(s)):
    if s[i] == "A":
        a += 1
    elif s[i] == "D":
        ans += a
    else:
        a = 0
print(ans)
### BUGGY 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()))

Swap.sort(key=lambda x:x[0])

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

count=0

for i in range(N):
    if Group[P[i]]==Group[i+1]:
        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 ###

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(len(a)-1):
  s_tmp = 0
  for j in range(i + 1, len(a)):
    s_tmp += a[j]
  s += a[i] * s_tmp
print(s % 1000000007)

### FIXED CODE ###

n = int(input())
s = 0
a = list(map(int, input().split()))
sum_tmp = sum(a[1:len(a)])
for i in range(len(a)-1):
  s += a[i] * sum_tmp
  sum_tmp -= a[i + 1]
print(s % 1000000007)
### BUGGY CODE ###

s = input()[::-1]
n = len(s)
dp = [1] + [0]*2018
now = 0
 
for i in range(n):
    now += 10**i * int(s[i])
    dp[now%2019] += 1
 
ans = sum([i*(i-1)/2 for i in dp])
print(int(ans))

### FIXED CODE ###

s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i *= 10
    i %= 2019

ans = sum([i*(i-1)/2 for i in dp])
print(int(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]

inds = [[] for _ in range(max(a)+1)]
y = [0]*n

for i in range(n):
    if inds[a[i]]:
        y[inds[a[i]][-1]] = i+1 - inds[a[i]][-1]
    inds[a[i]].append(i)

for j in range(max(a)+1):
    if inds[j]:
        y[inds[j][-1]] = n+inds[j][0]+1 - inds[j][-1]

length = (n*k).bit_length()

db = [y]
for m in range(length):
    next_y = [0]*n
    for i in range(n):
        next_y[i] = db[-1][i] + db[-1][(i+db[-1][i]) % n]
    db.append(next_y)


def last():
    cur = 0
    while True:
        for i in range(length+1):
            if cur + db[i][cur % n] > n*k:
                if i != 0:
                    cur += db[i-1][cur % n]
                    break
                else:
                    return cur


cur = last()

ans = []
while cur < n*k:
    if cur + db[0][cur % n] > n*k:
        ans.append(cur)
        cur += 1
    elif cur + db[0][cur % n] == n*k:
        break
    else:
        cur = cur + db[0][cur % n]

print(*map(lambda x: a[x % n]+1, ans))


### FIXED CODE ###

from bisect import bisect_right
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

d = {}
for i in range(n):
    if a[i] in d:
        d[a[i]].append(i)
    else:
        d[a[i]] = [i]


def simulate(k):
    if k == 0:
        return 0, []
    lap = 1
    res = [0]
    while True:
        s = res.pop()
        nxt = d[a[s]][bisect_right(d[a[s]], s) % len(d[a[s]])] + 1
        if nxt == n:
            if lap == k and s == n-1:
                res.append(s)
            if s == n-1:
                lap += 1
            return lap, res
        elif nxt <= s+1:
            if lap == k:
                res.append(s)
                if s == n-1:
                    return lap, res
                res.append(s+1)
                if s+1 == n-1:
                    return lap, res
            else:
                res.append(nxt)
                lap += 1
        else:  # s+1 < nxt
            s = nxt
            res.append(s)
    return 0


period, ans = simulate(k)

if period != k:
    lap, ans = simulate(k % period)

print(*[a[x] for x in ans])
### BUGGY CODE ###

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

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    x = input()

    while 'ST' in x:
        x = x.replace('ST', '', 1)

    print(len(x))


### FIXED CODE ###

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

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    from collections import deque

    x = input()
    n = len(x)
    d = deque()

    for i in range(n):
        d.append(x[i])

        if len(d) >= 2 and d[-2] + d[-1] == 'ST':
            d.pop()
            d.pop()

    print(len(d))
### BUGGY CODE ###

from math import pow
from itertools import combinations
x = int(input())

def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def func(a, b):
    return pow(a, 5) - pow(b,5)
    
cands = prime_factorize(x) + [1]
ok = False

for i in range(1, len(cands)):
    for c in combinations(cands, i):    
        y = 1
        for j in c:
            y *= j
        for a in range(1, y + 1):
            b = a - y
            if func(a,b) == x:
                print(a, b)
                ok = True
                break
        if ok:
            break
    if ok:
        break

### FIXED CODE ###

from math import pow
from itertools import combinations
x = int(input())

def func(a, b):
    return pow(a, 5) - pow(b,5)

ok = False
for a in range(-200, 200):
    for b in range(-200, 200):
        if func(a, b) == x:
            print(a, b)
            ok = True
            break
    if ok:
        break
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    query = input()
    if query[0] == '1':
        s = s[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            s = c + s
        else:
            s += c
print(s)

### FIXED CODE ###

s = input()
q = int(input())
is_reverse = 0
left = ''
for i in range(q):
    query = input()
    if query[0] == '1':
        is_reverse = (is_reverse+1) % 2
    else:
        _, f, c = query.split()
        if (is_reverse+int(f))%2 == 0:
            s += c
        else:
            left += c
s = left[::-1] + s
if is_reverse:
    print(s[::-1])
else:
    print(s)