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

import sys,math,collections,itertools
input = sys.stdin.readline

H,W = list(map(int,input().split()))
s = [input().rstrip() for _ in range(H)]
maperW = [[0]*W for _ in range(H)]
maperH = [[0]*W for _ in range(H)]


#--W方向を調べる--#
for ih in range(H):
    for iw in range(W):
        if s[ih][iw]=='#':
            maperW[ih][iw]=0
        elif s[ih][iw]=='.' and iw == 0:
            maperW[ih][iw]=1
        else:
            maperW[ih][iw]=1+maperW[ih][iw-1]
    for iw in range(W-2,-1,-1):
        if maperW[ih][iw+1] == 0 or maperW[ih][iw]==0:
            continue
        else:
            maperW[ih][iw] = maperW[ih][iw+1]
#--H方向を調べる--#
for iw in range(W):
    for ih in range(H):
        if s[ih][iw]=='#':
            maperH[ih][iw]=0
        elif s[ih][iw]=='.' and ih == 0:
            maperH[ih][iw]=1
        else:
            maperH[ih][iw]=1+maperH[ih-1][iw]
    for ih in range(H-2,-1,-1):
        if maperH[ih+1][iw] == 0 or maperH[ih][iw]==0:
            continue
        else:
            maperH[ih][iw] = maperH[ih+1][iw]
ans = 0
for iw in range(W):
    for ih in range(H):
        ans = max(ans,maperW[ih][iw]+maperH[ih][iw]-1)
print(ans)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W = list(map(int,input().split()))
s = [input().rstrip() for _ in range(H)]
maperW = [[0]*W for _ in range(H)]
maperH = [[0]*W for _ in range(H)]


#--W方向を調べる--#
for ih in range(H):
    for iw in range(W):
        if s[ih][iw]=='#':
            maperW[ih][iw]=0
        elif s[ih][iw]=='.' and iw == 0:
            maperW[ih][iw]=1
        else:
            maperW[ih][iw]=1+maperW[ih][iw-1]
    for iw in range(W-2,-1,-1):
        if maperW[ih][iw+1] == 0 or maperW[ih][iw]==0:
            continue
        else:
            maperW[ih][iw] = maperW[ih][iw+1]
#--H方向を調べる--#
for iw in range(W):
    for ih in range(H):
        if s[ih][iw]=='#':
            maperH[ih][iw]=0
        elif s[ih][iw]=='.' and ih == 0:
            maperH[ih][iw]=1
        else:
            maperH[ih][iw]=1+maperH[ih-1][iw]
    for ih in range(H-2,-1,-1):
        if maperH[ih+1][iw] == 0 or maperH[ih][iw]==0:
            continue
        else:
            maperH[ih][iw] = maperH[ih+1][iw]
ans = 0
for iw in range(W):
    for ih in range(H):
        ans = max(ans,maperW[ih][iw]+maperH[ih][iw]-1)
print(ans)
### BUGGY CODE ###

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


n, k, l = map(int, input().split())
ufd, ufr = UnionFind3(n), UnionFind3(n)
for _ in range(k):
    p, q = map(int, input().split())
    ufd.union(p - 1, q - 1)
for _ in range(l):
    r, s = map(int, input().split())
    ufr.union(r - 1, s - 1)
result = [1] * n
for i in range(n):
    for j in range(i + 1, n):
        if ufd.find(i) == ufd.find(j) and ufr.find(i) == ufr.find(j):
            result[i] += 1
            result[j] += 1
print(*result)


### FIXED CODE ###

from collections import defaultdict


class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2


n, k, l = map(int, input().split())
ufd, ufr = UnionFind3(n), UnionFind3(n)
for _ in range(k):
    p, q = map(int, input().split())
    ufd.union(p - 1, q - 1)
for _ in range(l):
    r, s = map(int, input().split())
    ufr.union(r - 1, s - 1)
d = defaultdict(int)
for i in range(n):
    d[ufd.root(i), ufr.root(i)] += 1
print(*(d[ufd.root(i), ufr.root(i)] for i in range(n)))
### BUGGY CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	dansu=int((x+y)/3)
	r=y-dansu
	if r>dansu-r:
		r=dansu-r
	mod=1000000007
	d=1
	rr=1
	nr=1
	for i in range(1,dansu+1):
		d=d*(i%mod)
	for i in range(1,r+1):
		rr=rr*(i%mod)
	for i in range(1,dansu-r+1):
		nr=nr*(i%mod)
	rr2=rr*rr
	nr2=nr*nr
	rrinv=1
	nrinv=1
	modd=mod
	mod2=[]
	while modd>0:
		mod2.append(modd%2)
		modd=modd//2
	for i in range(len(mod2)-1):
		if mod2[i]==1:
			rrinv=rrinv*(rr2**(len(mod2)-i-1))
			nrinv=nrinv*(nr2**(len(mod2)-i-1))
	rrinv*=rr
	nrinv*=nr
	kotae=int((d%mod)*(rrinv%mod)*(nrinv%mod))
	kotae=int(kotae%(10**9+7))
	
	print(kotae)

### FIXED CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    l1 = [0]*61
    mod = 10**9+7
    for cnt in range(61):
        l1[cnt] = sum([i % 2 for i in a])
        a = [i//2 for i in a]
    l0 = [n-i for i in l1]
    ans = 0
    for i in range(len(l1)):
        ans = (ans+l0[i]*l1[i]*pow(2, i, mod)) % mod
    print(ans)


main()


### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    l1=[0]*61
    for i in a:
        j=list(reversed(bin(i)[2:]))
        for k in range(len(j)):
            if j[k]=="1":
                l1[k]+=1
    l0=[n-i for i in l1]
    ans=0
    mod=10**9+7
    for i in range(len(l1)):
        ans=(ans+l0[i]*l1[i]*pow(2,i,mod))%mod
    print(ans)
main()
### BUGGY CODE ###

#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N=int(input())
A = [list(map(int, input().split())) for _ in range(N)]

inf=float('inf')
dp=[[0]*3 for j in range(N+1)]

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0:
        return 0
    if dp[n][m]>0:
        return dp[n][m]

    for i in range(3):
            if (i == m):
                continue
            dp[n][m]=chmax(dp[n][m], rec(n-1,i) + A[n-1][m])
    
    return dp[n][m]

re=max(rec(N,0),rec(N,1),rec(N,2))
print(re)

### FIXED CODE ###

#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N=int(input())
A = [list(map(int, input().split())) for _ in range(N)]

inf=float('inf')
dp=[[0]*3 for j in range(N+1)]

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0:
        return 0
    if dp[n][m]>0:
        return dp[n][m]

    for i in range(3):
            if (i == m):
                continue
            dp[n][m]=chmax(dp[n][m], rec(n-1,i) + A[n-1][m])
    
    return dp[n][m]

re=max(rec(N,0),rec(N,1),rec(N,2))
print(re)
### BUGGY CODE ###

N = int(input())

a = [int(input()) for i in range(N)]

b = a[0]
li = [0]
c = 1

while b != 2:
    li += [b-1]
    b = a[b-1]
    if b-1 in li:
        print(-1)
        break
    else:
        c += 1
else:
    print(c)


### FIXED CODE ###

N = int(input())

a = [int(input()) for i in range(N)]

b = a[0]
li = [0]
c = 1

while b != 2:
    li += [b-1]
    b = a[b-1]
    c += 1
    if c > N:
        print(-1)
        break
else:
    print(c)
### BUGGY CODE ###

a, b, n = map(int, input().split())
current = 0
for x in range(1,n+1):
  current = max(current, (a*x)//b - a*(x//b))
print(current)
  

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1,n)
print((a*x)//b - a*(x//b))
### BUGGY CODE ###


x = input().split()
n = int(x[0]) # n == 比較文字列の長さ
q = int(x[1]) # q == 検討する回数
s = input()
maxx = 0
count = 0
data = ["A","C","T","G"]

def sc():
    global s
    global n
    global q
    maxx = 0
    count = 0
    com = [int(s)-1 for s in input().split()]
    for i in range(com[0], com[1] + 1): # i == 先頭の文字
        for j in range(i,com[1] ): # j == 動かす文字
            if (s[j] == "A") and(s[j+1] == "C"):
                count += 1
                
            else:
                break
        

    print(count)

for i in range(q):
    sc()


### FIXED CODE ###


x = input().split()
n = int(x[0]) # n == 比較文字列の長さ
q = int(x[1]) # q == 検討する回数
s = input()

        
t = [0] * n
if s[0] == "A":
    t[0] = 1
    
for i in range(0,n-1):
    if s[i:i+2] == "AC":
        
        if (i == 0) :
            t[i] =  + 1
        else:
            t[i] = t[i-1] + 1
    else :
        if i == 0:
            t[i] = 0
        else:
            t[i] = t[i-1]



def sc():
    global t
    global s
    global n
    global q
    global idbox
    maxx = 0
    count = 0
    com = [int(s)-1 for s in input().split()]
    
    
    print(t[com[1]-1] - t[com[0]-1])
        
    

    

for i in range(q):
    
    sc()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a1 = int(input())
a = [a1]
for _ in range(n-1):
  ai = int(input())
  if ai <= a[-1]:
    a.append(ai)
  elif ai > a[0]:
    a = [ai]+a[1:]
  else:
    h = 0
    l = len(a)-1
    while l-h>1:
      m = (l+h)//2
      if ai > a[m]:
        l = m
      else:
        h = m
    a = a[:l]+[ai]+a[l+1:]
print(len(a))   

### FIXED CODE ###

def sub():
  import sys
  input = sys.stdin.readline
  n = int(input())
  a1 = int(input())
  a = [a1]
  ap = a.append
  for _ in range(n-1):
    ai = int(input())
    if ai <= a[-1]:
      ap(ai)
    elif ai > a[0]:
      a[0] = ai
    else:
      h = 0
      l = len(a)-1
      while l-h>1:
        m = (l+h)//2
        if ai > a[m]:
          l = m
        else:
          h = m
      a[l] = ai
  print(len(a))   
sub()
### BUGGY CODE ###

def dfs_rec(start,prev):
    ans[start] = cnt[start]
    if start!=0:
        ans[start] +=ans[prev]
    for node in tree[start]:
        if node != prev:
            dfs_rec(node,start)
    return
import sys
sys.setrecursionlimit(10**6)


n,q = map(int,input().split())
tree = [[] for i in range(n)]
cnt = [0] *n
ans = [0] *n

for i in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for i in range(q):
    p,x = map(int,input().split())
    cnt[p-1]+=x
dfs_rec(0,0)
print(*ans)


### FIXED CODE ###

def main():
    def dfs_rec(start,prev):
        ans[start] = cnt[start]
        if start!=0:
            ans[start] +=ans[prev]
        for node in tree[start]:
            if node != prev:
                dfs_rec(node,start)
        return
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline

    n,q = map(int,input().split())
    tree = [[] for i in range(n)]
    cnt = [0] *n
    ans = [0] *n

    for i in range(n-1):
        a,b = map(int,input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    for i in range(q):
        p,x = map(int,input().split())
        cnt[p-1]+=x
    dfs_rec(0,0)
    print(*ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import collections

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

removes = {}

c = collections.Counter(A)
c2 = {}
for key in c:
    if c[key] > 1:
        c2[key] = c[key]

def comb(n):
    return (n * (n - 1)) // 2

# print(c2)
for k in range(N):
    i = A[k]
    if i not in removes:
        i_sum = 0
        for key in c2:
            if i == key:
                i_sum += comb(c2[key] - 1)
            else:
                i_sum += comb(c2[key])
        removes[i] = i_sum
    print(removes[i])


### FIXED CODE ###

import collections

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

# k番目の数字の総数がkey、そのときの答えがvalue
removes = {}

c = collections.Counter(A)
c2 = {}
for key in c:
    if c[key] > 1:
        c2[key] = c[key]

def comb(n):
    return (n * (n - 1)) // 2

# print(c2)
for k in range(N):
    # k番目の数字
    i = A[k]
    # k番目の数字の総数
    count = c[i]
    if count not in removes:
        answer = 0
        for key in c2:
            if i == key:
                answer += comb(c2[key] - 1)
            else:
                answer += comb(c2[key])
        removes[count] = answer
    print(removes[count])
### BUGGY CODE ###

n,k=[int(x) for x in input().split()]
p=[int(x)-1 for x in input().split()]
a=[0]
i=0
while p[i]!=0:
  a.append(p[i])
  i=p[i]
print(a[k%len(a)]+1)

### FIXED CODE ###

n,k=[int(x) for x in input().split()]
p=[(int(x)-1) for x in input().split()]
alp=[0 for _ in range(n)]
a=[0]
i=0
alp[0]=1
while alp[p[i]]==0:
  a.append(p[i])
  alp[p[i]]=1
  i=p[i]
l=a.index(p[i])
if k<=l: print(1+a[k])
else: print(1+a[l+(k-l)%(len(a)-l)])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    p = [i // 100, (i // 10) % 10 , i % 10]
    idx = 0
    for j in range(n):
        if int(s[j]) == p[idx]:
            idx += 1
        if idx == 3:
            break
    if idx == 3:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
a = [set(), set(), set()]
for i in range(n):
    for j in a[1]:
        a[2].add(j + s[i])
    for j in a[0]:
        a[1].add(j + s[i])
    a[0].add(s[i])
print(len(a[2]))
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        parent[i] = -1
    
que = deque()
que.append([root, path[root]])
while que:
    u, V = que.pop()
    for child in V:
        parent[child] = u
        que.append([child, path[child]])

for i in range(N):
    print(parent[i]+1)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        parent[i] = [-1]
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    if len(parent[v]) > 1:
        parent[v].remove(root) 
    else: que.append([root, v])
while que:
    u, V = que.popleft()
    for v in path[V]:
        if len(parent[v]) > 1:
            parent[v].remove(V)
        else:
            que.append([V, v])
for i in range(N):
    print(parent[i][0]+1)
### BUGGY CODE ###

n,p=map(int,input().split())
a=[]
for i in range(2,int(p//2)):
    b=0
    if p==1:
        break
    while p%i==0:
        p//=i
        b+=1
    a.append([i,b])
c=1
for j in a:
    c*=j[0]**(j[1]//n)
print(c)

### FIXED CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
    quit()
a=[i for i in range(int(p**(1/n))+1)]
a[1]=0
b=int(p**0.5)
for j in a:
    if j>b:
        break
    elif j==0:
        continue
    for k in range(2*j,len(a),j):
        a[k]=0
c=[l for l in a if l!=0]
for m in range(len(c)):
    d=0
    while p%c[m]==0:
        p//=c[m]
        d+=1
    c[m]=[c[m],d]
e=1
for v in c:
    e*=v[0]**(v[1]//n)
print(e)
### BUGGY CODE ###

N = int(input())
A = [0]+[int(x) for x in input().split()]
dp = [0]*(N+1)
res = 0
resstr = ''
for i in range(N):
    # 今見てるところ
    k = N-i
    if k < N//2:
        dp[k] = A[k]-sum([x for i,x in enumerate(dp[k+1:]) if i%k==0])%2
    else:
        dp[k] = A[k]
    if dp[k]==1:
        resstr = str(k)+' '+resstr
    res += dp[k]

print(res)
print(' '.join(resstr))

### FIXED CODE ###

N = int(input())
A = [0]+[int(x) for x in input().split()]
res = [0]*(N+1)
sum_res = 0
for i in range(N):
    # 今見てるところ
    k = N-i
    tmp = 0
    for j in range(k,N+1,k):
       	tmp += res[j]
    res[k] = A[k] ^ tmp%2
    sum_res += res[k]
 
print(sum_res)
print(' '.join([str(i) for i,x in enumerate(res) if x==1]))
### BUGGY CODE ###

x = int(input())
li = list(map(int,input().split()))
for i in range(len(li)):
    for k in range(len(li)):
        if i > k:
            if li[i] == li[k]:
                print('NO')
                exit()
    if i == len(li) -1:
        print('YES')

### FIXED CODE ###

import sys
input = sys.stdin.readline
x = int(input())
from collections import defaultdict
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
for i in dd:
    if dd[i] > 1:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    dp = np.full((N+1,H+1),float('inf'))
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j)
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[N][H]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


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

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = []
for i in range(N):
	dp.append(float("inf"))

dp[0] = 0

for i in range(N):
	for k in range(K):
		if i+k+1 < N:
			dp[i+k+1] = min(dp[i+k+1], dp[i]+abs(h[i+k+1]- h[i]))

print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = []
for i in range(N):
	dp.append(float("inf"))

dp[0] = 0

for i in range(N):
	for k in range(K):
		if i+k+1 < N:
			dp[i+k+1] = min(dp[i+k+1], dp[i]+abs(h[i+k+1]- h[i]))

print(dp[N-1])
### BUGGY CODE ###

import collections

n = int(input())
ln = list(map(int, input().split()))
m = int(input())
lm = list(map(int, input().split()))

c = collections.Counter(lm)

for i in c.keys():
    if ln.count(i) < c[i]:
        print("NO")
        exit()

print("YES")

### FIXED CODE ###

import sys
from collections import Counter
 
N = int(input())
s1 = list(map(int,input().split()))
M = int(input())
s2 = list(map(int,input().split()))
 
c1 = Counter(s1)
c2 = Counter(s2)
 
for k,v in c2.items():
    if k in c1:
        if v > c1[k]:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

n = int(input())
'''
ls = []
ls_re = []
for i in range(1,n+1):
    ls.append(i)
for i in reversed(ls):
    ls_re.append(i)

ans = 0
for i in range(n):
    ans += (ls[i]%ls_re[i])
    #print(ls[i]%ls_re[i],end=" ")
'''
c = 0
for i in range(1,n):
    c += i
    
print(c)
    

### FIXED CODE ###

n = int(input())
c = 0    
an = (n-1)*n//2
print(round(an))
### BUGGY CODE ###

s = input()
q = int(input())
a = []
# for j in range(q):
#     a.extend([list(map(str,input().split()))])
# # print(a)
# for i in a:
for j in range(q):
    i = list(map(str,input().split()))
    if i ==["1"]:
        s = s[::-1]
    elif i[0]=="2" and i[1]=="1":
        s = i[2]+s
    elif i[0]=="2" and i[1]=="2":
        s = s +i[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
a = []
# for j in range(q):
#     a.extend([list(map(str,input().split()))])
# # print(a)
# for i in a:
pre = ""
nex = ""
c = 1
for j in range(q):
    i = list(map(str,input().split()))
    if i ==["1"]:
        c *= -1
        # s = s[::-1]
    elif i[0]=="2" and i[1]=="1":
        # s = i[2]+s
        if c == 1:
            pre=i[2]+pre
        else:
            nex = nex + i[2]
    elif i[0]=="2" and i[1]=="2":
        # s = s +i[2]
        if c ==1:
            nex = nex +i[2]
        else:
            pre = i[2]+pre
s = pre+s+nex
if c ==-1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
j = 0
d = 0
c0 = 0
l = sorted(list(set(a)))
for i in l:
    if i == j+1:
        j = i
        if i in a[c0:]:
            c = a[c0:].index(i)+(n-len(a[c0:]))
        else:break
        if c >= c0:
            d += 1
            c0 = c
        else:break
    else:break
print(n-d if d !=0 else -1)

### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(int, input().split()))
a = deque(a)
d = 0
i = 1
for _ in range(n):
    b = a.popleft()
    if i == b:
        d +=1
        i += 1
        
print(n-d if d !=0 else -1)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=[0,T[0]]
Ares[-1]=[0,A[-1]]
for i in range(1,n):
  if T[i]!=T[i-1]:
    Tres[i]=[0,T[i]]
  else:
    Tres[i]=[1,T[i]]
  if A[-i-1]!=A[-i]:
    Ares[-i-1]=[0,A[-i-1]]
  else:
    Ares[-i-1]=[1,A[-i-1]]
ans=1
for i in range(n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==1 and aa==1:
    ans*=min(tb,ab)
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)

### FIXED CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = [int(x) for x in input().split()]

ans = 1

for x in A:
    ans = ans * x

if ans > 10**(18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
A = [int(x) for x in input().split()]

ans = 1
c=0

A.sort()

for x in A:
    ans = ans * x
    if ans == 0:
        print(0)
        c=1
        break
    elif ans > 10**(18):
        print(-1)
        c=1
        break

if c==0:
    print(ans)
### BUGGY CODE ###

while True:
 try:
  d = 0
  a = int(input())
  for c in range(2,a):
   for b in range(2,c):
    if c % b == 0:
      break
   else:
     d += 1

  print d
 except EOFError:
   break

### FIXED CODE ###


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env python
import sys
 
list=1000000*[1]
 
list[0] = 0
list[1] = 0
for i in range(1,1000000):
    if list[i] == 1:
        for j in range(i*i,1000000,i):
            list[j] = 0
 
for i in range(2,1000000):
    list[i] += list[i-1]
     
for line in sys.stdin:
    a = int(line)
    print list[a]