Harryxun/stf_run huggingface dataset:
from collections import deque
S = deque(list(input().strip()))
Q = int(input().strip())
flag = 1
for i in range(Q):
  line = input().strip()
  if len(line) == 1:
    flag = 1 - flag
  else:
    _, F, C = line.strip().split()
    if flag:
      if int(F) == 1:
        S.appendleft(C)
      else:
        S.append(C)
    else:
      if int(F) == 1:
        S.append(C)
      else:
        S.appendleft(C)

if flag:
  print(''.join(S))
else:
  print(''.join(S[::-1]))
    

### FIXED CODE ###

from collections import deque
S = deque(list(input().strip()))
Q = int(input().strip())
flag = 1
for i in range(Q):
  line = input().strip()
  if len(line) == 1:
    flag = 1 - flag
  else:
    _, F, C = line.strip().split()
    if flag:
      if int(F) == 1:
        S.appendleft(C)
      else:
        S.append(C)
    else:
      if int(F) == 1:
        S.append(C)
      else:
        S.appendleft(C)

if flag:
  print(''.join(S))
else:
  print(''.join(list(reversed(S))))
import math
from decimal import Decimal, getcontext
getcontext().prec = 0
a,b,c = map(int,input().split())

if c - a - b < 0:
  print("No")
elif Decimal(c**0.5 - a**0.5 - b**0.5) < 0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###


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

if 4*a*b - (c - a - b) ** 2 < 0 and c - a - b > 0:
  print("Yes")
  
else:
  print("No")
(a,b):
print(a*b,2*(a+b))


### FIXED CODE ###

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

print(A*B,2*(A+B))
H, W, A, B = map(int, input().split())

ans = [[0 for _ in range(W)] for _ in range(H)]

if A == 0:
  for i in range(H):
    for j in range(W):
      if i < B:
        ans[i][j] = 1
      else:
        ans[i][j] = 0
elif B == 0:
  for i in range(H):
    for j in range(W):
      if j < A:
        ans[i][j] = 1
      else:
        ans[i][j] = 0
else:
  w, h = 0, 0
  while w < W or h < H:
    for i in range(w, min(w + B, W)):
      for j in range(h, min(h + A, H)):
        ans[i][j] = 1
    w += B
    h += A

for i in range(H):
  for j in range(W):
    print(ans[i][j], end = "")
  print()

### FIXED CODE ###

H, W, A, B = map(int, input().split())

ans = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(A):
    ans[i][j] = 1

for i in range(B):
  for j in range(W):
    ans[i][j] ^= 1

for i in range(H):
  for j in range(W):
    print(ans[i][j], end = "")
  print()
a = {x:0 for x in range(ord('a'), ord('z') + 1)}

while True:
    text = input()
    for x in list(text.lower()):
        print(x)
        a[ord(x)] += 1

    for x in range(ord('a'), ord('z') + 1):
        print(chr(x), ':', a[x])

### FIXED CODE ###

a = {x:0 for x in range(ord('a'), ord('z') + 1)}

while True:
    try:
        text = input()
        for x in text:
            if ord('a') <= ord(x) <= ord('z') or ord('A') <= ord(x) <= ord('Z'):
                a[ord(x.lower())] += 1
    except EOFError:
        break

for x in range(ord('a'), ord('z') + 1):
    print(chr(x), ':', a[x])
n = input()
a = list(input().split())

b = set(a)

if len(a) == len(b):
  print(YES)
else:
  print(NO)


### FIXED CODE ###

n = input()
a = list(input().split())

b = set(a)

if len(a) == len(b):
  print("YES")
else:
  print("NO")
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n = int(input())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
W = int(input())
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)


### FIXED CODE ###

"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)
l = input().split()
if l[1] = "+":
  print(int(l[0])+int(l[2]))
else:
  print(int(l[0])-int(l[2]))

### FIXED CODE ###

l = input().split()
if l[1] == "+":
  print(int(l[0])+int(l[2]))
else:
  print(int(l[0])-int(l[2]))
lim=998244353
n,m,k=map(int,input().split())
def f(n,k):
    ans = m %lim
    ans = (ans *pow(m-1,n-k-1,lim)) % lim
    ans = (ans * comb(n-1,k,lim)) % lim
    return ans

#n,m,k = 60522, 114575, 7559
sum_ = 0
for j in range(k+1):
    ans = m %lim
    #print(m-j-1,n,j)
    ans = (ans *pow(m-1,n-j-1,lim)) % lim
    ans = (ans * comb(n-1,j,lim)) % lim
    #print(ans)
    sum_ = (sum_+ans) % lim
print(sum_)

### FIXED CODE ###

class Combination():
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fact = self.make_fact(n)
        self.fact_inv = self.make_fact_inv(n)
    def make_fact(self, n):#0~nの階乗を求める
        res = [1]*(n+1)
        for i in range(1, n+1):
            res[i] = res[i-1]*i%self.mod
        return res
    def make_fact_inv(self, n):#0~nの階乗のmodに関する逆元を求める
        fact_inv = [1]*(n+1)
        fact_inv[n] = pow(self.fact[n], self.mod-2, self.mod)#フェルマーの小定理
        for i in range(n, 0, -1):
            fact_inv[i-1] = fact_inv[i]*i%self.mod
        return fact_inv
    def comb(self, m, k):
        return self.fact[m]*self.fact_inv[k]*self.fact_inv[m-k]%self.mod
    


lim=998244353
n,m,k=map(int,input().split())

#n,m,k = 60522, 114575, 7559
sum_ = 0
comb=Combination(n,lim)
for j in range(k+1):
    ans = m %lim
    #print(m-j-1,n,j)
    ans = (ans *pow(m-1,n-j-1,lim)) % lim
    ans = (ans * comb.comb(n-1,j)) % lim
    #print(ans)
    sum_ = (sum_+ans) % lim
print(sum_)
N, X, T = map(int,input().split())
C=1
  if N%X!=0:
     C=N//X+1
  else:
    C=N//X

print(C*T)
    
   

### FIXED CODE ###

N, X, T = map(int,input().split())
C=1
if N%X!=0:
     C=N//X+1
else:
    C=N//X
 
print(C*T)
from fractions import gcd


def main(input_1, input_2):
    left = [0] * (input_1+1)
    for i in range(input_1):
        left[i+1] = gcd(left[i], input_2[i])

    right = [0] * (input_1 + 1)
    i = input_1 - 1
    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])
        i -= 1

    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])

    res = 0
    for i in range(input_1):
        l = left[i]
        r = right[i+1]
        gcd_val = gcd(l, r)
        if gcd_val > res:
            res = gcd_val

    return res


if __name__ == "__main__":
    input_1 = input()
    input_2 = list(map(int, input().split()))
    print(main(input_1, input_2))


### FIXED CODE ###

from fractions import gcd


def main(input_1, input_2):
    left = [0] * (input_1+1)
    for i in range(input_1):
        left[i+1] = gcd(left[i], input_2[i])

    right = [0] * (input_1 + 1)
    i = input_1 - 1
    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])
        i -= 1

    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])

    res = 0
    for i in range(input_1):
        l = left[i]
        r = right[i+1]
        gcd_val = gcd(l, r)
        if gcd_val > res:
            res = gcd_val

    return res


if __name__ == "__main__":
    input_1 = int(input())
    input_2 = list(map(int, input().split()))
    print(main(input_1, input_2))
K = int(input())
A = ""
for i in range(K):
  A += ACL
  
print(A)

### FIXED CODE ###

K = int(input())
A = ""
for i in range(K):
  A += "ACL"
  
print(A)
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_D

def postorder(binary_tree, target_index, result):
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    
    if not left == -1:
        postorder(binary_tree, left, result)
    if not right == -1:
        postorder(binary_tree, right, result)

    result.append(target_index)

def solve(preorder_list, inorder_list, result):
    if len(inorder_list) == 1:
        return inorder_list[0]
    #print(result)
    parent = preorder_list[0]

    left_trees = inorder_list[:inorder_list.index(parent)]
    right_tree_index = 1
    if left_trees:
        result[parent]["left"] = solve(preorder_list[1:], left_trees, result)
        right_tree_index = preorder_list.index(left_trees[-1])
        
    right_trees = inorder_list[inorder_list.index(parent) + 1:]
    if right_trees:
        result[parent]["right"] = solve(preorder_list[right_tree_index:], right_trees, result)

    return parent

def reconstruction(preorder_list, inorder_list, node_num):
    result = [{"left":-1,"right":-1} for i in range(node_num + 1)]
    solve(preorder_list, inorder_list, result)
    return result

def main():
    node_num = int(input())
    preorder_list = [int(a) for a in input().split()]
    inorder_list = [int(a) for a in input().split()]
    binary_tree = reconstruction(preorder_list, inorder_list, node_num)
    postorder_list = []
    postorder(binary_tree, preorder_list[0], postorder_list)
    print(*postorder_list)
if __name__ == "__main__":
    main()

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_D

def postorder(binary_tree, target_index, result):
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    
    if not left == -1:
        postorder(binary_tree, left, result)
    if not right == -1:
        postorder(binary_tree, right, result)

    result.append(target_index)

def solve(preorder_list, inorder_list, result):
    #print(preorder_list, inorder_list)
    if len(inorder_list) == 1:
        return inorder_list[0]
    
    parent = preorder_list[0]
    left_trees = inorder_list[:inorder_list.index(parent)]
    right_tree_index = 1
    if left_trees:
        result[parent]["left"] = solve(preorder_list[1:], left_trees, result)
        right_tree_index = len(left_trees) + 1
        
    right_trees = inorder_list[inorder_list.index(parent) + 1:]
    if right_trees:
        result[parent]["right"] = solve(preorder_list[right_tree_index:], right_trees, result)

    return parent

def reconstruction(preorder_list, inorder_list, node_num):
    result = [{"left":-1,"right":-1} for i in range(node_num + 1)]
    solve(preorder_list, inorder_list, result)
    return result

def main():
    node_num = int(input())
    preorder_list = [int(a) for a in input().split()]
    inorder_list = [int(a) for a in input().split()]
    binary_tree = reconstruction(preorder_list, inorder_list, node_num)
    postorder_list = []
    postorder(binary_tree, preorder_list[0], postorder_list)
    print(*postorder_list)
if __name__ == "__main__":
    main()
N = int(input())
cards = []
for i in range(N):
	cards.append(list(map(int,input().split())))

points = []
for i in range(N):
	points.append(0)

for i in range(3):
	for j in range(N):
		flag = 0
		for k in range(j):
			if cards[j][i] == cards[k][i]:
				flag = 1
				break
		if j+1<N:
			for k in range(j+1,N):
				if cards[j][i] == cards[k][i]:
					flag = 1
					break
		if flag==0: points[j] += cards[j][i]

for i in range(N):
	print(points[i])


### FIXED CODE ###

K,S = list(map(int,input().split()))

count = 0

if K>S: n=S
else: n=K
x=0
for i in range(n+1):
	if K>S-x: m=S-x
	else: m=K
	y=0
	for j in range(m+1):
		if S-x-y<=K: count +=1
		y+=1
	x+=1

print(count)
a = r
N = 2

print(a ** N)

### FIXED CODE ###

r = int(input())
print(r*r)
s = input()
n = len(s)

t = s[:(n-1)//2]
u = s[(n+3)//2:]

if (s == s[::-1]
    and len(t) > 0 and len(u) > 0 and
    and t == t[::-1]
    and u == u[::-1]):
  print('Yes')
else:
  print('No')
  


### FIXED CODE ###

s = input()
n = len(s)

t = s[:(n-1)//2]
u = s[(n+3)//2-1:]

if (s == s[::-1]
    and t == t[::-1]
    and u == u[::-1]):
  print('Yes')
else:
  print('No')
N, X, T = map(int, input().split())
y = N // X
c = N % X
print((y * T + T) if c else (y * T))

### FIXED CODE ###

s=input()
for i in range(4)[::-1]:
    if "R"*i in s:
        print(i)
        break
x = input()

if x{-1} == [2,4,5,7,9]:
    print("hon")

elif x{-1} == [0,1,6,8]:
    print("pon")

else:
    print("bon")


### FIXED CODE ###

x = int(input()[-1])

if x in [2,4,5,7,9]:
    print("hon")

elif x in [0,1,6,8]:
    print("pon")

else:
    print("bon")
n,d = map(int,input().split())
x_list_kai = [list(map(int,input().split())) for x in range(3)]


import itertools,math
dis = []
for x in itertools.combinations(x_list_kai,2):
    distance = 0
    for dim in range(0,d):
        result  = 0
        for y in x:
            if result == 0:
                result = y[dim]
            else:
                result -= y[dim]
            
        result  = result **2
        distance += result
    dis.append(math.sqrt(distance))
    
counter = 0
for i in dis:
    if i.is_integer() == True:
        counter += 1
print(counter)

### FIXED CODE ###

n,d = map(int,input().split())
x_list_kai = [list(map(int,input().split())) for x in range(n)]


import itertools,math
dis = []
for x in itertools.combinations(x_list_kai,2):
    distance = 0
    for dim in range(0,d):
        result  = 0
        for y in x:
            if result == 0:
                result = y[dim]
            else:
                result -= y[dim]
            
        result  = result **2
        distance += result
    dis.append(math.sqrt(distance))
    
counter = 0
for i in dis:
    if i.is_integer() == True:
        counter += 1
print(counter)
import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp[:]
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e])
    idx_prev = np.hstack([np.full(i-1, False), s[i:] == e, [False]])
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]
dp[0][0] = 1

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)
import sys
def main():
    input = sys.stdin.readline
    S = input()
    if S == "Sunny":
        ans = "Cloudy"
    elif S == "Cloudy":
        ans = "Rainy"
    elif S == "Rainy":
        ans = "Sunny"

    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()
    if S == "Sunny":
        ans = "Cloudy"
    elif S == "Cloudy":
        ans = "Rainy"
    elif S == "Rainy":
        ans = "Sunny"
    print(ans)
if __name__ == '__main__':
    main()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

N,M = (int(x) for x in input().split())
if M > N:
    N,M = M,N
    S,T = T,S
S = list(input())
T = list(input())
dn = make_divisors(N)
dm = make_divisors(M)
dnm = dn & dm
if dnm == {1}:
    if S[0] == T[0]:
        print(N*M)
    else:
        print('-1')
else:
    gcd = max(dnm)
    n = N // gcd
    m = M // gcd
    for i in range(N//n):
        if S[n*i] != T[m*i]:
            print('-1')
            break
    else:
        print(N*M//gcd)

### FIXED CODE ###

def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

N,M = (int(x) for x in input().split())
S = list(input())
T = list(input())
if M > N:
    N,M = M,N
    S,T = T,S
dn = make_divisors(N)
dm = make_divisors(M)
dnm = dn & dm
if dnm == {1}:
    if S[0] == T[0]:
        print(N*M)
    else:
        print('-1')
else:
    gcd = max(dnm)
    n = N // gcd
    m = M // gcd
    for i in range(N//n):
        if S[n*i] != T[m*i]:
            print('-1')
            break
    else:
        print(N*M//gcd)
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    Boo = [True]*len(B)
    _,s = sieve((10**6)+7)

    zero =  A.count(1)
    if A.count(1)>1:
        print(0)
        return
    if A.count(1)==1:
        print(1)
        return

    for i in range(len(B)):
        for j in range(i+1,len(B)):
            if Boo[j] and s[j] and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(len(B)):
        if Boo[i] and A.count(B[i])==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=list(Counter(a).values())
lst=[]
for i in range(len(b)):
  if b[i]>1:
    lst.append(int(Counter(a).keys()[i]))
Lst=set(lst)
lst.sort(reverse=True)
Lst_2=set(lst)
if len(Lst)<2:
  print(0)
else:
  print(Lst_2[0]*Lst_2[1])
    


### FIXED CODE ###

import collections
n=int(input())
a=map(int,input().split())
b=list(collections.Counter(a).items())
lst=[]
Lst=[]
for i in range(len(b)):
  if b[i][1]>1:
    lst.append(int(b[i][0]))  
    if b[i][1]>3:
      Lst.append(int(b[i][0]))
if len(lst)<2 and len(Lst)==0:
  print(0)
else:
  if len(lst)==1:
    Lst.sort(reverse=True)
    print(Lst[0]**2)
  else:
    if len(Lst)>0:
      lst.sort(reverse=True)
      Lst.sort(reverse=True)
      print(max(lst[0]*lst[1],Lst[0]**2))     
    else:
      lst.sort(reverse=True)
      print(lst[0]*lst[1])
n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
dp[2]=2

for i in range(m):
    dp[t[i]]=0

for i in range(3,n+1):
    if dp[i]==-1:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)


### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=1
dp[1]=1
for i in range(m):
    dp[t[i]]=0


for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)
x = input()

if x >= 30:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

x = input()

if int(x) >= 30:
    print("Yes")
else:
    print("No")
N, K = map(int, input().split())

if K % 2 != 0:
    ans = (N // K)**3
else:
    full = []
    for i in range(K, N, K):
        full.append(i)
        ans = len(full) ** 3

    half = []
    for i in range(int(K/2), N, int(K/2)):
        half.append(i)
        half = list(set(half) - set(full))
        ans += len(half) ** 3

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())

# N, K = 3, 2

if K % 2 != 0:
    ans = (N // K)**3
else:
    full = []
    half = []
    for i in range(int(K/2), N+1, int(K/2)):
        if i % K == 0:
            full.append(i)
        else:
            half.append(i)

    ans = len(half) ** 3 + len(full) ** 3

print(ans)
N = int(input())
A=[]
for i in range(N):
    A += [int(input())]

sort(A)
print(sum(A) - A[N-1]//2)

### FIXED CODE ###

N = int(input())
A=[]
for i in range(N):
    A += [int(input())]

A.sort()
print(sum(A) - A[N-1]//2)
a=str(input())
b=a.replace(1,9)
c=b.replace(9,1)
print(b)

### FIXED CODE ###

a=int(input())
b=1110-a
print(b)
k,n=map(int,input().split())
a=list(map(int,input().split())
a.append(a[0]+k)
al=[a[i+1]-a[i] for i in range(n)]
print(k-max(al))

### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
a.append(a[0]+k)
al=[a[i+1]-a[i] for i in range(n)]
print(k-max(al))
from string import*
from itertools import*
b = ascii_lowercase
s = input()
if len(s) < 26:
    print(s + sorted(set(b) - set(s))[0])
else:
    d = [p,len(list(k)) for p, k in groupby([i < j for i, j in zip(s[-1::-1], t[-2::-1])])][0] - 2
    print(-(d < -26) or s[:d] + sorted(set(s[d+1:]) - set(b[:ord(s[d]) - 97]))[0])

### FIXED CODE ###

#!/usr/bin/env python3
from string import*
from itertools import*
b = ascii_lowercase
s = input()
l = len(s)
if l < 26:
    print(s + sorted(set(b) - set(s))[0])
else:
    t = s[::-1]
    a = [(p, len(list(k))) for p, k in groupby([i < j for i, j in zip(t, t[1:])])][0]
    d = - a[0]*a[1] - 2
    print(-(d < -26) or s[:d] + sorted(set(s[d+1:]) - set(b[:ord(s[d]) - 97]))[0])
ss=input()
if ss[0] == ss[1] ==s[2] = "R":
  print(3)
elif ss[0] == s[1] = "R" or ss[1]==ss[2] = "R" or ss[2] == ss[0] = "R"
  print(2)
elif "R" in ss:
  print(1)
else:
  print(0)

### FIXED CODE ###

ss=input()
if ss[0] == ss[1] ==ss[2] == "R":
  print(3)
elif ss[0] == ss[1] == "R" or ss[1]==ss[2] == "R":
  print(2)
elif "R" in ss:
  print(1)
else:
  print(0)
import sys

def gcd(x,y):
    while y:
        x,y = y , x % y 
    return x

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

lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm,i)
for i in a:
    if (lcm/i)%2 == 0:
        print(0)
        sys.exit()
print((m+lcm//2)//lcm)

### FIXED CODE ###

import sys

def gcd(x,y):
    while y:
        x,y = y , x % y 
    return x

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

lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm,i)
for i in a:
    if (lcm//i)%2 == 0:
        print(0)
        sys.exit()
print((m+lcm//2)//lcm)
lst=input().split()
x_1=int(lst[0])
y_1=int(lst[1])
x_2=int(lst[2])
y_2=int(lst[3])
dis=((x_1-x_2)**2+(y_1-y_2)**2)**(1/2)
print(dis)



### FIXED CODE ###

lst=input().split()
lst=list(map(lambda i:float(i),lst))
x_1=lst[0]
x_2=lst[1]
y_1=lst[2]
y_2=lst[3]
dis=((x_1-y_1)**2+(x_2-y_2)**2)**(1/2)
print(dis)
import numpy as np
N, M = map(int, input().split())
A = np.array([list(input()) for _ in range(N)])
B = np.array([list(input()) for _ in range(M)])
# print('AB', A, B)
for i in range(N - M + 1):
    for j in range(N - M + 1):
        # print('i j', i, j)
        A_subset = A[i:i + N - 1, j:j + N - 1]
        # print('A_subset', A_subset)
        if np.all(A_subset == B):
            print('Yes')
            exit()
print('No')


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array([list(input()) for _ in range(N)])
B = np.array([list(input()) for _ in range(M)])
# print('AB', A, B)
for i in range(N - M + 1):
    for j in range(N - M + 1):
        # print('i j', i, j)
        A_subset = A[i:i + M, j:j + M]
        # print('A_subset', A_subset)
        if np.all(A_subset == B):
            print('Yes')
            exit()
print('No')
n=inr(input())
a=list(map(int,input().split()))

odd=True
for p in a:
  if p%2==0:
    odd=False
    
print(3**n-1-(1 if not odd else 0))

### FIXED CODE ###

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

odd=0
even=0
for i in range(n):
  if a[i]%2==1:
    odd+=1
  else:
    even+=1

all=3**n
oddgr=2**even
print(all-oddgr)