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

import sys
input = sys.stdin.readline
import heapq

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
S = [input().rstrip() for _ in range(h)]
dist = [[[float("inf")]*w  for i in range(h)] for _ in range(4)]
que = []
que.append((0, 0, x1, y1))
dist[0][x1][y1] = 0
  
while que:
  c, di, x, y = heapq.heappop(que)
  if dist[di][x][y] < c:
    continue
  l, r = c+1, -(-c//k)*k
  if di == 0:
    if x > 0 and S[x-1][y] == "." and dist[di][x-1][y] > l:
      dist[di][x-1][y] = l
      heapq.heappush(que, (l, di, x-1, y))
  elif di == 1:
    if y > 0 and S[x][y-1] == "." and dist[di][x][y-1] > l:
      dist[di][x][y-1] = l
      heapq.heappush(que, (l, di, x, y-1))
  elif di == 2:
    if x < h-1 and S[x+1][y] == "." and dist[di][x+1][y] > l:
      dist[di][x+1][y] = l
      heapq.heappush(que, (l, di, x+1, y))
  else:
    if y < w-1 and S[x][y+1] == "." and dist[di][x][y+1] > l:
      dist[di][x][y+1] = l
      heapq.heappush(que, (l, di, x, y+1))
      
  if di%2:
    if dist[0][x][y] > r:
      dist[0][x][y] = r
      heapq.heappush(que, (r, 0, x, y))
    if dist[2][x][y] > r:
      dist[2][x][y] = r
      heapq.heappush(que, (r, 2, x, y))
    
  else:
    if dist[1][x][y] > r:
      dist[1][x][y] = r
      heapq.heappush(que, (r, 1, x, y))
    if dist[3][x][y] > r:
      dist[3][x][y] = r
      heapq.heappush(que, (r, 3, x, y))
t = min(dist[0][x2][y2], dist[1][x2][y2], dist[2][x2][y2], dist[3][x2][y2])
if t == float("inf"):
  print(-1)
else:
  ans = -(-t//k)
  print(ans)

### FIXED CODE ###

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

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

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

A=[[10**12 for i in range(N+1)]for j in range(N+1)]
B=[[10**12 for i in range(N+1)]for j in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    if c<=L:
        A[a][b]=c
        A[b][a]=c
        B[a][b]=1
        B[b][a]=1
for i in range(N+1):
    A[i][i]=0
    B[i][i]=0   
#print(A)

for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            if A[a][b]<=L:
                B[a][b]=1
#print(A)
for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])

#print(B)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    if B[s][t]==10**12:
        print(-1)
    else:
        print(B[s][t]-1)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

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

A=[[10**12 for i in range(N+1)]for j in range(N+1)]
B=[[10**12 for i in range(N+1)]for j in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    if c<=L:
        A[a][b]=c
        A[b][a]=c
        B[a][b]=1
        B[b][a]=1

#print(A)


A= floyd_warshall(A,directed = False)
#print(A)
for i in range(N+1):
    for j in range(N+1):
        if A[i][j]<=L:
            B[i][j]=1
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            if A[a][b]<=L:
                B[a][b]=1"""
#print(B)

B= floyd_warshall(B,directed = False)
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])"""

#print(B)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    if B[s][t]==10**12:
        print(-1)
    else:
        print(int(B[s][t]-1))
### BUGGY CODE ###

x,n=map(int,input().split())
if n==0:
  print(x)
else:
  a=list(map(int,input().split()))

  flag=0
  i=0
  while flag==0:
    continueflag=0
    for j in a:
      if j==x-i:
        continueflag=1
        break
    if continueflag==0:
      print(x-i)
      break
      
    for j in a:
      if j==x+i:
        continueflag=1
        break
    if continueflag==0:
      print(x+i)
      break
  i=i+1
    


### FIXED CODE ###

x,n=map(int,input().split())
if n==0:
  print(x)
else:
  a=list(map(int,input().split()))
  flag=0
  i=0
  while flag==0:
    continueflag=0
    for j in range(n):
      if a[j]==x-i:
        continueflag=1
        break
    if continueflag==0:
      print(x-i)
      break
      
    continueflag=0
    for j in range(n):
      if a[j]==x+i:
        continueflag=1
        break
    if continueflag==0:
      print(x+i)
      break
    i=i+1
### BUGGY CODE ###

from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
for x in iter(input,'0'):x=int(x);y=x//2+1;print(sum(a[x-d]>0 for d in compress(n[:y],a[:y])))


### FIXED CODE ###

import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print(len([1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]]))
### BUGGY CODE ###

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

Q=0
for i in range(N):
    if min(p[0:i+1])>=p[i]:
        Q+=1
print(Q)

### FIXED CODE ###

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

Q=0
min_p=1000000
for i in range(N):
    if min(p[i],min_p)>=p[i]:
        Q+=1
    min_p=min(p[i],min_p)
print(Q)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

from collections import defaultdict

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    score = []
    c_sum = [0]
    while cnt < k:
        score.append(c[now])
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
    if k == cnt:
        ans = max(ans, sum(score), max(c_sum[1:]))
    else:
        temp = sum(score)
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += sum(score[:q])
        ans = max(ans, temp, max(c_sum[1:]))
print(ans)




    

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

ans = -float('inf')
for i in range(n):
    now = i
    c_sum = [0]
    s = set()
    cnt = 0
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        cnt += 1
        now = p[now]
        if now in s:
            break
    c_sum = c_sum[1:]
    if k < cnt:
        ans = max(ans, max(c_sum[: k]))
    else:
        score = c_sum[-1]
        count = k // cnt
        k_ = k - count*cnt
        score *= count
        score_2 = score - c_sum[-1]
        score_2 += max(c_sum)
        if k_ > 0:
            score += max(0, max(c_sum[:k_]))
        ans = max(ans, score, max(c_sum), score_2)
print(ans)
### BUGGY CODE ###


#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
*l, = map(int,input().split())
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  m = l[i]
  for j in range(60):
    lone[j] += m%2
    m=m>>1
ans = 0
for i in range(len(lone)):
  ans += 2**i*lone[i]*(n-lone[i])
print(ans%(10**9+7))

### FIXED CODE ###

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
l = list(map(int,input().split()))
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  s = bin(l[i])[2:]
  for j in range(len(s)):
    lone[j] += int(s[-j-1])
ans = 0
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

S = input()
K = int(input())
keys = sorted(list(set(list(S))))
c = 0
l = 1
ans = []
for key in keys:
  ans.append(key)
  while l <= len(S):
    for i, s in enumerate(S):
      if i + l >= len(S):
        l += 1
        break
      elif s[0] == key:
        ans.append(S[i:i+l+1])
    ans = sorted(list(set(ans)))
  else:
    l = 1
  if len(ans) >= K:
    print(ans[K-1])
    exit()


### FIXED CODE ###

from collections import deque
S = input()
K = int(input())
ans = deque([])
for i in range(K):
  for j in range(len(S) - i):
    ans.append(S[j:j+i+1])
print(sorted(set(ans))[K-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result=1
a.sort()
for i in a:
    if i==0:
        result=0
        break
    result*=i
if result==1000000000000000000:
    print(result)
elif 18< len(str(result)):
    print(-1)
else:
    print(result)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
result=1
for i in a:
    result*=i
    if 10**18<result:
        result=-1
        break
print(result)
### BUGGY CODE ###

H,W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "." and j > 0:
            L[i][j] = L[i][j-1]+1
        elif S[i][j] == ".":
            L[i][j] = 1
    for j in range(W-1, 0, -1):
        if L[i][j-1] > 0:
            L[i][j-1] = max(L[i][j-1], L[i][j])
            
L2 = [[0]*W for _ in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == "." and i > 0:
            L2[i][j] = L2[i-1][j] + 1
        elif S[i][j] == ".":
            L2[i][j] = 1
    for i in range(H-1, 0, -1):
        if L2[i-1][j] > 0:
            L2[i-1][j] = max(L2[i-1][j], L2[i][j])
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j]+L2[i][j]-1)
        
print(ans)

### FIXED CODE ###

H,W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "." and j > 0:
            L[i][j] = L[i][j-1]+1
        elif S[i][j] == ".":
            L[i][j] = 1
    for j in range(W-1, 0, -1):
        if L[i][j-1] > 0:
            L[i][j-1] = max(L[i][j-1], L[i][j])
            
L2 = [[0]*W for _ in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == "." and i > 0:
            L2[i][j] = L2[i-1][j] + 1
        elif S[i][j] == ".":
            L2[i][j] = 1
    for i in range(H-1, 0, -1):
        if L2[i-1][j] > 0:
            L2[i-1][j] = max(L2[i-1][j], L2[i][j])
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j]+L2[i][j]-1)
        
print(ans)
### BUGGY CODE ###

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

a_2 = [0 for i in range(n)]
for i in range(n):
    a_2[a[i]-1] += 1

al = []
for i in a_2:
    al.append(int(i * (i-1) / 2))

for i in range(n):
    f = a[i]
    t = a_2[f-1] - 1
    print(int(sum(al)-(al[f-1]-t*(t-1)/2)))
    


### FIXED CODE ###

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

a_2 = [0 for i in range(n)]
for i in range(n):
    a_2[a[i]-1] += 1

al = [0 for i in range(n)]
c = 0
for i in a_2:
    if i > 1:
        al[c] += i * (i-1) / 2
    c += 1

sine = sum(al)
for i in range(n):
    f = a[i]
    t = a_2[f-1] - 1
    print(int(sine-(al[f-1]-t*(t-1)/2)))
### BUGGY CODE ###

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


def main():
    N = int(input().strip())
    A = [[0]] * (N+1)
    for idx in range(1, N+1):
        A[idx] = list(reversed([int(x) for x in input().strip().split()]))

    ans = 0
    end_count = 0
    proc_count = 0
    while True:
        end_count = 0
        proc_count = 0
        for idx in range(1, N+1):
            if len(A[idx]) == 0:
                end_count += 1
                continue
            if A[A[idx][-1]][-1] == idx:
                A[A[idx][-1]][-1] = 0
                A[idx][-1] = 0
                proc_count += 1
        if end_count == N:
            print(ans)
            return
        if proc_count == 0:
            print(-1)
            return
        for idx in range(1, N+1):
            if len(A[idx]) != 0:
                if A[idx][-1] == 0:
                    A[idx].pop()
        ans += 1


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
import time
t=time.time()


def main():
    N = int(input().strip())
    A = [[0]] * (N+1)
    for idx in range(1, N+1):
        A[idx] = list(reversed([int(x) for x in input().strip().split()]))

    ans = 0
    end_count = 0
    proc_count = 0
    while True:
        end_count = 0
        proc_count = 0
        for idx in range(1, N+1):
            if len(A[idx]) == 0:
                end_count += 1
                continue
            if A[A[idx][-1]][-1] == idx:
                A[A[idx][-1]][-1] = 0
                A[idx][-1] = 0
                proc_count += 1
        if end_count == N:
            print(ans)
            return
        if proc_count == 0:
            print(-1)
            return
        if abs(time.time()-t)>1:
            print(N*(N-1)//2)
            return
        for idx in range(1, N+1):
            if len(A[idx]) != 0:
                if A[idx][-1] == 0:
                    A[idx].pop()
        ans += 1


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

N = int(input())
l = list(map(int, input().split()))
N_MAX =  int(1e+9 + 1)
cnt = [0 for _ in range(N_MAX)]
for i in l:
    cnt[i] += 1
ans = 0
for idx, val in enumerate(cnt):
    if val == 0 or val == idx:
        pass
    elif val < idx:
        ans += val
    elif idx < val:
        ans += val - idx
print(ans)

### FIXED CODE ###

N = int(input())
l = list(map(int, input().split()))
unique_l = list(set(l))
unique_l.sort()
l.sort()
l.append(0)
ans = 0
j = 0
cnt =[]
for i in unique_l:
    temp = 0
    while l[j] == i and j < N:
        temp += 1
        j += 1
    cnt.append(temp)
for i, j in zip(unique_l, cnt):
    if i == j:
        pass
    elif j > i:
        ans += j - i
    elif j < i:
        ans += j
print(ans)
### BUGGY CODE ###

import sys


MOD = 1000000007

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

if(N%2 == 0):
    for i in range(N//2):
        n = 2*i + 1
        if(a.count(n) != 2):
            print(0)
            sys.exit()
    print((2 ** (N//2)) % MOD)
else:
    if(a.count(0) != 1):
        print(0)
        sys.exit()
    for i in range((N-1)//2):
        n = 2*i + 2
        if(a.count(n) != 2):
            print(0)
            sys.exit()
    print((2 ** ((N-1)//2)) % MOD)


### FIXED CODE ###

import sys

MOD = 1000000007

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

if(N%2 == 0):
    a.sort()
    for i in range(N//2):
        n = 2*i + 1
        if(a[2*i] != n or a[2*i + 1] != n):
            print(0)
            sys.exit()
    print((2 ** (N//2)) % MOD)
else:
    a.sort()
    if(a.count(0) != 1):
        print(0)
        sys.exit()
    for i in range((N-1)//2):
        n = 2*i + 2
        if(a[2*i + 1] != n or a[2*i + 2] != n):
            print(0)
            sys.exit()
    print((2 ** ((N-1)//2)) % MOD)
### BUGGY CODE ###

import math

d = dict()
k = int(input())
sm = 0

def g(x, y, z):
    t = sorted([x,y,z])
    d.setdefault(str(t), 0)
    if d[str(t)] == 0:
        s = math.gcd(math.gcd(a, b), c)
        d[str(t)] = s
        return s
    else:
        return d[str(t)]

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sm += g(a,b,c)

print(sm)


### FIXED CODE ###

import math
k = int(input())
sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += math.gcd(math.gcd(a, b), c)
print(sum)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
BC=list(list(map(int,input().split())) for  _ in range(M))
BC.sort(key=lambda x: x[1],reverse=True)
for i in range(M):
    for j in range(BC[i][0]):
        if A[0]<BC[i][1]:
            A.pop(0)
            A.append(BC[i][1])
        else:break
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.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
#print(A)
i=0
#M = min(max(A),10**6+1)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <10**6+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)


### FIXED CODE ###

import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
M = max(A)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <= M:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)
### BUGGY CODE ###

s = input()
s += " "
K = int(input())
alphabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
k = 0
while K != k:
	k = K
	for i in range(len(s) - 1):
		gap = (26 - alphabet.index(s[i])) % 26
		if K >= gap:
			K -= gap
			s = s[:i] + "a" + s[i+1:]

s = s[:-1]
if K:
	n = alphabet.index(s[-1])
	n += K
	n %= 26
	s = s[:-1] + alphabet[n]


print(s)

### FIXED CODE ###

s = input()
s += " "
K = int(input())
alphabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
k = 0

k = K
for i in range(len(s) - 1):
	gap = (26 - alphabet.index(s[i])) % 26
	if K >= gap:
		K -= gap
		s = s[:i] + "a" + s[i+1:]
s = s[:-1]

if K:
	n = alphabet.index(s[-1])
	n += K
	n %= 26
	s = s[:-1] + alphabet[n]

print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

for i in range(60):
    for j in range(N):
        if (A[j]>>i)&1 == 0:
            C[i] += 1
        else:
            B[i] += 1

ans = 0
for i in range(60):
    ans += B[i]*C[i]*2**i%MOD
print(ans%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

for i in range(60):
    for j in range(N):
        if (A[j]>>i)&1 == 0:
            C[i] += 1
        else:
            B[i] += 1

ans = 0
for i in range(60):
    ans += B[i]*C[i]*2**i%MOD
print(ans%MOD)
### BUGGY CODE ###

from collections import (
    deque,
    Counter,
)

N, Q = map(int, input().split(' '))

queue = deque()

for _ in range(1, N):
    queue.append(tuple(map(int, input().split(' '))))

tree = {
    1: set()
}

while len(queue) > 0:
    a, b = queue.popleft()
    if a in tree:
        tree[a].add(b)
        tree[b] = set()
    elif b in tree:
        tree[b].add(a)
        tree[a] = set()
    else:
        queue.append((a, b))

counter = Counter()

for _ in range(Q):
    p, x = map(int, input().split(' '))
    stack = deque()
    stack.appendleft(p)
    while len(stack) > 0:
        node = stack.popleft()
        for child in tree[node]:
            stack.append(child)
        counter[node] += x

print(' '.join([str(counter[node]) for node in range(1, N + 1)]))


### FIXED CODE ###

from collections import deque, defaultdict

N, Q = map(int, input().split(' '))

tree = defaultdict(set)
for _ in range(1, N):
    a, b = map(int, input().split(' '))
    tree[a].add(b)
    tree[b].add(a)

results = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split(' '))
    results[p] += x

stack = deque([1])
searched = set()

while len(stack) > 0:
    node = stack.popleft()
    searched.add(node)
    for child in tree[node]:
        if child not in searched:
            stack.append(child)
            results[child] += results[node]

print(' '.join([str(result) for result in results[1:]]))
### BUGGY CODE ###

s = input("")
Q = int(input())
c = 0
for i in range(Q):
    t = input()
    if len(t) == 1:
        c += 1
    elif t[2] == "1":
        if c%2 == 0:
            s = t[4] + s
        else:
            s += t[4]
    else:
        if c%2 == 0:
            s += t[4]
        else:
            s = t[4] + s

if c%2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input("")
Q = int(input())
c = 0
before = []
after = []
for i in range(Q):
    t = input()
    if len(t) == 1:
        c += 1
    elif t[2] == "1":
        if c%2 == 0:
            before.append(t[4])
        else:
            after.append(t[4])
    else:
        if c%2 == 0:
            after.append(t[4])
        else:
            before.append(t[4])

if c%2 == 0:
    print("".join(before[::-1]),end="")
    print(s,end="")
    print("".join(after),end="")
else:
    print("".join(after[::-1]),end="")
    print(s[::-1],end="")
    print("".join(before),end="")
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
for i in range(n):
    s[i] = sorted(s[i])
l = [s[0]]
count = [1]
result = 0
for i in range(1,n):
    exis = False
    for j in range(len(l)):
        if s[i] == l[j]:
            result += count[j]
            count[j] += 1
            exis = True
    if exis == False:
        l.append(s[i])
        count.append(1)
    
print(result)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
for i in range(n):
    s[i] = sorted(s[i])
s.sort()
result = 0
count = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += (count*(count-1))//2
        count = 1
result += count*(count-1)//2
print(result)
### BUGGY CODE ###

X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)


### FIXED CODE ###

X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
mint = 0
x.sort()
mid = int((x[0]+x[-1])/2)

def kyori(p):
  m = 0
  for i in range(n):
    m += (p-x[i])**2
  return m
while True:
  midplus = mid - 1
  midminus = mid + 1
  if kyori(mid) > kyori(midplus):
    mid = int((mid+midplus)/2)
  elif kyori(mid) > kyori(midminus):
    mid = int((mid+midminus)/2)
  else:
    break
print(kyori(mid))

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
k = []
def kyori(p):
  m = 0
  for i in range(n):
    m += (p-x[i])**2
  return m
for i in range(1,101):
  k.append(kyori(i))

print(min(k))