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

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

M = h + w
blck = [M]*(w+2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [M]*(w+2)
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 0
    data += [lineN]
data += [blck]
def cp(d, s):
    d[0] = s[0]
    d[1] = s[1]
def ad(d, s):
    d[0] += s[0]
    d[1] += s[1]
def eq(d, s):
    return d[0] == s[0] and d[1] == s[1]
def eql(d, s):
    return d[0] == s[0] or d[1] == s[1]
def mn(s):
    return [-s[0], -s[1]]


cur = [0] * 2
curE = [0] * 2
addS = [0] * 2
addE = [0] * 2

for d in range(1, -2, -2):
    if d == 1:
        curS, curW, addS, addE, mov= [[1, 1], [h+1, w+1], [0, 1], [1, 0], [1, -1]]
    else:
        curS, curW, addS, addE, mov= [[h, w], [0, 0], [0, -1], [-1, 0], [-1, 1]]
    cp(curE, curS)

    for i in range(w+h-1):

        cp(cur, curS)

        while True:
            x = cur[0]
            y = cur[1]
            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

            if eq(cur, curE):
                break
            ad(cur, mov)

        ad(curS, addS)
        if eql(curS, curW):
            ad(curS, mn(addS))
            cp(addS, [addS[1], -addS[0]])
            ad(curS, addS)

        ad(curE, addE)
        if eql(curE, curW):
            ad(curE, mn(addE))
            cp(addE, [-addE[1], addE[0]])
            ad(curE, addE)

print(max((data[x][y] for x in range(1, h+1) for y in range(1, w+1))))


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in reversed(S):
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(k * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))


### FIXED CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))
### BUGGY CODE ###

import numpy as np
ans=10**9
N,C=map(int,input().split())
s=[list(map(int,input().split())) for i in range(C)]
t=[list(map(int,input().split())) for i in range(N)]
u=[np.zeros((C)) for i in range(3)]
for i in range(N):
    for j in range(N):
        pass
        u[(i+j)%3]+=np.array(s[t[i][j]-1])
from itertools import permutations
for i,j,k in list(permutations(range(C),3)):
    p=u[0][i]+u[1][j]+u[2][k]
    ans=min(ans,p)
print(int(ans))    


### FIXED CODE ###

import numpy as np
N,C=map(int,input().split())
ans=10**9
a=np.array([0]*C)
b=np.array([0]*C)
c=np.array([0]*C)
s=[]
t=[]
for i in range(C):
    s.append(list(map(int,input().split())))
for i in range(N):
    t.append(list(map(int,input().split())))
for j in range(N):
    for i in range(N):
        if (i+j)%3==0:
            a+=np.array(s[t[i][j]-1])
        elif (i+j)%3==1:
            b+=np.array(s[t[i][j]-1])
        else:
            c+=np.array(s[t[i][j]-1])
from itertools import permutations
for i,j,k in permutations(range(C),3):
    p=a[i]+b[j]+c[k]
    ans=min(p,ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))
### BUGGY CODE ###

import numpy as np
 
N, K = map(int, input().split())
new_list_a = sorted(list(map(int, input().split())), reverse=True)
new_list_f = sorted(list(map(int, input().split())))
 
new_list_a = np.array(new_list_a)
new_list_f = np.array(new_list_f)
time = new_list_f * new_list_a
 
for i in range(K):
  number_a = np.argmax(time)
  new_list_a[number_a] = new_list_a[number_a] - (i - (i - 1))
  time = new_list_f * new_list_a
  
print(max(time))

### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = {}
DP[(0, 0)] = 0

for wa in range(1, N+1):
    # AA[:wa]までを考える
    a, i = AA[wa-1]
    for x in range(wa+1):
        y = wa - x
        DP[(x, y)] = 0
        if x - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x-1, y)]+a*(i-x))
        if y - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x, y-1)]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

print(max([DP[(x, N-x)] for x in range(N+1)]))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = {}
DP[(0, 0)] = 0

for wa in range(1, N+1):
    # AA[:wa]までを考える
    a, i = AA[wa-1]
    for x in range(wa+1):
        y = wa - x
        DP[(x, y)] = 0
        if x - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x-1, y)]+a*(i-x))
        if y - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x, y-1)]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

print(max([DP[(x, N-x)] for x in range(N+1)]))
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
n=0
for i in range(a,b+1):
  if i%c!=0 and i%d!=0:
    n=n+1
print(n)

### FIXED CODE ###

import fractions

a,b,c,d=map(int,input().split())
g=int(fractions.gcd(c,d))
l=int((c*d)/g)

print(b-a+1-int(b//c)+int((a-1)//c)-int(b//d)+int((a-1)//d)+int(b//l)-int((a-1)//l))
### BUGGY CODE ###

def main():
    import sys
    
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    
    set_a = set(A)
    
    d = {}
    comb_sum = 0
    
    for i in set_a:
        n = A.count(i)
        if n == 1:
            comb = 0
            comb_ex = 0
        else:
            comb = n * (n - 1) / 2
            comb_ex = (n - 1) * (n - 2) / 2
        comb_sum += comb
        d[i] = comb_ex - comb
     
    for n in A:
        ans = int(d[n] + comb_sum)
        print(ans)
      
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import Counter
    
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    
    count = Counter(A)
    
    d = {}
    comb_sum = 0
    
    for i, n in count.items():
        if n == 1:
            comb = 0
            comb_ex = 0
        else:
            comb = n * (n - 1) / 2
            comb_ex = (n - 1) * (n - 2) / 2
        comb_sum += comb
        d[i] = comb_ex - comb
     
    for n in A:
        ans = int(d[n] + comb_sum)
        print(ans)

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

s = input()
K = int(input())
visited = [False] * len(s)
substrings = set()
for lc in "abcdefghijklmnopqrstuvwxyz":
    for i in range(len(s)):
        if visited[i] or s[i] != lc:
            continue
        visited[i] = True
        for j in range(i + 1, len(s) + 1):
            substrings.add(s[i:j])
    if len(substrings) >= K:
        break
print(sorted(list(substrings))[K - 1])


### FIXED CODE ###

s = input()
K = int(input())
s_dic = {c: [] for c in "abcdefghijklmnopqrstuvwxyz"}
for i, c in enumerate(s):
    s_dic[c].append(i)
substrings = set()
for indices in s_dic.values():
    for i in indices:
        for j in range(i + 1, i + K + 1):
            substrings.add(s[i:j])
print(sorted(list(substrings))[K - 1])
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]

for i in range(n):
    a=l[i]
    l.remove(a)
    #print(a,l)
    print(max(l))
    l.insert(i,a)


### FIXED CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
l_sorted = sorted(l)

for i in range(n):
    if l[i] == l_sorted[-1]:
        print(l_sorted[-2])
    else:
        print(l_sorted[-1])
### BUGGY CODE ###

def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x] += self.size[y]
            self.size[y] = 0

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)



n,m = getMN()

bridges = []

for i in range(m):
    a,b = getMN()
    bridges.append([a,b])

bridges.reverse()

uf = UnionFind(n)
answers = []
for query in bridges:
    x,y = query
    if not uf.same_check(x-1,y-1):
        uf.union(x-1,y-1)
    ans = 0
    for si in uf.size:
        ans += si * (n-si)
    answers.append(ans//2)

for fa in answers[:-1][::-1]:
    print(fa)
print(n*(n-1)//2)

### FIXED CODE ###

def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x] += self.size[y]
            self.size[y] = 0

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)



n,m = getMN()

bridges = []

for i in range(m):
    a,b = getMN()
    bridges.append([a,b])

bridges.reverse()

uf = UnionFind(n)
ans = n*(n-1)//2
answers = [ans]
for query in bridges:
    x,y = query
    if not uf.same_check(x-1,y-1):
        #print(uf.size,x,y)
        ans -= uf.size[uf.find(x-1)]*uf.size[uf.find(y-1)]
        #print(uf.find(x-1))
        uf.union(x-1,y-1)

    answers.append(ans)

for fa in answers[:-1][::-1]:
    print(fa)
### BUGGY CODE ###

N = int(input())
# print(N)
kyaku = 0
mise = 0

while N:
    # print(N, kyaku, mise)
    c = N%10
    if c == 5 and N%100-c >= 50:
        mise += 10 - c
        N += 10
    elif c <= 5:
        kyaku += c
    else:
        mise += 10-c
        N += 10
    N = N//10

print(kyaku+mise)

### FIXED CODE ###

NN = 2020202
MOD = 10**9+7
INF = float("inf")

A = input()
N = [0]*len(A)
for i in range(len(A)):
    N[i] = int(A[i])
N = N[::-1]
N.append(0)
kyaku = 0
mise = 0

for i in range(len(N)-1):
    # print(N, kyaku, mise)
    if N[i] == 5 and N[i+1] >= 5:
        mise += 10 - N[i]
        N[i+1] += 1
    elif N[i] <= 5:
        kyaku += N[i]
    else:
        mise += 10-N[i]
        N[i + 1] += 1

if N[-1] == 1:
    kyaku += 1

print(kyaku+mise)
### BUGGY CODE ###

input_s = input()
len_s = len(input_s)
ans = 0

for i in range(len_s - 4):
    for j in range(i+3, len_s):
        if (int(input_s[i:j+1]) % 2019) == 0:
            ans += 1
            i = j - 1
            break

print(ans)


### FIXED CODE ###

s = input()[::-1]
n = len(s)
x = 1
tot = 0 # 累積和
cnt = [0 for i in range(2019)] # 累積和の値になる個数

ans = 0
for i in range(n):
    # print('======={}======'.format(i))
    cnt[tot] += 1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    # print(tot)
    ans += cnt[tot]
    # print('ans:', ans)
    x = x*10%2019

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

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
st = s.count('1')
num = 0
for i,x in enumerate(s[::-1]):
    if x == '1': num += pow(2,i)
for i in range(n):
    ntmp = pow(2,n-i-1)
    if s[i] == '0':
        nnow = num + ntmp
        stnow = st + 1
    else:
        nnow = num - ntmp
        stnow = st - 1
    res = 0
    while nnow:
        # print(nnow)
        nnow %= stnow
        stnow = bin(nnow).count('1')
        res += 1
    print(res)



### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

m = 2*10**5+10
ans = [0] * m
for i in range(1,m):
    nnow = i
    res = 0
    stnow = bin(nnow).count('1')
    while nnow:
        # print(nnow)
        nnow %= stnow
        stnow = bin(nnow).count('1')
        res += 1
    ans[i] = res
# for i in range(10):
#     print(i,ans[i])
n = inp()
s = list(input())
tmp = s.count('1')
stm = tmp-1
stp = tmp+1
numm = 0
nump = 0
for i,x in enumerate(s):
    if x == '1': 
        nump += pow(2,n-i-1,stp)
        nump %= stp
        if stm > 0:
            numm += pow(2,n-i-1,stm)
            numm %= stm

for i in range(n):
    if s[i] == '0':
        nnow = (nump+pow(2,n-i-1,stp))%stp
    else:
        if stm <= 0:
            print(0)
            continue
        nnow = (numm-pow(2,n-i-1,stm))%stm
    # print(nnow)
    print(ans[nnow]+1)
### BUGGY CODE ###

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

b = set(a)

c = {}

for i in b:
    c[i] = a.count(i)

for k in a:
    ans = 0
    for i in b:
        if i != k:
            ans += c[i]*(c[i]-1)//2
        else:
            ans += (c[i]-1)*(c[i]-2)//2
    print(ans)


### FIXED CODE ###

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

c = {}

for i in a:
    c[i] = c.get(i, 0) + 1

ways = 0
for i in c:
    ways += c[i]*(c[i]-1)//2

for k in a:
    ans = ways-c[k]+1
    print(ans)
### BUGGY CODE ###

from collections import Counter
from math import factorial


def comb(n, r):
    if (n < r):
        return 0
    else:
        return factorial(n) // factorial(r) // factorial(n - r)


N = int(input())
A = list(map(int, input().split()))
l = Counter()
for i in range(N):
    l.update(str(A[i]))

gsum = 0
combD = {}
for key in l.keys():
    tmp = comb(l[key], 2)
    gsum += tmp
    combD[str(key)] = tmp - comb(l[key]-1, 2)

for i in range(N):
    print(gsum - combD[str(A[i])])


### FIXED CODE ###

from collections import Counter


from operator import mul
from functools import reduce


def cmbf(n, r):
    if (n < r):
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N = int(input())
A = list(map(int, input().split()))
c = [0]*(N+1)

for A_i in A:
    c[A_i] += 1

gsum = 0
for i in range(1, N + 1):
    if (c[i] != 0):
        gsum += cmbf(c[i], 2)

for i in A:
    print(gsum-(c[i]-1))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    print(0,flush = True)
    s = S()
    if s == "Vacant":
        return
    x = s
    ok = 0
    ng = n
    while 1:
        mid = (ok + ng) // 2
        print(mid, flush=True)
        s = S()
        if s == "Vacant":
            return
        if mid & 1 == ok & 1:
            if s == x:
                ok = mid
            else:
                ng = mid
        else:
            if s == x:
                ng = mid
            else:
                ok = mid
                x = s

    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    print(0,flush = True)
    s = S()
    if s == "Vacant":
        return
    x = s
    ok = 0
    ng = n
    while 1:
        mid = (ok + ng) // 2
        print(mid, flush=True)
        s = S()
        if s == "Vacant":
            return
        if mid & 1 == ok & 1:
            if s == x:
                ok = mid
            else:
                ng = mid
        else:
            if s == x:
                ng = mid
            else:
                ok = mid
                x = s

    return


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

S = input()
Q = int(input())
Que = [list(input().split()) for _ in range(Q)]
r = 0
for q in Que:
    if q[0] == '1':
        r += 1
    else:
        if (q[1] == '1' and r % 2 == 0) or (q[1] == '2' and r % 2 == 1):
            S = q[2] + S
        else:
            S = S + q[2]
if r % 2 == 1:
    S = S[::-1]       
print(S)

### FIXED CODE ###

from collections import deque
S = input()
SS = deque()
for s in S:
    SS.append(s)
Q = int(input())
Que = [list(input().split()) for _ in range(Q)]
r = 0

for q in Que:
    if q[0] == '1':
        r += 1
    else:
        if (q[1] == '1' and r % 2 == 1) or (q[1] == '2' and r % 2 == 0):
            SS.append(q[2])
        else:
            SS.appendleft(q[2])
if r % 2 == 0:
   while len(SS) > 0:
        s = SS.popleft()
        print(s, end='')    
else:
    while len(SS) > 0:
        s = SS.pop()
        print(s, end='')
print('')