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

import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit = Bit(2*N+1)
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])


### FIXED CODE ###

import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
# print(sorted_in)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} half {} value {}".format(lft, rgt, half, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    bit.add(N, 1)
    for i, x in enumerate(inarr):
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        # print("summed: {}, bit: {}".format(summed, bit.sum(N + summed)))
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print("num {} cnt {} judge {}".format(sorted_in[half], res, math.ceil(comb/2)))
    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
suml = []
#最大のリストを選定
before_pi = 0
for i in range(0,n-k+1):
    suml.append(sum(p[i:i+k]))

#計算
print((max(suml)+k)/2.0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#最大のリストを選定
before_pi = p[0]
before_sum = sum(p[0:k])+ 0.0
suml = [sum(p[0:k])]
for i in range(1,n-k+1):
    before_sum = before_sum - before_pi+p[i+k-1]
    suml.append(before_sum)
    before_pi = p[i]

#計算
print((max(suml)+k)/2.0)
### BUGGY CODE ###

from collections import deque
def main():
    n,m=map(int,input().split())
    root=[[0 for i in range(n)] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    min=[-1 for i in range(n)]
    min[0]=2
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=deque()
    check[start]=True
    for i in range(len(root[0])):
        if root[0][i]==1:
            toVis.append(i)
            dict[i]=start
        #   print(i,":",start)
            check[i]=True
    while len(toVis)>0:
        now=toVis.popleft()
        #print(now)
        check[now]=True
        for i in range(n):
            if root[now][i]==1 and check[i]==False:
                toVis.append(i)
                dict[i]=now
            # print(i,":",now)
                check[i]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


if __name__=="__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    n,m=map(int,input().split())
    root=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    dict={}
    for i in range(n):
        dict[i]=-1

    start=0
    check=[False]*n
    toVis=deque()
    check[start]=True
    for v in root[start]:
        toVis.append(v)
        dict[v]=start
    #   print(i,":",start)
        check[v]=True
    while len(toVis)>0:
        now=toVis.popleft()
        #print(now)
        check[now]=True
        for v in root[now]:
            if check[v]==False:
                toVis.append(v)
                dict[v]=now
            # print(i,":",now)
                check[v]=True
    #print(dict)  
    for i in range(1,n):
        if dict[i]==-1:
            print("No")
            return 0
    print("Yes")
    for i in range(1,n):
        print(dict[i]+1)         


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

import functools
n=int(input())
a=list(map(int,input().split()))
def gcd(j,k):
  if j<k:j,k=k,j
  if j%k==0:return k
  return gcd(k,j%k)
A=functools.reduce(gcd,a)
for i in range(n):
    c=a[i]
    del a[i]
    B=functools.reduce(gcd,a)
    if A<B:
        A=B
    else:
        A=A
    a.insert(i,c)
print(A)


### FIXED CODE ###

import fractions 
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
sna=a[n-1]
Ans=[ans]*n
Sna=[sna]*n
for j in range(1,n):
  ans=fractions.gcd(ans,a[j])
  Ans[j]=ans
  sna=fractions.gcd(sna,a[n-j-1])
  Sna[j]=sna
m=Sna[n-2]
for k in range(n-2):
  m=max(m,fractions.gcd(Ans[k],Sna[n-3-k]))
m=max(m,Ans[n-2])
print(m)
### BUGGY CODE ###

from itertools import count
n = input()
l = []
l += [str(n) + ":"]
while 1:
    if n == 1:break
    for i in count(2):
        if n % i == 0:
            n /= i
            l += [i]
            break
print " ".join(map(str,l))

### FIXED CODE ###

n = input()
l = []
l += [str(n)+":"]
i = 2
while i * i <= n:
    while n % i == 0:
        l += [i]
        n /= i
    i += 1
if n > 1: l += [n]
print " ".join(map(str,l))
### BUGGY CODE ###

N = int(input())
move_num_list = [0]*5
for i in range(5):
    move_num_list[i] = int(input())

num_list = [0]*6
num_list[0] = N
time = 0
while sum(num_list) != 0:
    time += 1
    for i in range(4, -1, -1):
        num = move_num_list[i]
        if i == 4:
            if num_list[i] > 0:
                if num_list[i] >= num:
                    num_list[i] -= num
                else:
                    num_list[i] = 0
        if num_list[i] > 0:
            if num_list[i] >= num:
                num_list[i] -= num
                num_list[i+1] += num
            else:
                num_list[i+1] += num_list[i]
                num_list[i] = 0

print(time)

### FIXED CODE ###

N = int(input())
move_num_list = [0]*5
for i in range(5):
    move_num_list[i] = int(input())

min_ = min(move_num_list)
print(-(-N//min_)+4)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
LR = []
num = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    l,r = list(map(int,input().split()))
    l -= 1
    r -= 1
    num[l][r] += 1
    LR.append([l,r])
LR.sort()
pq = []
for i in range(Q):
    p,q=list(map(int,input().split()))
    p -= 1
    q -= 1
    ans = 0
    for i in range(N-1,p-1,-1):
        ans += sum(num[i][:q+1])
    print(ans)
    


### FIXED CODE ###

N,M,Q = map(int,input().split())
num = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    l,r = list(map(int,input().split()))
    l -= 1
    r -= 1
    num[l][r] += 1
for i in range(N):
    for j in range(N-1):
        num[i][j+1] += num[i][j]
for i in range(N-1,0,-1):
    for j in range(N):
        num[i-1][j] += num[i][j]
for i in range(Q):
    p,q = map(int,input().split())
    print(num[p-1][q-1])
### BUGGY CODE ###

import collections
n = int(input())
A = list(map(int, input().split()))

def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return collections.Counter(r)

fa = collections.Counter()
p = []
for a in A:
    tt = prime_factorize(a)
    fa = fa | tt
    p.append(tt)

ans = 0
mod = 10**9+7
for i in range(n):
    t = 1
    fb = fa - p[i]
    for k, v in fb.items():
        t *= pow(k, v, mod)
    ans += t % mod
    ans %= mod
print(ans % mod)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
cm = 1
for i in range(n):
    cm = cm*a[i]//gcd(cm, a[i])
ai = sum(pow(x, mod-2, mod) for x in a)
print(int(ai*cm%mod))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = {i:[] for i in range(n)}
count = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)   
    block[min(a-1,b-1)].append(max(a-1,b-1))
for i in range(k):
    c,d = map(int,input().split())
    block[min(c-1,d-1)].append(max(c-1,d-1))
for j in uf.all_group_members():
    for k in uf.all_group_members()[j]:
        for l in uf.all_group_members()[j] :
            if k < l and not max(k,l) in block[min(k,l)]:
                count[k] += 1
                count[l] += 1
print(" ".join(map(str,count)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
        self.count = [1]*n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.count[x] +=  self.count[y]
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1) 
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)
ans = []
for i in range(n):
    ans.append(uf.count[uf.find(i)]-len(block[i])-1)
print(" ".join(map(str,ans)))
### BUGGY CODE ###

#python3
from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
    print(dp[5])
main()


### FIXED CODE ###

from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
        mul %= 13
    print(dp[5])
main()
### BUGGY CODE ###

N=int(input())
S=list(input())
count = N
for i in range(N):
  x=[i for i in S[:i] if i == 'W']
  y=[i for i in S[(i+1):] if i == 'E']
  if count > (len(x)+len(y)):
    count = (len(x)+len(y))

print(count)

### FIXED CODE ###

N=int(input())
S=list(input())
C=[0]*N
C[0]=S[1:].count('E')
for i in range(1,N):
  C[i]=C[i-1]+ (S[i-1]=='W')-(S[i]=='E') 
print(min(C))
### BUGGY CODE ###

from collections import defaultdict

n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]


edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x

queue = [1]
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(queue) > 0:
    node = queue.pop(0)
    next_nodes = filter(lambda m: not visited[m - 1], edge_dict[node])
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        queue.append(m)


for i in range(1, n + 1):
    end = '\n' if i == n else ' '
    print(total_value_dict[i], end=end)


### FIXED CODE ###

from collections import defaultdict
from collections import deque
import time
import sys

input = sys.stdin.readline

# start = time.time()
n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]

# elapsed = time.time() - start
# print("elapsed_time:{0}".format(elapsed) + "[sec]")

edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x


qu = deque([1])
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(qu) > 0:
    node = qu.popleft()
    next_nodes = [m for m in edge_dict[node] if not visited[m - 1]]
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        qu.append(m)

print(' '.join([str(total_value_dict[i]) for i in range(1, n + 1)]))
### BUGGY CODE ###

s = input()
t = input()
len_s = len(s)
len_t = len(t)

# dp[i][j] = sのi-1文字目,tのj-1文字目まででの最長共通部分列の長さ
dp = [[-1]*(len_t+1) for i in range(len_s+1)]
# 遷移記録用（0,1が両方-1ならその文字を追加する）
prev = [[[0]*2 for j in range((len_t+1))] for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        # どちらかが空文字列の場合
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        # i-1文字目とj-1文字目が一致する場合
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prev[i][j][0] = -1
            prev[i][j][1] = -1
        # 一致しない場合
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prev[i][j][0] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prev[i][j][1] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1
# 遷移をたどっていく
for i in range(10**18) :
    if prev[si][ti][0] == -1 and prev[si][ti][1] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prev[st][tt][0] ; ti += prev[st][tt][1]
    if si == st and ti == tt :
        break

print(*ans, sep='')

### FIXED CODE ###

s = input()
t = input()
len_s = len(s)
len_t = len(t)

# dp[i][j] = sのi-1文字目,tのj-1文字目まででの最長共通部分列の長さ
dp = [[0]*(len_t+1) for i in range(len_s+1)]
# 遷移記録用（0,1が両方-1ならその文字を追加する）
prevs = [[0]*(len_t+1) for i in range(len_s+1)]
prevt = [[0]*(len_t+1) for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        # どちらかが空文字列の場合
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        # i-1文字目とj-1文字目が一致する場合
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prevs[i][j] = -1
            prevt[i][j] = -1
        # 一致しない場合
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prevs[i][j] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prevt[i][j] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1
# 遷移をたどっていく
for i in range(10**18) :
    if prevs[si][ti] == -1 and prevt[si][ti] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prevs[st][tt] ; ti += prevt[st][tt]
    if si == st and ti == tt :
        break

print(*ans, sep='')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = []
for i in range(a - b + 1):
	h = 0
	for j in range(b):
		h += c[i + j]
	d.append(h)
e = 0
g = d.index(max(d))
for i in range(b):
	f = c[i + g]
	d = 0
	for j in range(f):
		d += (j + 1)
	e += d / f
print(e)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)
### BUGGY CODE ###

N= int(input())
A= list(map(int,input().split()))
 
S= 1
for n in range(N):
  if A[n] == 0:
    S=0
    break
  elif S > 10**18:
    S = -1
  else:
    S *= A[n]
    if S > 10**18:
      S = -1
print(S)

### FIXED CODE ###

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

A = sorted(A)

if A[0] == 0:
  print(0)
else:
  S = 1
  for n in range(N):
    S *= A[N-1-n]
    if S > 10**18:
      S = -1
      break
  print(S)
### BUGGY CODE ###

n, x, m = map(int, input().split())
a = x
s = 0
h = []
h.append(a)
i = 0
fl = 0
while i < n:
    s += a
    a = (a*a) % m
    if a == 0:
      break
    i += 1
    if fl == 0 and a in h:
      fl = 1
      po = h.index(a)
      ss = 0
      for j in range(po):
        ss += h[j]
      s2 = s - ss
      f = (n - po) // (i - po)
      s2 *= f
      s = s2 + ss
      i2 = i - po
      i2 *= f
      i = i2 + po
    else:
      h.append(a)
print(s)

### FIXED CODE ###

n, x, m = map(int, input().split())
a = x
s = 0
h = []
h.append(a)
i = 0
fl = 0
while i < n:
    s += a
    a = (a*a) % m
    if a == 0:
      break
    i += 1
    if fl == 0 and a in h:
      fl = 1
      po = h.index(a)
      ss = 0
      for j in range(po):
        ss += h[j]
      s2 = s - ss
      f = (n - po) // (i - po)
      s2 *= f
      s = s2 + ss
      i2 = i - po
      i2 *= f
      i = i2 + po
    else:
      h.append(a)
print(s)
### BUGGY CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)

### FIXED CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = list(input())
Q = int(input())

is_reversed = False
for _ in range(Q):
    token = input().split(' ')
    if len(token) == 1:
        is_reversed = ~is_reversed

    else:
        _, f, c = token
        f = int(f)
        if (f == 1 and is_reversed) or (f == 2 and not is_reversed):
            S.append(c)

        else:
        # elif (f == 1 and not is_reversed) or (f == 2 and is_reversed):
            S.insert(0, c)

if is_reversed:
    S.reverse()
    print(''.join(S))

else:
    print(''.join(S))



### FIXED CODE ###

# -*- coding: utf-8 -*-
S = list(input())
Q = int(input())

lim = 10**5 *2
buf = [None for _ in range(lim)] + S + [None for _ in range(lim)]
forward_i, back_i = lim-1, lim + len(S) + 1
is_reversed = False
for _ in range(Q):
    token = input().split(' ')
    if len(token) == 1:
        is_reversed = ~is_reversed

    else:
        _, f, c = token
        f = int(f)
        if (f == 1 and is_reversed) or (f == 2 and not is_reversed):
            buf[back_i] = c
            back_i += 1
            # S.append(c)

        else:
        # elif (f == 1 and not is_reversed) or (f == 2 and is_reversed):
            buf[forward_i] = c
            forward_i -= 1
            # S.insert(0, c)

S = ''.join([b for b in buf if b is not None])
if is_reversed:
    print(''.join(reversed(list(S))))
    # S.reverse()
    # print(''.join(S))

else:
    print(S)
    # print(''.join(S))
### BUGGY CODE ###

#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
key=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    for i in n-set(y):
        n.remove(i)
        for j in range(M):
            if i==x[j]:
                if z[y[j]]<=z[x[j]]:
                    z[y[j]]=z[x[j]]+1
                x[j],y[j]=0,0
print(max(z))

### FIXED CODE ###

from collections import defaultdict, deque

N, M = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(M)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))