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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
f = 1
finv = 1
p2 = 1
for i in range(1, MAX_N+1):
    # fac[i] = fac[i-1] * i % MOD
    f *= i
    f %= MOD
    fac[i] = f
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    # fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD
    finv *= pow(i, MOD-2, MOD)
    finv %= MOD
    fac_inv[i] = finv
    p2 *= 2
    p2 %= MOD
    mod_pow2_n[i] = p2

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
def single_mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    if r > n - r:
        r = n - r
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD
    return ret

n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = tuple(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())
Exam = []
maxD = 0
for i in range(Q):
    l, r = map(int, input().split())
    maxD = max(maxD, (r-l))
    Exam.append((l,r))

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, maxD+1, D):
    for start in range(H*W+1-w):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

for l, r in Exam:
    print(DP[l][r])

### FIXED CODE ###

H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [0] * (H*W+1)

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])
### BUGGY CODE ###

n, k = map(int, input().split())
scs = list(map(int, input().split()))
#print(scs)
#res = []
re = 1
pre = 0

for i in range(n - k + 1):
    for j in range(k):
        re = re * scs[i + j]
    if pre < re and i != 0:
        print("Yes")
    elif i != 0:
        print("No")
    pre = re
    re = 1

### FIXED CODE ###

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

for i in range(k, n):
    if  scs[i] > scs[i - k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from sys import stdin


def LI(): return list(map(int, stdin.readline().split()))


inf = 1000000007


def main():
    N, K = LI()
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    stack = [0]
    ans = 1
    done = [False for _ in range(N)]
    while len(stack) > 0:
        now = stack.pop(0)
        done[now] = True
        cnt = 0
        for x in graph[now]:
            if not done[x]:
                cnt += 1
                stack.append(x)
        if now == 0:
            for i in range(cnt):
                ans = (K - 1 - i) * ans % inf
        else:
            for i in range(cnt):
                ans = (K - 2 - i) * ans % inf
    print(ans * K % inf)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import heapq as hq

x,y,z,k = map(int,input().split())
a = list(map(lambda x:int(x) * (-1),input().split()))
b =list(map(lambda x:int(x) * (-1),input().split()))
c = list(map(lambda x:int(x) * (-1),input().split()))
a.sort()
b.sort()
c.sort()
possibles = [(a[0]+b[0]+c[0],0,0,0)]

done = [[[0 for _ in range(z)]for _ in range(y)] for _ in range(x)]
done[0][0][0] = 1
def neibor(ai,bi,ci,possibles,done):
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not done[aj][bj][cj]):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done[aj][bj][cj] = 1
    

def conf(possibles,done):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    neibor(ai,bi,ci,possibles,done)

for i in range(k):
    conf(possibles,done)

### FIXED CODE ###

import heapq as hq

x,y,z,k = map(int,input().split())
a = list(map(lambda x:int(x) * (-1),input().split()))
b =list(map(lambda x:int(x) * (-1),input().split()))
c = list(map(lambda x:int(x) * (-1),input().split()))
a.sort()
b.sort()
c.sort()
possibles = [(a[0]+b[0]+c[0],0,0,0)]

done = set()
done |= {(0,0,0)}
def neibor(ai,bi,ci,possibles,done):
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not (aj,bj,cj) in done):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done  |= {(aj,bj,cj)}
    

def conf(possibles,done):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    neibor(ai,bi,ci,possibles,done)

for i in range(k):
    yam,ai,bi,ci = hq.heappop(possibles)
    print(-1*yam)
    for aj,bj,cj in [(ai+1,bi,ci),(ai,bi+1,ci),(ai,bi,ci+1)]:
        if (aj<=x-1) and (bj<=y-1) and (cj<=z-1) and (not (aj,bj,cj) in done):
            hq.heappush(possibles,(a[aj]+b[bj]+c[cj],aj,bj,cj))
            done  |= {(aj,bj,cj)}
### BUGGY CODE ###

s = input()
q = int(input())
que = [0] * q
t = []
f = []
c = []
for i in range(q):
    que[i] = list(map(str,input().split()))
    if(len(que[i])==3):
        if que[i][1] == '1':
            s = que[i][2] + s
        else:
            s += que[i][2]
    else:
        s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s = input()
sque = deque(s)
q = int(input())
que = [0] * q
flg = False
for i in range(q):
    que[i] = (list(map(str,input().split())))
    if(len(que[i])==3):
        if que[i][1] == '1':
            if flg:
                sque.append(que[i][2])
            else:
                sque.appendleft(que[i][2])
        else:
            if flg:
                sque.appendleft(que[i][2])
            else:
                sque.append(que[i][2])
    else:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    sque.reverse()
    print("".join(list(sque)))
else:
    print("".join(list(sque)))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    ans = [0] * 60
    
    
    x0 = 0
    x1 = 0
    for j in range(N):
        if (A[j]>>0)&1:
            x1 += 1
        else:
            x0 += 1
    
    ans[0] = x0*x1
    for i in range(1, 60):
        # x0 = len([j for j in range(N) if not (A[j]>>i)&1])
        # x1 = len([j for j in range(N) if (A[j]>>i)&1])
        x0 = 0
        x1 = 0
        for j in range(N):
            if (A[j]>>1)&1:
                x1 += 1
            else:
                x0 += 1
            A[j] = A[j] >> 1

        ans[i] = x0*x1

    x = 0
    for i in range(60):
        # print(i, 2**i)
        x += pow(2, i) * ans[i] % MOD

    print(x%MOD)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    ans = [0] * 60
    
    
    for i in range(60):
        # x0 = len([j for j in range(N) if not (A[j]>>i)&1])
        # x1 = len([j for j in range(N) if (A[j]>>i)&1])
        x0 = 0
        x1 = 0
        for j in range(N):
            if (A[j]>>i)&1:
                x1 += 1
            else:
                x0 += 1

        ans[i] = x0*x1

    x = 0
    for i in range(len(ans)):
        # print(i, 2**i)
        x += pow(2, i) * ans[i] % MOD

    print(x%MOD)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import sys

sys.setrecursionlimit(10 ** 9)

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    ans[pos] += ans[before]
    for next_pos in root[pos]:
        root[next_pos].remove(pos)
        dfs(next_pos, pos)

dfs(0, -1)

for i in range(n):
    print(ans[i], end=" ")

### FIXED CODE ###

from sys import setrecursionlimit, stdin

setrecursionlimit(10 ** 9)

def input():
    return stdin.readline()

n, q = map(int, input().split())
root = [[] for _ in range(n)]
ans = [0 for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    root[a - 1].append(b - 1)
    root[b - 1].append(a - 1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
    
def dfs(pos, before):
    for next_pos in root[pos]:
        if next_pos == before:
            continue
        ans[next_pos] += ans[pos]
        dfs(next_pos, pos)

dfs(0, -1)

for i in range(n):
    print(ans[i], end=" ")
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
counter=[0 for _ in range(n)]
a=list(input().split())
for i in a:
    counter[int(i)-1]+=1
for j in counter:
    print(j)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()

P = [[] for _ in range(ord('Z') - ord('A') + 1)]
for i in range(N):
  p = ord(S[i]) - ord('A')
  P[p].append(i)

G = [1 for _ in range(N)]
for i in range(Q):
  t,d = input().split()
  ti = ord(t) - ord('A')
  dG = []
  
  for j in P[ti]:
    g = G[j]
    G[j] = 0
    dG.append(g)
  for j in P[ti]:
    dg = dG.pop(0)
    if ('L' == d):
      if (0 < j):
        G[j-1] += dg
    elif ('R' == d):
      if (j < (N-1)):
        G[j+1] += dg
print(sum(G))


### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
C = [tuple(map(str, input().split())) for _ in range(Q)]
C = C[::-1]

left = -1
right = N

for (t,d) in C:
  if ('L' == d):
    if (S[left+1] == t):
      left += 1
      if (N-1 <= left):
        print(0)
        exit()
    if (right < N):
      if (S[right] == t):
        right += 1
        if (N < right):
          right = N
  else:
    if (S[right-1] == t):
      right -= 1
      if (right <= 0):
        print(0)
        exit()
    if (-1 < left):
      if (S[left] == t):
        left -= 1
        if (left < -1):
          left = -1

print(right - left - 1)
### BUGGY CODE ###

import itertools
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()))
result = [a + b  for (a,b) in list(itertools.product(A, B))]
result.sort(reverse = True)
result = [s + c for (s,c) in list(itertools.product(result[:K], C))]
result.sort(reverse = True)
for i in range(K):
    print(result[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)
t =[]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k) <= K:
                t.append(A[i]+B[j]+C[k])
            else:break
t.sort(reverse=True)
for i in range(K):
    print(t[i])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0

# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(n):
    #ll += 1
    #print(i)
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
for i in A:
    dic[i] += 1
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:    
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
for i in A:
   dic[i] += 1
A = list(set(A))
# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(len(A)):
    #ll += 1
    #print(i)
    #print(A[i])
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)
### BUGGY CODE ###

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

cost = [[float('inf')]*(m+1) for i in range(n+1)]
#Aからi冊、Bからｊ冊読むときにかかる時間がcost[i][j]
              
cost[0][0] = 0
max_count = 0

i = 0
while i<=n:
  j = 0
  while j<m:
    cost[i][j+1] = cost[i][j] + b[j]
    j += 1
    if cost[i][j]<=k:
      max_count = max(max_count,i+j)
    else:
      break
  if i == n:
    break
  cost[i+1][0] = cost[i][0] + a[i]
  i += 1
  if cost[i][0]<=k:
    max_count = max(max_count,i)
  else:
    break
print(max_count)

### FIXED CODE ###

def judge(num):
  if num>n+m:
    return False
  for i in range(max(0,num-m),min(n,num)+1):
    if a_cumsum[i] + b_cumsum[num-i]<=k:
      return True
  return False
 
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
 
a_cumsum = [0]
b_cumsum = [0]
for i in a:
  a_cumsum.append(a_cumsum[-1]+i)
for i in b:
  b_cumsum.append(b_cumsum[-1]+i)
  
left = 0
right = k+1
 
while right-left>1:
  mid = (right+left)//2
  
  if judge(mid):
    left = mid
  else:
    right = mid
 
print(left)
### BUGGY CODE ###

import bisect
import heapq
N,Q = list(map(int,input().split(" ")))

hitos = []
ans = [-1] * Q
queries =[]
heapq.heapify(queries)
events = {}
for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ



for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(min(events))
        else:
            print(-1)
    if kind == -1:
        events[x] = x
    if kind == 1:
        events.pop(x)



### FIXED CODE ###

import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# for i in range(N):
    # S,T,X =list(map(int,input().split(" ")))
    # lt = S -X -0.5
    # rt = T -X -0.5
    # queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

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

X = int(input())

possible_locations = [0]
previous_point = 0

for i in range(100000000):
    length = i + 1

    possible_locations_previous = possible_locations[:]
    for start_from in possible_locations_previous:
        new_points = [start_from, start_from + length ,start_from - length]
        possible_locations += new_points

    possible_locations = list(set(possible_locations))

    if X in possible_locations:
        print(i+1)
        break


### FIXED CODE ###

X = int(input())
previous = 0 
for i in range(100000):
    previous += i 
    if X <= previous:
        print(i)
        break
### BUGGY CODE ###

import collections

N = int(input())
s = [input() for i in range(N)]
k = 0
i = 0
ans =[]

ss=sorted(s)
c = collections.Counter(ss)
for i in range(len(c)):
    if c.most_common()[i][1] ==c.most_common()[0][1]:
        ans.append(c.most_common()[i][0])

ans_A =sorted(ans)
for i in range(len(ans_A)):
    print(ans_A[i])

### FIXED CODE ###

import collections

N = int(input())
s = [input() for i in range(N)]
k = 0
i = 0
ans =[]

c = collections.Counter(s)
c_mc=c.most_common()
for i in range(len(c)):
    if c_mc[i][1] ==c_mc[0][1]:
        ans.append(c_mc[i][0])

ans_A =sorted(ans)
for i in range(len(ans_A)):
    print(ans_A[i])
### BUGGY CODE ###

S = input()
Q = int(input())
parity = 0

for i in range(Q):
    query = input().split()
    if len(query) == 1:
        parity += 1
    else:
        if int(query[1]) == 1 + (parity % 2):
            S = query[2] + S
        else:
            S = S + query[2]

if parity % 2 == 1:
    S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
parity = 0

for i in range(Q):
    query = input().split()
    if len(query) == 1:
        parity += 1
    else:
        if int(query[1]) == 1 + (parity % 2):
            S.appendleft(query[2])
        else:
            S.append(query[2])
S = ''.join([c for c in S])
if parity % 2 == 1:
    S = S[::-1]
print(S)
### BUGGY CODE ###

a = input()
q = int(input())

fflag = 0
for i in range(q):
  qi = input()
  if( qi == "1"):
    fflag += 1 
  else:
    if( fflag%2 == 0 ):
      if( qi[2] == "2" ):
        a += qi[4]
      else:
        a = qi[4] + a
    else:
      if( qi[2] == "2" ):
        a = qi[4] + a
      else:
        a += qi[4]      
    
if( fflag%2==0 ):
  print( a )
else:
  print( a[::-1] )	

### FIXED CODE ###

a = input()
q = int(input())

fflag = 0
ato = ""
mae = ""
for i in range(q):
  qi = input()
  if( qi == "1"):
    fflag += 1 
  else:
    if( fflag%2 == 0 ):
      if( qi[2] == "2" ):
        ato += qi[4]
      else:
        mae += qi[4]
    else:
      if( qi[2] == "2" ):
        mae += qi[4]
      else:
        ato += qi[4]      
    
a = mae[::-1] + a + ato    
    
if( fflag%2==0 ):
  print( a )
else:
  print( a[::-1] )
### BUGGY CODE ###

n, m = map(int, input().split())
broken_list = [int(input()) for _ in range(m)]
enable_list = [i for i in range(2, n+1) if not i in broken_list]
a = [0] * (n+1)
a[0] = 1
a[1] = 0 if 1 in broken_list else 1

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in enable_list:
  a[i] = a[i-1] + a[i-2]

print(a[n]%1000000007)

### FIXED CODE ###

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

a = 1
b = 1

i = 2

for j in range(m):
  ind = int(input())
  if ind == 1:
    b = 0
    continue
  while i < ind:
    a, b = b, a+b
    i += 1
  else:
    a, b = b, 0
    i += 1
    
while i < n+1:
  a, b = b, a+b
  i += 1
  
  
print(b%1000000007)
### BUGGY CODE ###

import math

def is_prime(n):
    for p in range(2, int(math.sqrt(n)) + 1):
        if n % p == 0:
            return False
    return True

def prime_factorize(n):
    lst = []
    while n % 2 == 0:
        lst.append(2)
        n = n / 2
    a = 3
    while n > 1:
        if n % a == 0:
            lst.append(a)
            n = n / a
        else:
            a += 2
    return lst

A, B = map(int, input().split())
lst = prime_factorize(min(A, B))
ret = 1
for n in set(lst):
    if is_prime(n) and A % n == 0 and B % n == 0:
        ret += 1

print(ret)

### FIXED CODE ###

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
 
def prime_factorize(n):
    a = 2
    lst = []
    while a * a <= n:
        if n % a == 0:
            n = n / a
            lst.append(a)
        else:
            a += 1
    if n > 1:
        lst.append(n)
    return lst
 
A, B = map(int, input().split())
n = gcd(A, B)
lst = prime_factorize(n)
print(len(set(lst)) + 1)