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

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        if start_t - time.time() > 1.9999:
            return -3
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.append((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)




### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)
### BUGGY CODE ###

N = int(input())
cnt = 0
list = []

while cnt < N :
    S = input()
    if S in list :
        cnt += 1
        continue
    else :
        list.append(S)
        cnt += 1

print(len(list))


### FIXED CODE ###

N = int(input())
p = []

for i in range(N):
    S = input()
    p.append(S)

print(len(list(set(p))))
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    s_ba = ba//2+1
    index = bisect.bisect_right(li, s_ba)
    tmp_li = li[:index+1]
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

#a.sort(reverse=True)
#b.sort(reverse=True)
#c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])
### BUGGY CODE ###

def main():
  n,m = list(map(int,input().split()))
  d = [0]*m
  ma = 0
  mi = 0
  for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = ((1<<a)-1) ^ ((1<<b)-1)
    ma = max(ma,a,b)
    mi = min(mi,a,b)
  s = ((1<<ma)-1) | ((1<<mi)-1) 
  for bit in range(1<<n):
    if bit & s:
      spr = [True]*m
      for k in range(m):
        if (d[k] & bit) > 0:
          spr[k] = False
      if sum(spr) == 0:
        print(sum([1 for i in range(n) if bit & 1<<i]))
        exit()

main()


### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

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

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
li = []
ans = 0

B = set(A)

cnt = len(B)

for x in B:
    a = A.count(x)
    li.append(a)

li = sorted(li)

if cnt - K > 0:
    for x in range(cnt - K):
        ans += li[x]
    print(ans)

else :
    print(ans)

### FIXED CODE ###

import sys
import collections

input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
li = []
ans = 0

B = set(A)

cnt = len(B)

#for x in B:
#    a = A.count(x)
#    li.append(a)

li = list(collections.Counter(A).values())
li = sorted(li)

if cnt - K > 0:
    for x in range(cnt - K):
        ans += li[x]
    print(ans)

else :
    print(ans)
### BUGGY CODE ###

N = int(input())
A = [0]
for i in range(N):
    A.append(int(input()))
old = []
bo = 1
ind = 1
while True:
    if A[bo] == 2:
        print(ind)
        exit()
    else:
        ind += 1
        if bo in old:
            print(-1)
            exit()
        old.append(bo)
        bo = A[bo]


### FIXED CODE ###

N = int(input())
A = [0]
for i in range(N):
    A.append(int(input()))
old = []
bo = 1
ind = 1
while ind <= N:
    if A[bo] == 2:
        print(ind)
        exit()
    else:
        ind += 1
        bo = A[bo]
print(-1)
### BUGGY CODE ###

N,Q = input().split()
N,Q = int(N),int(Q)
S = input()
l,r = [],[]
for i in range(Q):
    l_,r_ = input().split()
    l_,r_ = int(l_)-1,int(r_)-1
    l.append(l_)
    r.append(r_)
    
for i in range(Q):
    print(S[l[i]:r[i]+1].count("AC"))

### FIXED CODE ###

N,Q = input().split()
N,Q = int(N),int(Q)
S = input()
l,r = [],[]
for i in range(Q):
    l_,r_ = input().split()
    l_,r_ = int(l_)-1,int(r_)-1
    l.append(l_)
    r.append(r_)
    
A = [0]
sum_ = 0
for i in range(1,N):
    if(S[i-1]=="A" and S[i]=="C"):
        sum_ += 1
    A.append(sum_)

for i in range(Q):
    if(l[i]==0):
        num = r[i]
        print(A[r[i]])
    else:
        sa = A[r[i]]-A[l[i]]
        print(sa)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

d = dict()
ans = 0
ss = [str(input())[2:-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	rh = RollingHash(s, BASE, MOD)
	if n == 1:
		ans += zero[ord(s[0])-97]
	else:
		suff = rh.get(1, n)
		if suff in d:
			ans += d[suff][ord(s[0])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[0])-97] = 1
		for i in range(1, n-1):
			alph[ord(s[i])-97] = 1
			tmp = rh.get(i+1, n)
			if tmp in d:
				for i, a in enumerate(alph):
					d[tmp][i] += a
			else:
				d[tmp] = [0 for _ in range(26)]
				for i, a in enumerate(alph):
					d[tmp][i] += a
		alph[ord(s[n-1])-97] = 1
		for i, a in enumerate(alph):
			zero[i] += a
	#print(ans)
	#print(d, sep="\n")
print(ans)


### FIXED CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

d = dict()
ans = 0
ss = [str(input())[2:-1][::-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	if n == 1:
		ans += zero[ord(s[n-1])-97]
	else:
		hashes = [0 for _ in range(n-1)]
		hashes[0] = ord(s[0])
		for i in range(1, n-1):
			hashes[i] = (hashes[i-1] * BASE + ord(s[i])) % MOD
		if hashes[n-2] in d:
			ans += d[hashes[n-2]][ord(s[n-1])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[n-1])-97] = 1
		for i in range(n-2, 0, -1):
			alph[ord(s[i])-97] = 1
			if hashes[i-1] not in d:
				d[hashes[i-1]] = [0 for _ in range(26)]
			for j, a in enumerate(alph):
				d[hashes[i-1]][j] += a
		alph[ord(s[0])-97] = 1
		for j, a in enumerate(alph):
			zero[j] += a
print(ans)
### BUGGY CODE ###

s = input()
t = input()

dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        elif len(dp[i][j+1]) > len(dp[i+1][j]):
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = dp[i+1][j]
print(dp[len(s)][len(t)])


### FIXED CODE ###

s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ''
i = n
j = m
while i >= 0 and j >= 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

from collections import deque, defaultdict
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v]:
        if nv in visited:
            continue
        if tokens[nv] < 0:
            tokens[nv] = v
        q.append(nv)
if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    [print(t + 1) for t in tokens[1:]]


### FIXED CODE ###

from collections import deque, defaultdict
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)
if len(set(graph.keys())) != N:
    print('No')
    exit()

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v]:
        if nv in visited:
            continue
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

print('Yes')
[print(t + 1) for t in tokens[1:]]
### BUGGY CODE ###

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))

    ans = 0

    for a in range(N):
        for b in range(a+1, N):
            for c in range(b+1, N):
                if L[a] < L[b] + L[c] and L[b] < L[c] + L[a] and L[c] < L[a] + L[b]:
                    ans += 1

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import bisect
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce, reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()

    ans = 0

    for a in range(N):

        for b in range(a+1, N-1):
            ab = L[a] + L[b]
            i = bisect.bisect_left(L, ab) - 1

            ans += i - b

    print(ans)


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

n = int(input())
L =sorted([int(i) for i in input().split()],reverse=True)

#print(L)

count=0
for i in range(0, n-2,1):
  c=L[i]
  x=0
  for j in range(i+1,n-1,1):
    b=L[j]
    for k in range(j+1,n,1):
      a=L[k]
      if a+b>c:
        count +=1
      else:
        if k == j+1:
          x=1
        break
    if x==1:
      break

print(count)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

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

x =0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                x +=1

print(x)

### FIXED CODE ###

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

x =0

for i in range(min(k+1,s+1)):
    x += max(0, min(s-i,k)+1 - max(0,s-i-k) )

print(x)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
n = len(s)
cs = [0] * (n + 1)
for i, x in enumerate(s[::-1]):
    cs[i + 1] = cs[i] + int(x) * 10 ** i % 2019
    cs[i + 1] %= 2019
dp = [0] * 2019
for i, x in enumerate(cs):
    dp[x] += 1
ans = sum(x * (x - 1) // 2 for x in dp)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()[::-1]
n = len(s)
cs = [0] * (n + 1)
ten = 1
for i in range(n):
    cs[i + 1] = int(s[i]) * ten % 2019
    ten = ten * 10 % 2019
for i in range(n):
    cs[i + 1] = (cs[i + 1] + cs[i]) % 2019
cnt = [0] * 2019
for i, x in enumerate(cs):
    cnt[x] += 1
ans = sum(x * (x - 1) // 2 for x in cnt)
print(ans)
### BUGGY CODE ###

from heapq import heappop,heappush
from collections import defaultdict
N,Q = map(int,input().split())
event = []
for _ in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,2,x))

for i in range(Q):
    d = int(input())
    event.append((d,3,i))
event.sort()

memo = defaultdict(int)
nowStop = []
ans = [-1]*Q
while event:
    t,e,x = heappop(event)
    if e == 1:
        heappush(nowStop,x)
        memo[x] += 1
    if e == 2:
        memo[x] -= 1
    if e == 3:
        while nowStop:
            s = nowStop[0]
            if memo[s] == 0:
                heappop(nowStop)
            else:
                ans[x] = s
                break
for a in ans:
    print(a)

### FIXED CODE ###

"""
愚直に一人一人交通止めに対してシミュレートしていは、絶対に間に合わない。

そこで、「この時間に出発したら"まず最初に"この通行止めで引っかかる」というのを前処理でまとめておく。
これは座標圧縮とセグメント木っぽいものを用いることで実現可能。
"""
N,Q = map(int,input().split())
STX = [list(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
times = set(D+[s-x for s,t,x in STX]+[t-x for s,t,x in STX])
compTimes = {t:i for i,t in enumerate(sorted(times))}

class originalSegTree:
    def __init__(self,n):
        self.end_leaves = 2**n.bit_length()
        self.tree = [float("INF")]*(2*self.end_leaves)
    
    def add(self,left,right,x):
        L = left + self.end_leaves
        R = right + self.end_leaves
        while L < R:
            if L&1:
                self.tree[L] = min(self.tree[L],x)
                L += 1
            if R&1:
                R -= 1
                self.tree[R] = min(self.tree[R],x)
            L >>= 1
            R >>= 1
    
    def merge(self):
        for i in range(1,self.end_leaves):
            self.tree[i*2] = min(self.tree[i],self.tree[i*2])
            self.tree[i*2+1] = min(self.tree[i],self.tree[i*2+1])

seg = originalSegTree(len(compTimes))
for s,t,x in STX:
    a = compTimes[s-x]
    b = compTimes[t-x]
    seg.add(a,b,x)

seg.merge()

for d in D:
    c = compTimes[d]
    ans = seg.tree[c+seg.end_leaves]
    if ans == float("INF"):
        ans = -1
    print(ans)
### BUGGY CODE ###

import sys,collections as cl,bisect as bs
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def wa(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

def on():
    N,M,L = m()

    e = [[Max for i in range(N)]for j in range(N)]

    for i in range(M):
        a,b,c = m()
        e[a-1][b-1] = c
        e[b-1][a-1] = c

    for i in range(N):
        e[i][i] = 0

    d = wa(e)


    E = [[Max for i in range(N)]for j in range(N)]

    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                E[i][j] = 1

    for i in range(N):
        E[i][i] = 0

    E = wa(E)
    q = onem()
    for i in range(q):
        s,t = m()
        if E[s-1][t-1] == Max:
            print(-1)
        else:
            print(E[s-1][t-1]-1)

if __name__ == "__main__":
    on()




### FIXED CODE ###

import sys,collections as cl,bisect as bs
Max = 10**18
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def wa(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

def on():
    N,M,L = m()

    e = [[Max for i in range(N)]for j in range(N)]

    for i in range(M):
        a,b,c = m()
        e[a-1][b-1] = c
        e[b-1][a-1] = c

    for i in range(N):
        e[i][i] = 0

    d = wa(e)


    E = [[Max for i in range(N)]for j in range(N)]

    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                E[i][j] = 1

    for i in range(N):
        E[i][i] = 0

    E = wa(E)
    q = onem()
    for i in range(q):
        s,t = m()
        if E[s-1][t-1] == Max:
            print(-1)
        else:
            print(E[s-1][t-1]-1)

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

N = int(input())
A = [int(input()) for i in range(N)]
for i, num in enumerate(A):
    AA = [x for j, x in enumerate(A) if i != j]
    print(max(AA))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A_max = max(A)
AA = A[:]
AA.remove(A_max)
A_max_2nd = max(AA)
for num in A:
    if num != A_max:
        print(A_max)
    else:
        print(A_max_2nd)
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
max_val = 0

for i in range(n):
    p_list[i] = (1 + p_list[i]) * 0.5

for j in range(n-k+1):
    max_val = max(max_val, sum(p_list[j:j+k]))
        
print(max_val)

### FIXED CODE ###

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

for i in range(n):
    p_list[i] = (1 + p_list[i]) / 2

wa = sum(p_list[0:k])
ans = wa

for j in range(n-k):
    wa = wa + p_list[j+k] - p_list[j]
    ans = max(ans, wa)
    
print(ans)
### BUGGY CODE ###

import itertools
n=int(input())
a=list(map(int,input().split()))
ans=0
for a,b in itertools.combinations(a,2):
    ans+=(a*b)%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
cum=[0]
for i in range(n):
    cum.append((cum[i]+a[i])%(10**9+7))
for i in range(n):
    # print(a[i],cum[-1]-cum[i+1])
    ans+=a[i]*(cum[-1]-cum[i+1])%(10**9+7)
    ans%=(10**9+7)
print(ans)
### BUGGY CODE ###

def main():
  t = int(input())
  for _ in range(t):
    a, b, c, d = map(int, input().split())
    if (a < b or d < b):
      print("No")
      continue
    if (c >= b - 1):
      print("Yes")
      continue
  
    a %= b
    if a > c:
      print("No")
      continue
    d %= b
    if d == 0:
      print("Yes")
      continue
    if b % d != 0:
      print("No")
      continue
    for i in range(b // d):
      a = (a + d) % b
      if a > c:
        print("No")
        break
    else:
      print("Yes")
main()

### FIXED CODE ###

def gcd(a, b):
    if b == 0:return a
    return gcd(b, a % b)

t = int(input())
for _ in range(t):
    a, b, c, d = map(int, input().split())
    #exception
    if a < b or d < b:
        print("No")
        continue

    if c >= b:
        print("Yes")
        continue

    g = gcd(d, b)
    print("Yes" if b - g + a % g <= c else "No")
### BUGGY CODE ###

n, x, m = map(int, input().split())
amr = []
for i in range(n):
    if i == 0:
        x %= m
        amr.append(x)
        continue
    x = pow(x, 2, m)

    if x in amr:
        break
    if x == 0:
        break
    amr.append(x)

if x == 0:
    print(sum(amr[:n]))
else:
    idx = amr.index(x)

    loop = sum(amr[idx:])
    l = len(amr[idx:])

    if n >= idx:
        cnt = (n-idx)//l
        print(cnt*loop + sum(amr[:idx]) + sum(amr[idx:idx+n-idx-cnt*l:]))
    else:
        print(sum(amr[:n]))



### FIXED CODE ###

n, x, m = map(int, input().split())
amr = []
for i in range(n):
    if i == 0:
        x %= m
        amr.append(x)
        continue
    x = pow(x, 2, m)

    if x in amr:
        break
    if x == 0:
        break
    amr.append(x)

if x == 0:
    print(sum(amr[:n]))
else:
    idx = amr.index(x)

    loop = sum(amr[idx:])
    l = len(amr[idx:])

    if n >= idx:
        cnt = (n-idx)//l
        print(cnt*loop + sum(amr[:idx]) + sum(amr[idx:idx+n-idx-cnt*l:]))
    else:
        print(sum(amr[:n]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
    if i in a:
        print(a.count(i))
    else:
        print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = [0]*n
for i in a:
    x[i-1] += 1
for j in x:
    print(j)
### BUGGY CODE ###

from math import log2
n, k = map(int, input().split())
To = []
A = list(map(int, input().split()))
A = list(map(lambda x: x - 1, A))
To.append(A)
for i in range(int(log2(k))):
    N = [0 for i in range(n)]
    for j in range(n):
        N[j] = To[i][To[i][j]]
    To.append(N)

v = 0
for i in reversed(range(int(log2(k)) + 1)):
    l = 1 << i
    if l <= k:
        v = To[i][v]
        k -= l
    else:
        pass

print(v + 1)

### FIXED CODE ###

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

C = [0 for i in range(n)]   #Count
P = [-1 for i in range(n)]  #Patern
cp = 1  #current point
t = 0   #周期
while 1:
    #print('C = ', C)
    C[cp - 1] += 1
    if C[cp - 1] < 2:
        P[cp - 1] = t
    else:
        break
    cp = A[cp - 1]
    t += 1

pret = P[cp - 1]    #周期に入るまでの時間
t = t - pret
#print('pret = ', pret)
#print('t = ', t)
#print('P = ', P)

if k <= pret:
    l = k 
else:
    k = k - pret
    l = k % t
    P = list(map(lambda x: x - pret, P))
#print('P = ', P)

ans = 0
for i in range(n):
    if P[i] == l:
        ans = i + 1
        break
    else:
        pass
print(ans)
### BUGGY CODE ###

t = int(input())
s = [int(i) for i in input().split()]
c = 0
for i in range(1, t):
  c += sum(s[:i]) * s[i]
mod = 10**9 + 7
print(c%mod)

### FIXED CODE ###

t = int(input())
s = [int(i) for i in input().split()]
c = 0
n = s[0]
for i in range(1, t):
  c += n * s[i]
  n += s[i]
mod = 10**9 + 7
print(c%mod)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    for _ in range(q):
        tmp = input()
        if len(tmp) == 1:
            s = s[::-1]
        else:
            a, b, c = tmp.split()
            if b == '1':
                s = c + s
            else:
                s = s + c
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

if __name__ == '__main__':
    main()