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

import sys
from collections import *
from heapq import *
from fractions import gcd
import itertools
import math

sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N, K = InMap()
P = InMap()
E = [(p+1)/2 for p in P]
Res = [sum(E[i:i+K]) for i in range(N-K+1)]
print(max(Res))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N, K = InMap()
P = InMap()

Res = [0]*(N - K + 1)
tmp = sum(P[0:K])
for i in range(K, N):
    Res[i-K] = tmp
    tmp -= P[i-K]
    tmp += P[i]
Res[-1] = tmp
print((max(Res) + K) / 2)
### BUGGY CODE ###

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値

L=1
L2=0
for i in range(n):
    count=0
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L2=j
                v+=1
                
            
        if count==k+1:
            ans=max(ans,j-L)
            #次はL2から始める
            L=L2
            break
            
        if s[j]=='E':
            ans=max(ans,j-L)
            print(ans)
            exit()

### FIXED CODE ###

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値

L=1
count=0
L2=[1]
for i in range(n):
    if i>=1:
        count-=1
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1):
            if s[j-1]==str(0):
                L2.append(j)
                
            
        if count==k+1:
            
            ans=max(ans,j-L2[i])
            #次はｊ+１から始める
            L=j+1
            break
            
        if s[j]=='E':
            ans=max(ans,j-L2[i])
            print(ans)
            exit()
### BUGGY CODE ###

n, k = map(int, input().split())
lst = list(map(int, input().split()))
for i in range(k):
    lit = [0 for _ in range(n)]
    for _ in range(0, n):
        mx = max(0,_ - lst[_])
        mn = min(n, _ + lst[_] +1)
        lit[mx:mn] = map(lambda x:x+1, lit[mx:mn])
    lst = lit
    if set(lst) == {n}:
        break
lst = [str(_) for _ in lst]
ans = ' '.join(lst)
print(ans)

### FIXED CODE ###

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

if n**(1/2) <= k:
    lst = [n for _ in range(n)]
    print(*lst)
else:
    for _ in range(k):
        ans = 0
        dp = [0] * (n + 1)
        for _ in range(n):  
            mx = max(0,_ - lst[_])
            mn = min(n, _ + lst[_] +1)
            dp[mx] += 1
            dp[mn] -= 1
        
        for _ in range(n):
            ans = ans + dp[_]
            lst[_] = ans

    print(*lst[:n])
### BUGGY CODE ###

N = int(input())
print(0, flush=True)
s0 = input()
if s0 == 'Vacant':
    exit()
l = 0
r = N-1

while r - l > 1:
    m = (l+r) // 2  # 中央値のクエリを送る
    print(m, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    if m & 2 == 1:  # r-lが奇数であることと同義
        if s != s0:  # 異性ならば
            l = m
        else:  # 同性ならば
            r = m
    else:  # r-lが奇数であることと同義
        if s != s0:  # 異性ならば
            r = m
        else:  # 同性ならば
            l = m
print(r, flush=True)
sr = input()


### FIXED CODE ###

# 円状に席が並んでいるので、空席を作ると男女の並びが不自然になるのは確か
# 男 空席 男 とやると一見空席が見つけられないような気がするが、それは円のどこかで同性同士が隣り合ってしまうので無理
# 空席の隣は必ず男と女である

N = int(input())
# Vacantがあるとそこで並びがずれる

# 0を基準とする
print(0, flush=True)  # 0番目の座席に対してリクエストを送る
s0 = input()
if s0 == "Vacant":
    exit()

l = 0  # ずれていない(ずれているかも)
r = N-1  # ずれている
while r - l > 1:
    m = (l+r) // 2  # 中央値のリクエストを送る
    print(m, flush=False)
    s = input()
    if s == 'Vacant':
        exit()
    if m % 2 == 1:
        if s != s0:
            l = m
        else:
            r = m
    else:
        if s != s0:
            r = m
        else:
            l = m
print(r, flush=True)
sr = input()
### BUGGY CODE ###

n, m = map(int,input().split())
plst = list(map(int,input().split()))
pare_inds = [i for i in range(n)]
belongs = [[] for i in range(n)]

def get_root(x):
  lst = []
  while pare_inds[x] != x:
    lst.append(x)
    x = pare_inds[x]
  for i in lst:
    pare_inds[i] = x
  return x

for i in range(m):
  x, y = map(int,input().split())
  x, y = x - 1, y - 1
  r_x, r_y  = get_root(x), get_root(y)
  if r_x < r_y:
    pare_inds[y] = r_x
    pare_inds[r_y] = r_x
  elif r_x > r_y:
    pare_inds[x] = r_y
    pare_inds[r_x] = r_y
#  print(x,y,p_x,p_y,pare_inds)

for i in range(n):
  belongs[get_root(i)].append(i)

ans = 0
for lst in belongs:
  for i in lst:
    if plst[i] - 1 in lst:
      ans += 1

print(ans)
#print(belongs)
#print(pare_inds)

### FIXED CODE ###

def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)
  #print(belongs)
  #print(plst)
  ans = 0
  for lst in belongs:
    lst2 = [plst[i] - 1 for i in lst]
    lst.sort()
    lst2.sort()
    ind1 = 0
    ind2 = 0
    end = len(lst)
    while ind1 < end and ind2 < end:
      if lst[ind1] == lst2[ind2]:
        ans += 1
        ind1 += 1
        ind2 += 1
      elif lst[ind1] < lst2[ind2]:
        ind1 += 1
      else:
        ind2 += 1
  
  print(ans)
solve()
### BUGGY CODE ###

import collections
N=int(input())
S=[]
for i in range(N):
    Si=input()
    S.append(Si)

C=collections.Counter(S)
max_C_list=[i[0] for i in C.items() if i[1]==max(C.values())]
ans_list=sorted(max_C_list)
for i in ans_list:
    print(i)

### FIXED CODE ###

import collections
N=int(input())
S=[input() for i in range(N)]

C=collections.Counter(S)
C_S=C.most_common()
m=C.most_common()[0][1]
ans=[]

for i in range(len(C_S)):
    if C_S[i][1]!=m:
        break
    else:
        ans.append(C_S[i][0])

ans.sort()

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

n, k = map(int, input().split())
p = list(int(i) for i in input().split())

kitai = list(map(lambda x: (x+1)/2, p))

gokei = []

for i in range(n-k+1):
    wa = sum(kitai[i:i+k])
    gokei.append(wa)

print(max(gokei))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(int(i) for i in input().split())

kitai = [(x+1)/2 for x in p]

rui_kitai = [kitai[0]]

for i in range(1, n):
    ruiseki=rui_kitai[i-1]+kitai[i]
    rui_kitai.append(ruiseki)

gokei = 0

for i in range(n-k+1):
    if i==0:
        wa = rui_kitai[k-1]
    else:
        wa = rui_kitai[i+k-1]-rui_kitai[i-1]
    if gokei < wa:
        gokei = wa

print(gokei)
### BUGGY CODE ###

from sys import stdin
from collections import namedtuple
from heapq import heappush, heappop

input = stdin.readline


class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n + 1)]
    self.rank = [0] * (n + 1)

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.rank[a] < self.rank[b]:
      a, b = b, a
    self.par[b] = a
    if self.rank[a] == self.rank[b]:
      self.rank[a] += 1

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  heappush(edges, Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  heappush(edges, Edge(abs(y1 - y2), a, b))

u = UnionFind(N)
cost = 0

while edges:
  w, s, t = heappop(edges)
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)


### FIXED CODE ###

from collections import namedtuple


class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n + 1)]
    self.size = [1] * (n + 1)

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)
### BUGGY CODE ###


def select2( val ):
  return( val*(val-1) // 2 ) 

N = int(input())
elms = input().split(" ")


ielms = []
for elm in elms:
  ielms.append( int(elm ))



test_dict = {}

for ielm in ielms:
  if( ielm in test_dict.keys() ):
    test_dict[ielm] += 1
  else:
    test_dict[ielm] = 1
               
for ielm in ielms:
  total = 0
  for dkey in test_dict.keys():
    if( ielm == dkey ):
      total += select2( test_dict[dkey]-1 )
    else:
      total += select2( test_dict[dkey] )
  print(total)
    

### FIXED CODE ###


def select2( val ):
  return( val*(val-1) // 2 ) 

N = int(input())
elms = input().split(" ")


ielms = []
for elm in elms:
  ielms.append( int(elm ))



test_dict = {}

for ielm in ielms:
  if( ielm in test_dict.keys() ):
    test_dict[ielm] += 1
  else:
    test_dict[ielm] = 1

total = 0
for dkey in test_dict.keys():      
  total += select2( test_dict[dkey] )
      
for ielm in ielms:
  print(total - select2( test_dict[ielm] ) + select2( test_dict[ielm]-1 ))
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    
    def seach(x):
        l = 0
        r = n - 1
        while True:
            i = (l + r) // 2
            if r - l <= 1:
                if b[r] == x:
                    return r
                else:
                    return l
            if b[i] < x:
                l = i
            elif b[i] > x:
                r = i
            else: 
                return i
    
    for i in range(n):
        j = seach(a[i])
        c = b[:j] + b[j+1:]
        print(c[n // 2 - 1])

        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    
    for i in range(n):
        if a[i] <=  b[n // 2 - 1]:
            print(b[n // 2])
        elif a[i] >  b[n // 2 - 1]:
            print(b[n // 2 - 1])
        
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
d = []
for i in range(n):
    tmp = int(input())
    d.append(tmp)

for i in range(n):
    if i == 0:
        print(max(d[1:]))
    elif i == n - 1:
        print(max(d[:-1]))
    else:
        print(max(d[i+1:] + d[:i]))


### FIXED CODE ###

n = int(input())
mv = 0
mi = 0
d = []
for i in range(n):
    tmp = int(input())
    if tmp > mv:
        mv = tmp
        mi = i
    else:
        d.append(tmp)

for i in range(n):
    if i == mi:
        print(max(d))
    else:
        print(mv)
### BUGGY CODE ###

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

stepper = 0

gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])

for i in range(N):
    i += 1
    counter = 0
    for k in gate:
        #print(k, i)
        if k[0] <= i <= k[1]:
            counter += 1
    #print(counter, M)
    if counter == M:
        stepper += 1

print(stepper)


### FIXED CODE ###

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

stepper = 0
gate = []

for j in range(M):
    gate_1, gate_2 = map(int, input().split())
    gate.append([gate_1, gate_2])

gate_min = 0
gate_max = N

for m in range(M):
    if gate[m][0] > gate_min:
        gate_min = gate[m][0]

    if gate[m][1] < gate_max:
        gate_max = gate[m][1]

#print(gate_min, gate_max)
for k in range(N):
    k = k+1
    if gate_min <= k <= gate_max:
        stepper += 1

print(stepper)
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    F = list(map(int, input().split()))
    F.sort(reverse=True)
    H = []
    for i in range(N):
        heapq.heappush(H, [-A[i] * F[i], A[i], F[i]])

    while K > 0:
        m1 = heapq.heappop(H)
        m2 = heapq.heappop(H)
        if m1[0] == 0:
            break
        x = max(1, m1[1] - (m2[1] * m2[2]) // m1[2])
        if x > K:
            x = K
        m1[1] -= x
        K -= x
        heapq.heappush(H, [-m1[1] * m1[2], m1[1], m1[2]])
        heapq.heappush(H, m2)

    print(-min(H)[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


# 解説AC
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)


def check(mid):
    k = K
    # 全員が目標値 mid を下回るまで修行できるか？
    for i in range(N):
        if A[i] * F[i] > mid:
            # x: 必要な修行回数
            x = A[i] - mid // F[i]
            k -= x
            # 誰かが修行できなかった ⇒ その目標値は達成不可能
            if k < 0:
                return False
    return True


def main():
    H = []
    for i in range(N):
        H.append(A[i]*F[i])
    # lb := 条件を満たさない最大, ub := 条件を満たす最小
    lb, ub = -1, max(H)
    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid):
            ub = mid
        else:
            lb = mid
    print(ub)


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

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
min = n
for i in range(k):
    left = one_index - i
    right = len(nums[one_index+1:]) + i
    if left < 0 or right < 0:
        continue
    else:
        min_tmp = math.ceil(left/(k-1))+math.ceil(right/(k-1))
        if min > min_tmp:
            min = min_tmp
print(min)


### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
if k == len(nums):
    print(1)
else:
    print(math.ceil((n-1)/(k-1)))
### BUGGY CODE ###

import numpy as np
MOD = 1000000007
#s = (list(input()))
s = [int(x) if x!="?" else -1 for x in reversed(input())]
#s = s[::-1]

dp = np.full((len(s), 13), 0, dtype="int64")

if s[0] == -1:
    dp[0][0:10] = 1
else:
    dp[0][int(s[0])] = 1

for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])
        for old_amari in range(13):
            new_amari = (value * pow(10, index) + old_amari) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (value * pow(10, index) + old_amari) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
    dp[index] = dp[index] % MOD

print(dp[len(s)-1][5])

### FIXED CODE ###

MOD = 1000000007
s = [int(x) if x!="?" else -1 for x in input()]
dp = [[0] *  13 for _ in range(len(s))] 

if s[0] == -1:
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
 
table = [ s % 13 for s in range(130)]
for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])
 
        for old_amari in range(13):
            new_amari = (table[old_amari * 10] + value) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (table[old_amari * 10] + value) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
 
    for i in range(len(dp[index])):
        dp[index][i] %= MOD

print(dp[len(s)-1][5])
### BUGGY CODE ###

N, M = map(int, input().split())
P = []
Y = []
for i in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)

Order = [None]*M

for v in set(P):
    l = filter(lambda x:x[1] == v, zip(range(M), P, Y))
    l_ = sorted(l, key = lambda x:x[2])
    
    for n in l_:
        Order[n[0]] = l_.index(n)+1
        
for (p, od) in zip(P, Order):
    print('{0:0>6d}{1:0>6d}'.format(p, od))

### FIXED CODE ###

N, M = map(int, input().split())
L = []
P = [0]*(N+1)
for i in range(M):
    p, y = map(int, input().split())
    L.append([i, p, y, 0])

L = sorted(L, key = lambda x:x[2])

for l in L:
    P[l[1]] += 1
    l[3] = P[l[1]]    
        
for l in sorted(L, key = lambda x:x[0]):
    print('{0:0>6d}{1:0>6d}'.format(l[1], l[3]))
### BUGGY CODE ###

n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]

city1=[[i for i in range(n)]]
city2=[[i for i in range(n)]]
rank1=[0 for i in range(n)]
rank2=[0 for i in range(n)]
s1=[{i} for i in range(n)]
s2=[{i} for i in range(n)]
city1.append(rank1)
city1.append(s1)
city2.append(rank2)
city2.append(s2)
def find(c,x,y):
  return root(c,x)==root(c,y)
def root(c,x):
  if x==c[0][x]:
    return x
  else:
    return root(c,c[0][x])
def union(c,x,y):
  if find(c,x,y):
    return
  else:
    rx=root(c,x)
    ry=root(c,y)
    if c[1][x]>c[1][y]:
      c[0][y]=rx
      c[2][rx]=c[2][rx]|c[2][ry]
    elif c[1][y]>c[1][x]:
      c[0][x]=ry
      c[2][ry]=c[2][rx]|c[2][ry]
    else:
      c[0][x]=ry
      c[1][x]+=1
      c[2][ry]=c[2][rx]|c[2][ry]
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
root1=[root(city1,i) for i in range(n)]
root2=[root(city2,i) for i in range(n)]
for i in range(n):
  ans=len(city1[2][root1[i]] & city2[2][root2[i]])
  if i==n:
    print(ans)
  else:
    print(ans,end=' ')

### FIXED CODE ###

from collections import Counter
n,k,l=map(int,input().split())
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    return root(c,c[x])
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[rx]=ry
  else:
    c[ry]=rx
for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')
### BUGGY CODE ###

from bisect import bisect_left
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B, C = map(int, input().split())
    b = bisect_left(A,C)
    if B>=b:
        A[:b] = [C for _ in range(b)]
    else:
        A[:B] = [C for _ in range(B)]
    A.sort()
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
n = 0
i = 0
m = 0
while A[i]<BC[n][1]:
    A[i] = BC[n][1]
    m = m+1
    if m >=BC[n][0]:
        m = 0
        n = n+1
    i += 1
    if n==M:
      break
    if i == N:
      break
print(sum(A))
### BUGGY CODE ###

def d():
    S = str(input())
    Q = int(input())
    rvs = False

    for i in range(Q):
        q = list(input().split())

        if q[0] == '1':
            rvs = not rvs
        elif q[0] == '2':
            if q[1] == '1':
                if rvs:
                    S = S + q[2]
                else:
                    S = q[2] + S
            elif q[1] == '2':
                if rvs:
                    S = q[2] + S
                else:
                    S = S + q[2]
            else:
                raise ValueError(
                    'F({}) is {}, which is invalid!'.format(i, q[1]))
        else:
            raise ValueError('T({}) is {}, which is invalid!'.format(i, q[0]))

    if rvs:
        S = S[::-1]
    print(S)


def dd(S):
    print()


##########
d()


### FIXED CODE ###

def d():
    from collections import deque
    S = deque(str(input()))
    Q = int(input())
    rvs = False

    for i in range(Q):
        q = list(input().split())

        if q[0] == '1':
            rvs = not rvs
        elif q[0] == '2':
            if q[1] == '1':
                if rvs:
                    S.append(q[2])
                else:
                    S.appendleft(q[2])
            elif q[1] == '2':
                if rvs:
                    S.appendleft(q[2])
                else:
                    S.append(q[2])
            else:
                raise ValueError(
                    'F({}) is {}, which is invalid!'.format(i, q[1]))
        else:
            raise ValueError('T({}) is {}, which is invalid!'.format(i, q[0]))

    if rvs:
        ans = list(S)[::-1]
    else:
        ans = list(S)
    print(''.join(ans))


##########
if __name__ == "__main__":
    d()