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

import sys
imput=sys.stdin.readline

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


n,m,l=map(int,input().split())
ABC=[list(map(int, input().split())) for i in range(m)]
q=int(input())
st=[list(map(int, input().split())) for i in range(q)]

graph=WarshallFloyd(n)
graph2=WarshallFloyd(n)
for a,b,c in ABC:
    graph.add(a-1,b-1,c)
hasNegativeCycle, d = graph.WarshallFloyd_search()
#ans = sorted([[i, max(d[i])] for i in range(n)], key=lambda x: x[0])
ans=graph.WarshallFloyd_search()
#print(ans)
L=[[0,0,0] for _ in range(n**2)]
for i in range(n):
    for j in range(n):
        L[i*n+j][0],L[i*n+j][1],L[i*n+j][2]=i+1,j+1,ans[1][i][j]
#print(L)
for a,b,c in L:
    if 0<c<=l:
        graph2.add(a-1,b-1,1)
ans1=graph2.WarshallFloyd_search()
#print(ans1)
for i,j in st:
    if ans1[1][i-1][j-1]-1!=float('inf'):
        print(ans1[1][i-1][j-1]-1)
    else:
        print(-1)

### FIXED CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


n,m,l= map(int,input().split()) #n:頂点数　w:辺の数

d=[[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)

d2=[[float("inf") for i in range(n)] for i in range(n)] 
for i in range(n):
    for j in range(n):
        if d[i-1][j-1]<=l:
            d2[i-1][j-1]=1
            d2[j-1][i-1]=1
warshall_floyd(d2)
q=int(input())
l=[list(map(int, input().split())) for i in range(q)]
for i in range(q):
    if d2[l[i][0]-1][l[i][1]-1]-1!=float('inf'):
        print(d2[l[i][0]-1][l[i][1]-1]-1)
    else:
        print(-1)
### BUGGY CODE ###

X = map(int,input().split())
#X=7
P = {0}
i=1
while True:
    Q = {0}
    for p in P:
        Q.add(p+i)
        Q.add(p-i)
    P = P.union(Q)
    if X in P:
        print(i)
        break
    i = i+1


### FIXED CODE ###

a,b = input().split()
if a == b:
     print('H')
else:
     print('D')
### BUGGY CODE ###

N = int(input())
l = [input() for i in range(N)]
count = 0
for i in range(N):
    l[i] = ''.join(sorted(l[i]))
    for j in range(i):
        if(l[i]==l[j]):
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
l = [input() for i in range(N)]
mydict = {}
times = [1]*N
count = 0
value = 1

for i in range(N):
    l[i] = ''.join(sorted(l[i]))
    if l[i] in mydict.keys():
        count += times[mydict[l[i]]]
        times[mydict[l[i]]] += 1
    else:
        mydict[l[i]] = value
        value += 1
print(count)
### BUGGY CODE ###

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

if n<b:
  qlist = range(n+1)
else:
  qlist = range(b)
  
anslist = list(map(lambda x:a*x//b,qlist))

print(max(anslist))
 


### FIXED CODE ###

a,b,n = map(int,input().split())
 
if n<b:
  maxq = n
else:
  maxq = b-1
  
ans = a*maxq//b
 
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b)
    l[b-1].append(a)

#深さのリストを作る
l_depth=[1]
l_depth_sub=[0]*n
l_depth_sub[0]+=1
for i in range(n):
    for j in range(len(l[i])):
        if l_depth_sub[l[i][j]-1]==0:
            l_depth_sub[l[i][j]-1]+=1
            l_depth.append(l[i][j])               
    if l_depth_sub.count(0)==0:break

#解の出力
print('Yes')
for i in range(1,n):
    #各部屋の通じてる部屋リストを浅い順にソート
    ll=sorted(l[i], key=lambda data:l_depth.index(data))
    print(ll[0])

### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
 
g=nx.Graph() #無向グラフ
g.add_edges_from(s) #リストsを参照して頂点（部屋）の追加
di=nx.predecessor(g,source=1)#1から全点までの最短路におけるその点の前の点を表示
 
print("Yes")
for x in range(2,n+1):
      print(di[x][0])
### BUGGY CODE ###

s = input()

cnt = 0
for i in range(len(s)):
    n = s[i]
    for j in range(i+1, len(s)):
        n += s[j]
        if int(n) % 2019 == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

    vals = []
    for i in set(a_list):
        for X in [i]:
            vals.append(len([a for a in a_list if abs(X - a) <= 1]))
    print(max(vals))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    num_freq = collections.Counter(a_list)

    vals = []
    for X in set(a_list):
        v = 0
        if X in num_freq:
            v += num_freq[X]
        if X - 1 in num_freq:
            v += num_freq[X-1]
        if X + 1 in num_freq:
            v += num_freq[X+1]
        vals.append(v)
    print(max(vals))

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

# -*- coding: utf-8 -*-
N,X,Y = map(int,input().split())
ToltN=N*(N-1)/2
Dist=[[0 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i,N):
        Dist[i][j] = j-i
        MyDist=abs(i-(X-1))+abs(j-(Y-1))+1
        if MyDist<Dist[i][j]:
            Dist[i][j]=MyDist


for j in range(N-1):
    ans=0
    for i in range(N):
        ans+=Dist[i].count(j+1)

    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
N,X,Y = map(int,input().split())
ToltN=N*(N-1)/2
Dist=[[0 for i in range(N)] for i in range(N)]
c=[0]*N
for i in range(N):
    for j in range(i+1,N):
        MyDist=abs(i-(X-1))+abs(j-(Y-1))+1
        if MyDist<j-i:
            Dist[i][j]=MyDist
            c[MyDist-1]+=1
        else:
            Dist[i][j] = j-i
            c[j-i-1]+=1
for i in range(N-1):
    print(c[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 入力
N = int(input())

count = 0

for i in range(N-1):
    for j in range(N-1):
        if((i+1)*(j+1) < N):
            count = count + 1
        else:
            break
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 入力
N = int(input())

count = 0

for i in range(N-1):
    for j in range(N-1):
        if((i+1)*(j+1) < N):
            count = count + 1
        else:
            break
print(count)
### BUGGY CODE ###

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

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Start = {a for a in range(N)}
End = set()
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)
    End.add(y)
Start = Start - End
Q = deque(Start)

DP = [0] * N
ans = 0
while Q:
    now = Q.pop()
    for nex in Edge[now]:
        if DP[nex] < DP[now] + 1:
            DP[nex] = DP[now] + 1
            Q.append(nex)
            ans = max(ans, DP[nex])
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
Edge = [[]for _ in range(N)]
Far = [-1]*N
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    Edge[x].append(y)


def long(x):
    if len(Edge[x]) == 0:
        Far[x] = 0
        return 0
    if Far[x] >= 0:
        return Far[x]
    r = 0
    for i in Edge[x]:
        l = long(i) + 1
        r = max(r, l)
    Far[x] = r
    return r


for i in range(N):
    long(i)
print(max(Far))
### BUGGY CODE ###

def get_prime_number_list(N):
    primes = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    primes = get_prime_number_list(10**5)
    prime_lst = [0] * (10**5+10)
    for prime in primes:
        prime_lst[prime] = 1

    ans = [0]*(10**5+10)

    for i in range(3, 10**5+10, 2):
        if prime_lst[i] and prime_lst[(i+1)//2]:
            ans[i] += 1

    for _ in range(Q):
        l,r=map(int,input().split())
        print(sum(ans[:r+1]) - sum(ans[:l]))

main()


### FIXED CODE ###

from itertools import accumulate

def get_prime_number_list(N):
    # N以下の素数のリストを返す
    primes = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    primes = get_prime_number_list(10**5)
    prime_lst = [0]*(10**5+10)
    tmp = [0]*(10**5+10)
    for prime in primes:
        prime_lst[prime] = 1
    for i in range(3, 10**5+10, 2):
        if prime_lst[i] and prime_lst[(i+1)//2]:
            tmp[i] = 1
    ans = list(accumulate(tmp))
    l_r = []
    for _ in range(Q):
        l_r.append(map(int,input().split()))
    for l,r in l_r:
        print(ans[r] - ans[l-1])

main()
### BUGGY CODE ###

# 解説放送

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

    dp = [[inf] * 2 for _ in range(n + 1)]
    dp[0][0] = 0

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            for a in range(10):
                ni, nj = i + 1, 0
                x = int(c) + j
                b = a - x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

    print(dp[n][0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説放送
# 写経

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

    dp = [[inf] * 2 for _ in range(n + 1)]
    dp[0][0] = 0

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            x = int(c) + j
            if x < 10:
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)  # a=x,b=0
            if x > 0:
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))  # a=0,bに繰り下がり

    print(dp[n][0])


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

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(60):
  c=0
  for j in A:
    if j>>i&1==1:
      c+=1
  ans+=pow(2,i,mod)*c*(N-c)
  ans=ans%mod
print(ans)

### FIXED CODE ###

def main():
  N=int(input())
  A=list(map(int,input().split()))
  mod=10**9+7
  ans=0
  for i in range(60):
    c=0
    for j in A:
      if j>>i&1:
        c+=1
    ans+=pow(2,i,mod)*c*(N-c)
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	import time
	primes = get_sieve_of_eratosthenes(10**5)
	primes = [p for p in primes if primes.count((p+1)//2)]
	# print(primes)
	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(primes, r)-bisect_left(primes, l))

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
from bisect import bisect, bisect_left

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	primes = get_sieve_of_eratosthenes(10**5)

	prime_dict = dict(zip(primes, [1]*len(primes)))
	prime_2017 = []
	append = prime_2017.append
	for k in prime_dict.keys():
		if int((k+1)/2) in prime_dict:
			append(k)
	
	prime_2017.sort()
	# print(prime_2017)

	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(prime_2017, r)-bisect_left(prime_2017, l))

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

class DoublyLinkedList:
    def __init__(self, num):
        self.elements = [None for _ in range(300001)]
        self.elements[0] = [None, num, None]
        self.top = 0
        self.bottom = 0
        self.cnt = 0

    def push_top(self, val):
        self.cnt += 1
        self.elements[self.top][0] = self.cnt
        self.elements[self.cnt] = [None, val, self.top]
        self.top = self.cnt

    def push_bottom(self, val):
        self.cnt += 1
        self.elements[self.bottom][2] = self.cnt
        self.elements[self.cnt] = [self.bottom, val, None]
        self.bottom = self.cnt

    @staticmethod
    def from_str(s):
        ret = DoublyLinkedList(s[0])
        for v in s[1:]:
            ret.push_bottom(v)
        return ret

    def to_str(self):
        cur = self.top
        val = self.elements[self.top][1]
        while self.elements[cur][2] is not None:
            val += self.elements[self.elements[cur][2]][1]
            cur = self.elements[cur][2]
        return val


def main():
    s = input()
    d = DoublyLinkedList.from_str(s)
    q = int(input())
    swapped = 0
    for _ in range(q):
        query = input()
        if len(query) == 1:
            swapped = 1 - swapped
            continue
        _, f, c = query.split()
        if swapped:
            if f == '1':
                d.push_bottom(c)
            else:
                d.push_top(c)
        else:
            if f == '1':
                d.push_top(c)
            else:
                d.push_bottom(c)

    if swapped:
        print(d.to_str()[::-1])
    else:
        print(d.to_str())


if __name__ == '__main__':
    main()



### FIXED CODE ###


def main():
    s = input()
    q = int(input())
    bottom = ''
    top = ''
    swapped = 0
    for _ in range(q):
        query = input()
        if len(query) == 1:
            swapped = 1 - swapped
            continue
        _, f, c = query.split()
        if swapped:
            if f == '1':
                bottom += c
            else:
                top += c
        else:
            if f == '1':
                top += c
            else:
                bottom += c

    if swapped:
        print(bottom[::-1] + s[::-1] + top)
    else:
        print(top[::-1]+s+bottom)


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

r,g,b,n = map(int,input().split(" "))
count = 0
for i in range(n+1):
    for j in range(n+1):
        if (i * r + j * g) <= n:
            if (n - (i * r + j * g)) % b == 0: 
                    count += 1
print(count)

### FIXED CODE ###

r,g,b,n = map(int,input().split(" "))
count = 0
for i in range(0,n+1,r):
    for j in range(0,n+1,g):
        if i + j <= n:
            if (n - (i + j)) % b == 0: 
                    count += 1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python

def gcd(a, b):
    if a < b:
        a, b = b, a

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


def main():
    N, M = [int(a) for a in input().split()]

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(L):
        if i % cc != 0:
            continue
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def gcd(a, b):
    if a < b:
        a, b = b, a

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


def main():
    N, M = [int(a) for a in input().split()]

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(0, L, cc):
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


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

def detect_collor(num, blue_ball, red_ball):
    string = ''
    while len(string) < num:
        for i in range(blue_ball):
            string += 'b'
        for i in range(red_ball):
            string += 'r'
    return string[:num]

nums, blue_balls, red_balls = map(int, input().split())

ans = detect_collor(nums, blue_balls, red_balls)
print(ans.count('b'))

### FIXED CODE ###

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

blue = N // (A + B) * A
rem = N % (A + B)
blue = blue + min(rem, A)

print(blue)
### BUGGY CODE ###

from collections import defaultdict

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    jobs[a].append(b)

result = 0
pool = []
for i in range(1, m+1):
    pool += jobs[i]
    pool = sorted(pool)
    if 0 < len(pool):
        result += pool.pop()

print(result)

### FIXED CODE ###

from heapq import *
from collections import defaultdict

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    jobs[a].append(-b)

result = 0
pool = []
for i in range(1, m+1):
    for j in jobs[i]:
        heappush(pool, j)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)
### BUGGY CODE ###

def numsum(a) :
    ans = 0
    for i in range(len(a)) :
        ans += (i + 1) * a[i]
    return ans

n = int(input())
l_a = list(map(int, input().split()))
many = []
for i in range(1, 100001) :
    many.append(l_a.count(i))
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    many[c - 1] += many[b - 1]
    many[b - 1] = 0
    ans.append(numsum(many))

for value in ans :
    print(value)


### FIXED CODE ###

import collections

n = int(input())
l_a = list(map(int, input().split()))
col = collections.Counter(l_a)
bef = sum(l_a)
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    bef += (c - b)*col[b]
    ans.append(bef)
    col[c] += col[b]
    col[b] = 0

for value in ans :
    print(value)
### BUGGY CODE ###

N=[int(e) for e in input().split()]
p=[(int(e)+1)/2.0 for e in input().split()]
p2=[0.]*(N[0]-N[1]+1)
for i in range(N[0]-N[1]+1):
    p2[i]=sum(p[i:(i+N[1])])

print(max(p2))

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N-1):
    p[i+1]=p[i+1]+p[i]
max=p[K-1]
if N>K:
    for i in range(1,N-K+1):
        tmp=p[i+K-1]-p[i-1]
        if max < tmp:
            max=tmp
print((max+K)/2.)
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    cnt = 0
    for i in range(N):
        res = 0
        for j in range(i, N):
            res += A[j]
            if res == 0:
                cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa
from operator import mul
from functools import reduce


def cmb(n, r):
    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


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


def main():
    _ = int(input())
    A = list(map(int, input().split()))

    S = [0]
    for a in A:
        S.append(S[-1] + a)

    cnt = {}
    for s in S:
        if s not in cnt:
            cnt[s] = 1
        else:
            cnt[s] += 1

    ans = 0
    for v in cnt.values():
        if v >= 2:
            ans += cmb(v, 2)

    print(ans)


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

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = readline().decode().rstrip()
q = int(readline())

for _ in range(q):
    que = readline().decode().split()
    if len(que) == 1:
        S = S[::-1]
    else:
        if que[1] == '1':
            S = que[2] + S
        else:
            S += que[2]

print(S)


### FIXED CODE ###

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = readline().decode().rstrip()
q = int(readline())

head = ""
tail = ""
flip = 0
for _ in range(q):
    que = readline().decode().split()
    if len(que) == 1:
        flip += 1

    else:
        if que[1] == '1':
            if flip % 2 == 0:

                head = ''.join([que[2], head])
            else:
                tail = ''.join([tail, que[2]])

        else:
            if flip % 2 == 0:

                tail = ''.join([tail, que[2]])
            else:
                head = ''.join([que[2], head])

if flip % 2 == 0:
    print(''.join([head, S, tail]))
else:
    print(''.join([tail[::-1], S[::-1], head[::-1]]))
### BUGGY CODE ###

N = int(input())

l = []
l1 = []
for i in range(1, N):
    l.append(i)
    l1.append(i + 1)
l.append(N)
l1.append(1)
m = 0
for i in range(len(l)):
    m += l[i] % l1[i]
print(m)

### FIXED CODE ###

N = int(input())
ans = ((N - 1) * N ) // 2
print(ans)
### BUGGY CODE ###

from fractions import gcd

import sys
input = sys.stdin.readline

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

B = []
C = []

for a in A:
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    B.append(a)
    C.append(c)

ok = True
for i in range(N-1):
    if C[i] != C[i+1]:
        ok = False
if not ok:
    print(0)
else:
    g = 1
    for b in B:
        l = gcd(g, b)
        g = g*b//l
    p = g*2**(c-1)
    ans = (M+p)//(2*p)
    print(ans)

### FIXED CODE ###

from fractions import gcd

import sys
input = sys.stdin.readline


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

    B = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        B.sort()
        g = 1
        for b in B:
            l = gcd(b, g)
            g = g*b//l
            if g > M:
                ok = False
                break
        if not ok:
            print(0)
        else:
            p = g*2**(c-1)
            ans = (M+p)//(2*p)
            print(ans)


if __name__ == "__main__":
    main()