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

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
BI=[(b,i) for i,b in enumerate(B)]

# Segment tree(1-indexed,再帰を使わないもの)

seg_el=1<<(N.bit_length())# Segment treeの台の要素数
SEG=[(0,0)]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N):
    SEG[i+seg_el]=BI[i]

for i in range(seg_el-1,0,-1):# 親の部分もupdate
    SEG[i]=max(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):# A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1# 子ノードへ
    
    while i!=0:
        SEG[i]=max(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):# 区間[l,r)に関するmaxを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=(0,0)

    while L<R:
        if L & 1:
            ANS=max(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=max(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

ANS=0
while True:
    x,y=getvalues(0,N)
    if x==0:
        break
    if x<A[y]:
        print(-1)
        sys.exit()

    elif x==A[y]:
        update(y,(0,y),seg_el)

    else:
        B[y]-=B[(y+1)%N]+B[(y-1)%N]
        ANS+=1
        update(y,(B[y],y),seg_el)

print(ANS)
        

            


### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
BI=[(b,i) for i,b in enumerate(B)]

# Segment tree(1-indexed,再帰を使わないもの)

seg_el=1<<(N.bit_length())# Segment treeの台の要素数
SEG=[(0,0)]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N):
    SEG[i+seg_el]=BI[i]

for i in range(seg_el-1,0,-1):# 親の部分もupdate
    SEG[i]=max(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):# A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1# 子ノードへ
    
    while i!=0:
        SEG[i]=max(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):# 区間[l,r)に関するmaxを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=(0,0)

    while L<R:
        if L & 1:
            ANS=max(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=max(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

ANS=0
while True:
    x,y=getvalues(0,N)
    if x==0:
        break
    if x<A[y]:
        print(-1)
        sys.exit()

    elif x==A[y]:
        update(y,(0,y),seg_el)

    else:
        t=B[(y+1)%N]+B[(y-1)%N]
        if B[y]<t+A[y]:
            print(-1)
            sys.exit()
            
        q=(B[y]-A[y])//t
        ANS+=q
        B[y]-=t*q
        update(y,(B[y],y),seg_el)

print(ANS)
### BUGGY CODE ###

INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        ans = D[lst[1] - 1][lst[2] - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(n):
            D[i][j] = min(D[i][j], D[i][a - 1] + c + D[b - 1][j], D[i][b - 1] + c + D[a - 1][j])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

n = int(input())
ls = list(map(int, input().split()))
for i in range(n):
    j = ls.index(i + 1)
    print(j + 1, end = " ")


### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
ls2 = [0 for i in range(n)]
for j in range(n):
    a = ls[j]
#aは出席番号j+1番目の順位
    ls2[a - 1] = j + 1
for k in range(n):
    print(ls2[k], end = " ")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a,b,x = map(int,input().split())
L = []
for i in range(a,b+1):
  if i % x == 0:
    L.append(1)
print(sum(L))

### FIXED CODE ###

a,b,x = map(int,input().split())

def func(i):
    if i != -1:
        return i//x+ 1
    else:
        return 0

print(func(b) - func(a-1))
### BUGGY CODE ###

N = int(input())
numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
Ans = 0

for i in range(1,N+1):
  numlist[i] = float(input()) * 1000000000

  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break
  
  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break
  
for i in range(1,N+1):
  for j in range(i+1,N+1):
    if log2[i] + log2[j] >= 18 and log5[i] + log5[j] >= 18:
      Ans += 1
  
print(Ans)


### FIXED CODE ###

from decimal import Decimal
N = int(input())
#numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  #numlist[i] = Decimal(input()) * 1000000000
  wk = Decimal(input())
  wk = int(wk * 1000000000)

  #wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))
### BUGGY CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.insert(0,0)

ans = 0
time = 0
for i in range(len(a)):
    tmp = i
    time += a[i]
    if time > k:
        break
    tmp_time = time
    for j in range(len(b)):
        if tmp_time + b[j] <= k:
            tmp_time += b[j]
            tmp += 1
        else:
            break
    ans = max(ans,tmp)
print(ans)


### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.insert(0,0)
b.insert(0,0)

sum_a = [0]
for i in range(1,n+1):
    sum_a.append(sum_a[i-1] + a[i])

sum_b = [0]
for i in range(1,m+1):
    sum_b.append(sum_b[i-1] + b[i])

ans = 0
for i in range(n+1):
    if sum_a[i] > k:
        break
    for j in range(m,-1,-1):
        if sum_a[i] + sum_b[j] <= k:
            ans = max(ans, i+j)
            m = j
            break
print(ans)
### BUGGY CODE ###

def main(X, Y):
    M = len(Y)
    dp = [0]*(M+1)
    dp_s = [""]*(M+1)
    for i, x in enumerate(X):
        dp_pre = dp[:]
        dp_s_pre = dp_s[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp_pre[j] + 1
                dp_s[j+1] = dp_s_pre[j] + x
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                dp_s[j+1] = dp_s[j]
    return print(dp_s[M])


if __name__ == "__main__":
    X = input()
    Y = input()
    main(X, Y)


### FIXED CODE ###

import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def i(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    S = s()
    T = s()
    dp = [[0] * len(T) for _ in range(len(S))]
    dp[0][0] = int(S[0] == T[0])
    check = [[None] * len(T) for _ in range(len(S))]
    ok = (10, 10)
    check[0][0] = ok if dp[0][0] else (0, 0)
    for i in range(1, len(S)):
        if S[i] == T[0]:
            dp[i][0] = 1
            check[i][0] = ok
        else:
            dp[i][0] = dp[i - 1][0]
            check[i][0] = (-1, 0)
    for j in range(1, len(T)):
        if T[j] == S[0]:
            dp[0][j] = 1
            check[0][j] = ok
        else:
            dp[0][j] = dp[0][j-1]
            check[0][j] = (0, -1)
    for i in range(1, len(S)):
        for j in range(1, len(T)):
            if S[i] == T[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                check[i][j] = (-1, -1)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j] > dp[i][j - 1]:
                    check[i][j] = (-1, 0)
                else:
                    check[i][j] = (0, -1)

    ans = ""
    i = len(S)-1
    j = len(T)-1
    for _ in range(len(S) + len(T)):
        if check[i][j] == ok:
            ans = S[i] + ans
            break
        else:
            if check[i][j] == (-1, -1):
                ans = S[i] + ans
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
            else:
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
    #print(*check, sep="\n")
    print(ans)


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

from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()

    b = [0]*(n+1)
    for i in range(n,-1,-1):
        if i == n:
            b[i] = a[i]
        else:
            b[i] = min(b[i+1]+a[i],2**i)

    for i in range(n+1):
        if i!=0:
            b[i] = min(2*(b[i-1]-a[i-1]),b[i])
        if b[i]<a[i]:
            end()
    print(sum(b))
    return
 
if __name__=='__main__':
    main()

### FIXED CODE ###

from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    a = deque(LI())
    if n==0:
        if a[0] == 1:
            print(1)
            exit()
        else:
            end()
    elif a[0]!=0:
        end()

    b = [0]*(n+1)
    for i in range(n,-1,-1):
        if i == n:
            b[i] = a[i]
        else:
            b[i] = min(b[i+1]+a[i],2**i)

    for i in range(n+1):
        if i!=0:
            b[i] = min(2*(b[i-1]-a[i-1]),b[i])
        if b[i]<a[i]:
            end()
    print(sum(b))
    return
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

import itertools
n = int(input())
s = tuple(map(int, input()))
f = []
ans = 0

for i in range(n-2):
    right = n - 1
    if s[i] in f:
        continue
    else:
        f.append(s[i])
        left = i + 1
        a = tuple(set(itertools.combinations(s[left:right+1], 2)))
        ans += len(a)

print(ans)


### FIXED CODE ###

n = int(input())
s = tuple(map(int, input()))
f = [
    [] for i in range(10)
]
ans = 0

for i in range(n-2):
    if len(f[s[i]]) != 0:
        continue
    else:
        for j in range(i+1, n-1):
            if s[j] in f[s[i]]:
                continue
            else:
                f[s[i]].append(s[j])
                a = tuple(set(s[j+1:]))
                ans += len(a)

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

n=int(input())

ans=0
s=list(str(input()))
r=[]
b=[]
g=[]
for i in range(n):
    if s[i]=='R':
        r.append(i)
    if s[i]=='B':
        b.append(i)
    if s[i]=='G':
        g.append(i)
count=0
aida=1

while aida*2-1<=n:
    for i in range(n-aida*2):
        #print("DF")
       # print(s[i],i,s[i+aida],i+aida,s[i+aida*2],i+aida*2)
        aa=set()
        aa.add(s[i])
        aa.add(s[i+aida])
        aa.add(s[i+aida*2])
        #print(aa)
        if len(aa)==3:
            count+=1
    aida+=1
#print(count)

print(len(r)*len(b)*len(g)-count)


### FIXED CODE ###

n=int(input())

ans=0
s=list(str(input()))
r=[]
b=[]
g=[]
for i in range(n):
    if s[i]=='R':
        r.append(i)
    if s[i]=='B':
        b.append(i)
    if s[i]=='G':
        g.append(i)
count=0
aida=1

while aida*2-1<=n:
    for i in range(n-aida*2):
        #print("DF")
       # print(s[i],i,s[i+aida],i+aida,s[i+aida*2],i+aida*2)
        aa=set()
        aa.add(s[i])
        aa.add(s[i+aida])
        aa.add(s[i+aida*2])
        #print(aa)
        if len(aa)==3:
            count+=1
    aida+=1
#print(count)

print(len(r)*len(b)*len(g)-count)
### BUGGY CODE ###

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

result = 0

if n <= 2:
    print(0)
    
for i in range(n-2):
    for j in range(i+1, n-1):
        rgb = ["R", "G", "B"]
        rgb.remove(s[i])
        if s[j] in rgb:
            rgb.remove(s[j])
            for k in range(j+1, n):
                if s[k] in rgb:
                    if j-i != k-j:
                        result += 1
print(result)

### FIXED CODE ###

n = int(input())
s = input()
 
result = 0
 
if n <= 2:
    print(0)

for i in range(n-2):
    if s[i] == "R":
        a = s[i+1:].count("G")
        b = s[i+1:].count("B")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "G" and s[i+2*j] == "B") or (s[i+j] == "B" and s[i+2*j] == "G"):
                result -= 1
    elif s[i] == "G":
        a = s[i+1:].count("R")
        b = s[i+1:].count("B")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "R" and s[i+2*j] == "B") or (s[i+j] == "B" and s[i+2*j] == "R"):
                result -= 1
    elif s[i] == "B":
        a = s[i+1:].count("R")
        b = s[i+1:].count("G")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "R" and s[i+2*j] == "G") or (s[i+j] == "G" and s[i+2*j] == "R"):
                result -= 1
print(result)
### BUGGY CODE ###

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

n = int(raw_input())
A = map(int, raw_input().split())
count = 0
for i in range(n):
    for j in range(i, n):
        if A[i] > A[j]:
            count += 1
print count

### FIXED CODE ###

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

import sys

def merge(A, left, mid, right):
    global count
    n1 = mid-left
    n2 = right-mid
    L = [0]*(n1+1)
    R = [0]*(n2+1)
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = R[n2] = sys.maxint
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            count += n1-i

def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left+right)/2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

n = int(raw_input())
S = map(int, raw_input().split())
count = 0
mergeSort(S, 0, n)
print count
### BUGGY CODE ###

import itertools
n = int(input())
score = [ int(input()) for _ in range(n)]
cnt = max([sum(c) if sum(c) % 10 != 0 else 0 for i in sorted(range(1, n+1)) for c in itertools.combinations(score, i)])
print(cnt)


### FIXED CODE ###

import itertools
n = int(input())
score = [ int(input()) for _ in range(n)]
cnt = max([sum(c) if sum(c) % 10 != 0 else 0 for i in sorted(range(n-1, n+1)) for c in itertools.combinations(score, i)])
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
i = 0
while(i==0):
  a = abs(n-k)
  if a<n:
    n = a
  else:
    print(n)
    exit()

### FIXED CODE ###

n,k = map(int,input().split())
i = 0
while(i==0):
  #print(n,k)
  if n>k:
    a = n%k
    if a<n:
      n = a
  else:
    a = abs(k-n)
    if a<n:
      n = a
    else:
      print(n)
      exit()
### BUGGY CODE ###

def solve():
    n = int(input())
    dp = [[0] * 1005 for _ in range(1005)]
    for _ in range(n):
        x = input()
        y = input()
        len_x = len(x)
        len_y = len(y)
        for i in range(len_x):
            for j in range(len_y):
                if x[i] == y[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        print(dp[len_x][len_y])
solve()



### FIXED CODE ###

for _ in range(int(input())):
    a = input()
    b = input()
    if len(a) < len(b):
        a, b = b, a
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys

N,W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
  w[i],v[i] = map(int, input().split())

dp = [float('inf')] * (10**5+1)
dp[0] = 0

MAX_V = 0
for i in range(N):
  MAX_V += v[i]
  for j in range(MAX_V,-1,-1):
    if j >= v[i] and dp[j-v[i]]+w[i] <= W:
      dp[j] = min(dp[j], dp[j-v[i]]+w[i])

ans = 0
for i in range(len(dp)):
  if dp[i] < float('inf'):
    ans = max(ans, i)
print(ans)

### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys

N,W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
  w[i],v[i] = map(int, input().split())

dp = [float('inf')] * (sum(v)+1)
dp[0] = 0

MAX_V = 0
ans = 0
for i in range(N):
  MAX_V += v[i]
  for j in range(MAX_V,-1,-1):
    if j >= v[i] and dp[j-v[i]]+w[i] <= W:
      ans = max(ans,j)
      dp[j] = min(dp[j], dp[j-v[i]]+w[i])
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
d=dict(zip(list(range(2019)),[0]*2019))
d[0]=1
j=1
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  d[now]+=1
  j*=10
ans=0
for _,i in d.items():
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
d=[0]*2019
d[0]=1
j=1
ans=0
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  ans+=d[now]
  d[now]+=1
  j*=10
  j%=2019
print(ans)
### BUGGY CODE ###

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

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split(' '))
    cnt = 0
    x, y = comp[l]
    while l != r:
        l += d
        i, j = comp[l]
        cnt += abs(x - i) + abs(y - j)
        x, y = i, j

    print(cnt)

### FIXED CODE ###

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

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]

q = int(input())
lr = [map(int, input().split(' ')) for _ in range(q)]

dp = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    cnt = dp[i - d]
    cnt += abs(comp[i][0] - comp[i - d][0])
    cnt += abs(comp[i][1] - comp[i - d][1])    
    dp[i] = cnt
    

for l, r in lr:
    print(dp[r] - dp[l])
### BUGGY CODE ###



def main():
    import math
    import collections
    import numpy as np

    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

    # As = np.tile(A, (N, 1))
    # As = [A]*N
    # print(As)
    for i in range(N):
        x = A[i]
        A[i] = 0
        tmp_A = collections.Counter(A)
        su = 0
        for pairs in sorted(tmp_A.values(), reverse=True):
            if pairs >= 2:
                su += combinations_count(pairs, 2)
            else:
                break
        A[i] = x
        print(su)


if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    import collections

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

    allc = collections.Counter(A)
    # all_list = [0]*N
    allsu = 0
    for pairs in sorted(allc.values(), reverse=True):
        allsu += pairs*(pairs-1)//2

    for a in A:
        num = allc[a]
        print(allsu - (num-1))

    # for i in range(N):
    #     x = A[i]
    #     A[i] = 0
    #     tmp_A = cc(A)
    #     su = 0
    #     for pairs in sorted(tmp_A.values(), reverse=True):
    #         if pairs >= 2:
    #             su += pairs*(pairs-1)//2
    #         else:
    #             break
    #     A[i] = x
    #     print(su)


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

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

ans = input()
q = int(input())
num = 0

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans = query[2] + ans
      else:
        ans = ans + query[2]
    else:
      if num%2 == 0:
        # 後方
        ans = ans + query[2]
      else:
        ans = query[2] + ans

if num%2 == 0:
  print(ans)
else:
  print(ans[::-1])

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
num = 0
ans = deque(s)

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:
      if num%2 == 0:
        # 後方
        ans.append(query[2])
      else:
        ans.appendleft(query[2])     

if num%2 == 0:
  print(''.join(ans))
else:
  ans.reverse()
  print(''.join(ans))