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

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

import numpy as np

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            nei, w = nei[0], nei[1]
            if result[nei] is not None: continue
            if w%2 == 0:
                result[nei] = result[next_node]
            else:
                result[nei] = (result[next_node]+1)%2
            stack.append(nei)
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)

### FIXED CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')


N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [False]*(N+1), deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if visited[next_node]: continue
        visited[next_node] = True
        for nei in neighbor[next_node]:
            if result[nei[0]] is not None: continue
            if nei[1]%2 == 0:
                result[nei[0]] = result[next_node]
            else:
                result[nei[0]] = (result[next_node]+1)%2
            stack.append(nei[0])
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)
### BUGGY CODE ###

k = str(input())
d = int(input())
 
l = len(k)
 
mod = 10 ** 9 + 7
 
#less than: 1, else: 0
dp = [[[0] * 2 for _ in range(d)] for i in range(l+1)]
dp[0][0][0] = 1
 
for i in range(l):
    lim = int(k[i])
    for j in range(d):
        for num in range(10):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][1]) % mod
        for num in range(lim):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][0]) % mod
        
        dp[i+1][(j+lim) % d][0] = (dp[i+1][(j+lim) % d][0] + dp[i][j][0]) % mod
                
ans = (dp[l][0][0] + dp[l][0][1] + mod - 1) % mod
 
print(ans)

### FIXED CODE ###

k = str(input())
d = int(input())
 
l = len(k)
 
mod = 10 ** 9 + 7
 
#less than: 1, else: 0
dp = [[[0] * 2 for _ in range(d)] for i in range(l+1)]
dp[0][0][0] = 1
 
for i in range(l):
    lim = int(k[i])
    for j in range(d):
        for num in range(10):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][1]) % mod
        for num in range(lim):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][0]) % mod
        
        dp[i+1][(j+lim) % d][0] = (dp[i+1][(j+lim) % d][0] + dp[i][j][0]) % mod
                
ans = (dp[l][0][0] + dp[l][0][1] + mod - 1) % mod
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
dp = [10**10]*n
for _ in range(n-1):
    u,v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(k, p, dp):
    flag = False
    for v in edges[k]:
        if v != p:
            l = bl(dp, a[v])
            if dp[l] > a[v]:
                idx = l
                tmp = dp[l]
                dp[l] = a[v]
                flag = True
            ans[v] = n - dp.count(10**10)
            dfs(v, k, dp)
            if flag:
                dp[idx] = tmp
                flag = False
    return 
dfs(0, -1, dp)
for i in ans:
    print(i)




### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
dp = [10**10]*n
for _ in range(n-1):
    u,v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(k, p, dp):
    flag = False
    for v in edges[k]:
        if v != p:
            l = bl(dp, a[v])
            if dp[l] > a[v]:
                idx = l
                tmp = dp[l]
                dp[l] = a[v]
                flag = True
                if tmp == 10**10:
                    ans[v] = ans[k] + 1
                else:
                    ans[v] = ans[k]
            else:
                ans[v] = ans[k]
            dfs(v, k, dp)
            if flag:
                dp[idx] = tmp
                flag = False
    return 
dfs(0, -1, dp)
for i in ans:
    print(i)
### BUGGY CODE ###

import sys

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    valiation = list(set(A))
    cnt = 0
    for v in valiation:
        if A.count(v) % 2 != 0:
            cnt += 1
    print(cnt)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    d = {}
    for _ in range(N):
        a = int(input())
        if a not in d:
            d[a] = 1
        else:
            if d[a] == 1:
                d[a] = 0
            else:
                d[a] = 1
    
    cnt = 0
    for v in d.values():
        if v == 1:
            cnt += 1
    print(cnt)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

n, m = map(int, input().split())
data = []
row = []
col = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    data.append(1)
    row.append(a)
    col.append(b)
    data.append(1)
    row.append(b)
    col.append(a)
graph = csr_matrix((data, (row, col)), shape=(n, n))
_, p = dijkstra(graph, return_predecessors=True, directed=False, unweighted=True, indices=0)
for item in p[1:]:
    if(item < 0):
        print("No")
        exit()
print("Yes")
for item in p[1:]:
    print(item + 1)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
prev = [-1] * n
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def bfs(v):
    q = deque()
    visited[v] = True
    q.append(v)
    while q:
        v = q.popleft()
        for child in edges[v]:
            if not visited[child]:
                visited[child] = True
                prev[child] = v
                q.append(child)

bfs(0)
print("Yes")
for i in range(1, n):
    print(prev[i] + 1)
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = list(input())
ans = N
for i in range(N):
    L = Counter(S[:i])
    R = Counter(S[i+1:])
    ans = min(ans,L['W']+R['E'])
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = list(input())
WL = [0]*(N+1)
for i in range(0,N):
    if S[i] == 'W':
        WL[i+1] = WL[i] + 1
    else:
        WL[i+1] = WL[i]
T = S[::-1]
ER = [0]*(N+1)
for i in range(0,N):
    if T[i] == 'E':
        ER[i+1] = ER[i] + 1
    else:
        ER[i+1] = ER[i]
ans = N
for i in range(N):
    ans = min(ans,WL[i]+ER[N-i-1])
print(ans)
### BUGGY CODE ###

N, P = map(int, input().split())
if N == 1:
    print(P)
    exit()
for n in range(int(P ** (1 / N)) + 10, 0, -1):
    if P % (n ** N) == 0:
        print(n)
        break

### FIXED CODE ###

N, P = map(int, input().split())
if N == 1:
    print(P)
    exit()
if int(P ** (1 / N)) < 2:
    print(1)
    exit()
for n in range(int(P ** (1 / N))+1, 0, -1):
    if P % (n ** N) == 0:
        print(n)
        break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
ret = []
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  ret.append(x)
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input().strip())
M = N*(N-1)//2

graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1,N+1):
  l = list(map(int,input().split()))
  y = l[0]
  b,s = max(x,y),min(x,y)
  prev = (b-1)*(b-2)//2+s-1
  for y in l[1:]:
    b,s = max(x,y),min(x,y)
    now = (b-1)*(b-2)//2+s-1
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]

if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(M) if in_cnt[i]]:
  print(-1)
  exit()

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

from functools import reduce
S = list(map(int,input().rstrip()))
result=0
for i in range(len(S)):
    for j in range(1,len(S)-i+1):
        n = reduce(lambda a,b:10*a+b, S[i:i+j])
        if n %2019==0:
            result+=1
print(result)
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def convert_X(x,index):
	if index == 0:
		return x[1:]
	if index == len(x)-1:
		return x[:-1]
	return x[:index] + x[index+1:]

N = int(input())
X = [int(d) for d in input().split()]

for index in range(N):
	#print(index,convert_X(X,index))
	d_x = convert_X(X,index)
	d_x.sort()
	#print(d_x)
	#print(d_x[center-1])
	print(d_x[int( (len(d_x)+1)/2 ) -1])


### FIXED CODE ###

N = int(input())
X = [int(d) for d in input().split()]

sort_x = X.copy()
sort_x.sort()

nn = N//2
low_ = sort_x[nn-1]
high_ = sort_x[nn]

for x in X:
	if x < high_:
		print(high_)
	else:
		print(low_)
### BUGGY CODE ###

import sys
a=int(input())
i=1
j=1
t=True
while i**5<=a:
  if a-i**5>=0:
    if int((a-i**5)**0.2)==(a-i**5)**0.2:
      print(i,int((-1)*(a-i**5)**0.2))
      sys.exit()
  else:
    if int((-a+i**5)**0.2)==(-a+i**5)**0.2:
      print(i,int((-a+i**5)**0.2))
      sys.exit()
  i+=1
while t:
  if i**5-j**5>a:
    j+=1
  elif i**5-j**5<a:
    i+=1
  else:
    print(i,j)
    sys.exit()

### FIXED CODE ###

import sys
a=int(input())
for i in range(151):
  b=i**5-a
  c=abs(b)
  j=0
  while j**5<=c:
    if j**5==c:
      if b>=0:
        print(i,j)
        sys.exit()
      else:
        print(i,-j)
        sys.exit()
    j+=1
### BUGGY CODE ###

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

log_a = [math.log2(x) for x in a]
if sum(log_a) < m:
    print(0)
else:
    for i in range(1, m+1):
        a.sort()
        a[-1] = a[-1] // 2
    print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

while m > 0:
    a_max = heapq.heappop(a)
    if a_max == 0:
        break
    heapq.heappush(a, (-1)*(-a_max // 2))
    m -= 1
print(sum(a)*(-1))
### BUGGY CODE ###


Q = int(input().strip('\n'))
for i in range(Q):
    inDatas = input().strip('\n').split(' ')
    a, b = list(map(int, inDatas))
    score = a*b
    if a < b:
        tmp = a
        a = b
        b = tmp
    pa = b
    pb = a - 1
    count = b - 1 + b - 1
    while pb >= b+1:
        if pa == a: pa += 1
        elif pb == b: pb -= 1
        else:
            while pa*pb >= score or pb == b:
                pb -= 1
            if pb >= 1:
                count += 1
                pa += 1
                pb -= 1
    print(count)

### FIXED CODE ###

import math

if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        a, b = list(map(int, input().split()))
        prod = a*b
        rootInt = int(math.sqrt(prod))
        if a == b: print((a-1)*2)
        elif math.sqrt(prod) == rootInt:
            print((rootInt-2)*2+1)
        else:
            if rootInt*(rootInt+1) < prod:
                print((rootInt-1)*2+1)
            else:
                print((rootInt-1)*2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
h = tuple(map(int,input().split()))

def frog_2(N, K ,h):
    dp = [float("inf")] * (N)
    dp[0] = 0

    for n in range(1, N):
        k = max(0, n - K)
        dp[n] = min(abs(h[n] - h[i]) + dp[i] for i in range(k, n))
        
    return dp[-1]

print(frog_2(N,K,h))

### FIXED CODE ###

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

dp = [float('inf') for _ in range(n)]
dp[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        if i+j <= n-1:
            temp = dp[i] + abs(l[i+j] - l[i])
            if temp < dp[i+j]:
                dp[i+j] = temp

print(dp[-1])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort();C.sort()
M = 0
for i in range(N):
    low = 0
    high = N - 1
    t = (low + high) // 2
    if A[N-1] < B[i]:
        t = N-1
    elif A[0] >= B[i]:
        t = -1
    else:
        while (low <= high):
            if A[t] < B[i] <= A[t+1]:
                break
            elif B[i] <= A[t]:
                high = t
            elif A[t+1] < B[i]:
                low = t+1
            t = (low + high) // 2
    low = 0
    high = N - 1
    s = (low + high) // 2
    if C[N-1] <= B[i]:
        s = N-1
    elif B[i] < C[0]:
        s = -1
    else:
        while (low <= high):
            if C[s] <= B[i] < C[s+1]:
                break
            elif B[i] < C[s]:
                high = s
            elif C[s+1] <= B[i]:
                low = s + 1
            s = (low + high) // 2
    M += (t+1)*(N-s-1)
print(M)


### FIXED CODE ###

N = int(input())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
C = [0 for i in range(N)]
st = input().split()
for i in range(N):
    A[i] = int(st[i])
st = input().split()
for i in range(N):
    B[i] = int(st[i])
st = input().split()
for i in range(N):
    C[i] = int(st[i])
A.sort();C.sort()
M = 0
for i in range(N):
    low = 0
    high = N - 1
    t = (low + high) // 2
    if A[N-1] < B[i]:
        t = N-1
    elif A[0] >= B[i]:
        t = -1
    else:
        while (low <= high):
            if A[t] < B[i] <= A[t+1]:
                break
            elif B[i] <= A[t]:
                high = t
            elif A[t+1] < B[i]:
                low = t+1
            t = (low + high) // 2
    low = 0
    high = N - 1
    s = (low + high) // 2
    if C[N-1] <= B[i]:
        s = N-1
    elif B[i] < C[0]:
        s = -1
    else:
        while (low <= high):
            if C[s] <= B[i] < C[s+1]:
                break
            elif B[i] < C[s]:
                high = s
            elif C[s+1] <= B[i]:
                low = s + 1
            s = (low + high) // 2
    M += (t+1)*(N-s-1)
print(M)
### BUGGY CODE ###

n=int(input())
*x,=map(int,input().split())
s=sorted(x)
for i in x:
	if s.index(i)<=(n//2)-1:
		print(s[n//2])
	else:
		print(s[(n//2)-1])

### FIXED CODE ###

n=int(input())
*x,=map(int,input().split())
s=sorted(x)
m=(s[n//2]+s[(n//2)-1])/2
for i in x:
	if i<m:
		print(s[n//2])
	elif i==m:
		print(i)
	else: 
		print(s[(n//2)-1])
### BUGGY CODE ###

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

cnt = 0
dist = [a[0]-1] + a[1:]
for i, ai in enumerate(a[1:]):
    cnt += dist[:i+1].count(-ai)
    dist[:i+2] = list(map(lambda x: x-1, dist[:i+2]))

print(cnt)


### FIXED CODE ###

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

# i < j
# j - i = Aj + Ai
# j - Aj = i + Ai

ans = 0
adds = dict()
for j in range(n):
    sub = j - a[j]
    if sub in adds.keys():
        ans += adds[sub]

    add = j + a[j]
    if add in adds.keys():
        adds[add] += 1
    else:
        adds[add] = 1

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

import collections

h,w = map(int,input().split())

tizu = []
for i in range(h):
    s = list(input())
    tizu.append(s)

dy = [1,0,-1,0]
dx = [0,1,0,-1]

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = "#"
            
q = collections.deque()
for i in range(h): 
    for k in range(w):
        if tizu[i][k] == "#":
            q.append((i,k))
ans = 0
while True:
    flag = False
    l = len(q)
    for i in range(l):
        yx = q.popleft()
        f(yx[0],yx[1])
        #tizu[yx[0]][yx[1]] = "#"
        flag = True
    if flag == False:
        print(ans-1)
        exit()
    ans += 1

### FIXED CODE ###

import collections

h,w = map(int,input().split())
tizu = [list(input()) for i in range(h)]

dy = [1,0,-1,0]
dx = [0,1,0,-1]

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = "#"
            
q = collections.deque()
for i in range(h): 
    for k in range(w):
        if tizu[i][k] == "#":
            q.append((i,k))
ans = 0
while True:
    l = len(q)
    if l == 0:
        print(ans-1)
        exit()
    for i in range(l):
        yx = q.popleft()
        f(yx[0],yx[1])
    ans += 1
### BUGGY CODE ###

l=list(map(int,input().split()))
d=list(map(int,input().split()))
N=l[0]
K=l[1]
d_bar=[]
for m in range(10):
    if m not in d:
        d_bar.append(m) 
d_bar.sort()
n=[int(k) for k in str(N)]
dig1=''
dig2=0
for i in range(len(n)):
    for j in range(len(d_bar)):
        p=dig1+str(d_bar[j])
        if int(p)>l[0]:
            dig2=dig2*K**i+int(dig1)
            break
        dig1=p
        
dig2=dig2+1
r=dig2
q=dig2
R=[]
while q!=0 or q!=1:
    q=q//K
    r=q%K
    R.insert(0,r)
s=''
for t in range(len(R)):
    s=s+str(R[t])
print(int(s))




### FIXED CODE ###

l=list(map(int,input().split()))
d=list(map(int,input().split()))
u={i for i in range(10)}
d_bar=u-set(d)
d_bar={str(i) for i in d_bar}
n=l[0]
n_set=set(str(n))
while True:
    if n_set<=d_bar:
        print(n)
        break
    n=n+1
    n_set=set(str(n))
### BUGGY CODE ###

n, m = list(map(int, input().split()))
if n == m:
  print(0)
  exit()
h = list(map(int, input().split()))
maxi = sum(h)
f = [e for e in h]
# print(f)
for i in range(n - m - 1):
  for j in range(n - 1, i, -1):
    res = maxi
    for k in range(i, j):
      res = min(res, f[k] + max(0, h[j] - h[k]))
    f[j] = res
  # print(f)
print(min(f[n - m - 1:]))

### FIXED CODE ###

n, m = list(map(int, input().split()))
if n == m:
  print(0)
  exit()
h = list(map(int, input().split()))
maxi = sum(h)
f = [e for e in h]
# print(f)
for i in range(n - m - 1):
  for j in range(n - 1, i, -1):
    res = maxi
    for k in range(i, j):
      res = min(res, f[k] + max(0, h[j] - h[k]))
    f[j] = res
  # print(f)
print(min(f[n - m - 1:]))
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    s = list(input())
    s = deque(s)
    q = int(input())
    for _ in range(q):
        x = list(input().split())
        if x[0] == "1":
            l = len(s)
            for i in range(l//2):
                s[i],s[-i-1] = s[-i-1],s[i]
        else:
            if x[1] == "1":
                s.appendleft(x[2])
            else:
                s.append(x[2])
    
    print("".join(s))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    s = list(input())
    s = deque(s)
    q = int(input())
    count,b = 0,1
    for _ in range(q):
        x = list(input().split())
        if x[0] == "1":
            b *= -1
            count += 1
        else:
            if x[1] == "1":
                if b == 1:
                    s.appendleft(x[2])
                else:
                    s.append(x[2])
            else:
                if b == 1:
                    s.append(x[2])
                else:
                    s.appendleft(x[2])
    
    if count%2 != 0:
        s.reverse()
        
    print("".join(s))

if __name__ == "__main__":
    main()