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

import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
# [[10 ** 9, 1, 2],
#  [3, 10 ** 9, 2]
#  [10 ** 9, 4, 7]]


input = sys.stdin.readline


def main():
    N = int(input())
    ABC = [[int(x) for x in input().split()] for _ in range(N - 1)]

    edge = [[10 ** 9 + 1] * N for j in range(N)]
    for a, b, c in ABC:
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=10 ** 9 + 1)
    d = floyd_warshall(G)

    Q, K = [int(x) for x in input().split()]
    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(int(d[x - 1][K - 1] + d[K - 1][y - 1]))
        
    


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(d[x - 1] + d[y - 1])


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

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
field=[0]+["#"+input()+"#" for i in range(h)]+[0]
field[0],field[-1]="#"*(w+2),"#"*(w+2)
l,r,u,d=[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if field[i][j]=="#":continue
    l[i][j]=l[i][j-1]+1
    u[i][j]=u[i-1][j]+1
for i in range(1,h+1)[::-1]:
  for j in range(1,w+1)[::-1]:
    if field[i][j]=="#":continue
    r[i][j]=r[i][j+1]+1
    d[i][j]=d[i+1][j]+1
ans=0
for i in range(h+2):
  for j in range(w+2):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if c>ans:ans=c
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
field=[0]+["#"+input()+"#" for i in range(h)]+[0]
field[0],field[-1]="#"*(w+2),"#"*(w+2)
l,r,u,d=[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if field[i][j]=="#":continue
    l[i][j]=l[i][j-1]+1
    u[i][j]=u[i-1][j]+1
for i in range(1,h+1)[::-1]:
  for j in range(1,w+1)[::-1]:
    if field[i][j]=="#":continue
    r[i][j]=r[i][j+1]+1
    d[i][j]=d[i+1][j]+1
ans=0
for i in range(h+2):
  for j in range(w+2):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if c>ans:ans=c
print(ans)
### BUGGY CODE ###

INF=float("inf")
def main():
    H,W=map(int, input().split())
    A=[input()for _ in range(H)]
    D=[[0 if A[h][w]=="#" else INF for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(1,W):
            D[h][w]=min(D[h][w],D[h][w-1]+1)
        for w in range(W-2, -1, -1):
            D[h][w]=min(D[h][w],D[h][w+1]+1)
    for w in range(W):
        for h in range(1,H):
            D[h][w]=min(D[h][w],D[h-1][w]+1)
        for h in range(H-2, -1, -1):
            D[h][w]=min(D[h][w],D[h+1][w]+1)
    print(max(d for dd in D for d in dd))

if __name__ == "__main__":
    main()

### FIXED CODE ###

INF=float("inf")
def main():
    H,W=map(int, input().split())
    A=[input()for _ in range(H)]
    D=[[0 if A[h][w]=="#" else INF for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(1,W):
            D[h][w]=min(D[h][w],D[h][w-1]+1)
        for w in range(W-2, -1, -1):
            D[h][w]=min(D[h][w],D[h][w+1]+1)
    for w in range(W):
        for h in range(1,H):
            D[h][w]=min(D[h][w],D[h-1][w]+1)
        for h in range(H-2, -1, -1):
            D[h][w]=min(D[h][w],D[h+1][w]+1)
    print(max(d for dd in D for d in dd))

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

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.6))
    J = min(idx+1,i)
    J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)



### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0:
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

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

n, q = map(int, input().split())
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
count = {i + 1:0 for i in range(n)}
for i in range(q):
    p, x = map(int, input().split())
    count[p] += x
add_list = [1]
while add_list:
    add = add_list.pop(0)
    for i in graph[add]:
        add_list.append(i)
        count[i] += count[add]
for i in range(n):
    print(count[i + 1], end = " ")
print()

### FIXED CODE ###

import sys, collections
input = sys.stdin.readline

n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = collections.deque([1])
while check:
    test = check.popleft()
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()
### BUGGY CODE ###

import re
x = input()

while True:
    pre = len(x)
    x = re.sub('ST', '', x)
    if len(x) == pre:
        break
print(len(x))


### FIXED CODE ###

x = input()
ans = []

for i in x:
    if i == 'S':
        ans.append(i)
    else:
        if len(ans) == 0 or ans[-1] == 'T':
            ans.append(i)
        else:
            ans.pop()
print(len(ans))
### BUGGY CODE ###

s = input()

ans = 0

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

### FIXED CODE ###

s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
cnt = 0
keta = 1
for i in range(len(s)):
    cnt = (cnt + int(s[-(i+1)]) * keta) % 2019
    arr.append(cnt)
    keta =keta * 10 % 2019

for i in range(len(arr)):
    amari[arr[i]] +=1    
    
for i in amari:
    ans = ans + i * (i-1) // 2
print(ans)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
d={i+1:[[],[]] for i in range(n)}
for i in range(m):
     p,y=map(int,input().split())
     idx=bisect.bisect_left(d[p][0],y)
     d[p][0].insert(idx,y)
     d[p][1].insert(idx,i)
tmp2=[0 for i in range(m)]
for k in d.keys():
     x=d[k][1]
     for i in range(len(x)):
          num=str(k).zfill(6)+str(i+1).zfill(6)
          tmp2[x[i]]=num
for x in tmp2:
     print(x)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
d=[]
for i in range(m):
     p,y=map(int,input().split())
     d.append([p,y,i])
d=sorted(d,key=lambda x:(x[0],x[1]))
tmp2=[0 for i in range(m)]
p_=0
cnt=0
for x in d:
     p,y,i=x
     if p_!=p:
          p_=p
          cnt=0
     cnt+=1
     tmp2[i]=str(p).zfill(6)+str(cnt).zfill(6)
for x in tmp2:
     print(x)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    if n==1:
        print(min(u,v))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)
### BUGGY CODE ###

n = int(input())
li1 = list(map(int,input().split()))
m = int(input())
li2 = list(map(int,input().split()))
cnt = 0

for i in li2:
	if i in li1:
		cnt +=1
print(cnt)

### FIXED CODE ###

n = int(input())
S = set(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

sum = 0

for i in T:
    if i in S:
        sum +=1
        
print(sum)
### BUGGY CODE ###

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

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1                
    return ans
for i in k:
    print(search(i))

### FIXED CODE ###

from collections import deque
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    q = deque([])
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
            q.append(d)
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1
                
        
    return ans
for i in k:
    print(search(i))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7

  ans = 0
  for i in range(60):
    count_one = sum(a>>i & 1 for a in A)
    ans += count_one * (N - count_one) * (2 ** i)

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###


from collections import Counter
N = int(input())
X = [i for i in range(1,N+1)]

counts = []
for i in range(N):
    x = X[i]
    d = 2
    tmp = []
    while d**2<=x:
        if x%d==0:
            tmp.append(d)
            x //= d
        else:
            d += 1
    if x != 1:
        tmp.append(x)
    counts.append(Counter(tmp))

memo = []
for i in range(1,N+1):
    tmp = 1
    for v in counts[i-1].values():
        tmp *= (v+1)
    memo.append(i*tmp)

print(sum(memo))

### FIXED CODE ###

N = int(input())
memo = [0]*(N+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        memo[j] += 1

ans = 0
for i in range(1,N+1):
    ans += memo[i]*i

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

n = int(input())
l = []
for i in range(n):
  a = input()
  if a not in l:
    l.append(a)
  else:
    l.remove(a)
print(len(l))

### FIXED CODE ###

from collections import Counter
n = int(input())
l = [int(input()) for _ in range(n)]
c = Counter(l)
ans = 0
for key, value in c.items():
  if value % 2 != 0:
    ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())

def drawal(x):
  if(x <= 5):
    return x
  else:
    def drawal9(y):
      i = 0
      while 9** (i+ 1)<= y:
        i+= 1
      return drawal(y- 9** i)+ 1
    def drawal6(z):
      i = 0
      while 6** (i+ 1)<= z:
        i+= 1
      return drawal(z- 6** i)+ 1
    return min(drawal9(x), drawal6(x))

print(drawal(N))

### FIXED CODE ###

N = int(input())

def drawal(x):
  if(x <= 5):
    return x
  elif(6<= x and x < 9):
    return x- 5
  elif(9<= x and x < 15):
    return x- 8
  else:
    def drawal9(y):
      i = 0
      while 9** (i+ 1)<= y:
        i+= 1
      return drawal(y- 9** i)+ 1
    def drawal6(z):
      i = 0
      while 6** (i+ 1)<= z:
        i+= 1
      return drawal(z- 6** i)+ 1
    return min(drawal9(x), drawal6(x))

print(drawal(N))
### BUGGY CODE ###

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

for i in(range(1,N+1)):
    print(A.count(i))


### FIXED CODE ###

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

from collections import Counter

cnt = Counter(A)

for i in(range(1,N+1)):
    print(cnt[i])
### BUGGY CODE ###

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

s = list(set(a))
m=len(s)
cnt=0
for i in range(m):
  if a.count(s[i])%2==1:
    cnt+=1
print(cnt)

### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for i in range(n)]
s=list(collections.Counter(a).values())
cnt=0
for i in s:
  if i%2!=0:
    cnt+=1
print(cnt)
### BUGGY CODE ###

from collections import defaultdict
e=defaultdict(dict)

n=int(input())
a=[int(i) for i in input().split(" ")]
b=[int(i) for i in input().split(" ")]
c=[int(i) for i in input().split(" ")]

for i in b:
  e[i]=len([j for j in c if j>i])
n=0
for i in a:
  n+=sum([e[j] for j in b if j>i])
print(n)

### FIXED CODE ###

import bisect

n=int(input())
a=[int(i) for i in input().split(" ")]
b=[int(i) for i in input().split(" ")]
c=[int(i) for i in input().split(" ")]

a.sort()
c.sort()
lc=len(c)
print(sum([(lc-bisect.bisect_right(c,j))*(bisect.bisect_left(a,j)) for j in b]))
### BUGGY CODE ###

#!/usr/bin/env python3
#A
import numpy as np
import math
import re

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

c = [list(map(str,input().split()))for i in range(a)]
d = [[0 for j in range(b)]  for i in range(a)]

for i in range(a):#初期のリスト設定
    for j in range(b):
        if c[i][0][j] == '#':
            d[i][j] = 1

def change(save,d):
    for i in save:
        d[i[0]][i[1]] = 1

count = 0
for k in range(a*b):
    count += 1
    save = []
    save2 = []
    for i in range(a):
        for j in range(b):
            if d[i][j] == 1:
                if i != 0:#上があるなら
                    save.append((i-1,j))
                if j != 0:#左があるなら
                    save.append((i,j-1))
                if i != a-1:#下があるなら
                    save.append((i+1,j))
                if j != b-1:#右があるなら
                    save.append((i,j+1))
            else:
                save2.append(1)
    change(save,d)
    if len(save2) == 0:
        break;
print(count-1)

### FIXED CODE ###

#!/usr/bin/env python3
#AGC33 A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
maze = [list(input()) for _ in range(h)]
check = [[True]*w for _ in range(h)]
dx,dy = [0,1,0,-1],[1,0,-1,0]
que = deque()
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            check[i][j] = False
            que.append((j,i))
res = 0
while que:
    que2 = deque(que)
    que = deque()
    flg = False
    while que2:
        x,y = que2.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if check[ny][nx]:
                    check[ny][nx] = False
                    que.append((nx,ny))
                    flg = True
    if flg:
        res += 1
print(res)
### BUGGY CODE ###

N = int(input())
A = map(int, input().split())
A = list(A)
index = 0
sum = 0
j = 0
prev = 0


for i in range(N):
    index = j
    for a in A[index:]:
        j = j + 1
        if a == (i+1):
           sum = sum + 1
           break
    if prev == sum:
        break
    else:
        prev = sum

if sum == 0:
    print('-1')
else:
    print(N-sum)

### FIXED CODE ###

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

num = 1
ans = 0

for i in A:
    if i == num:
        num += 1
    else:
        ans += 1

if num == 1:
    print('-1')
else:
    print(str(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import itertools

import math

from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main():
    k = int(input())

    num_li = list(range(1, k+1))

    ans = 0

    for a,b,c in itertools.product(num_li, repeat=3):
        ans += gcd(a,b,c)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

import math

def main():
    k = int(input())

    ans = 0

    for i in range(1, k+1):
        for j in range(1, k+1):
            for l in range(1, k+1):
                ans += math.gcd(math.gcd(i,j),l)

    print(ans)


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

a,b,c,k = map(int, input().split())
cheak = 10**18
if a == b == c:
    print(0)
    quit()
while k > 0:
    a_new = b+c
    b_new = a+c
    c_new = a+b

    a = a_new
    b = b_new
    c = c_new

    k -= 1
ans = a-b
if ans > cheak:
    print("Unfair")
else:
    print(ans)


### FIXED CODE ###

a,b,c,k = map(int, input().split())
cheak = 10**18
key = a-b
def calc(a,b,c,k):
    if a == b:
        return 0
    elif key < 0:
        if k % 2 == 1:
            return -key
        else:
            return key
    else:
        if k % 2 == 1:
            return -key
        else:
            return key
ans = calc(a,b,c,k)
if ans > cheak:
    print("Unfair")
else:
    print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
flip = False

for i in range(Q):
    Que = input()
    if Que == "1":
        flip = not(flip)
    else:
        Query = Que.split()
        F = Query[1]
        C = Query[2]
        if (F == "1" and not flip) or (F == "2" and flip):
            S = "".join([C, S])
        else:
            S = "".join([S, C])
print(S if not flip else S[::-1])


### FIXED CODE ###

import sys
from collections import deque

S = deque(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline().rstrip())
flip = False

for i in range(Q):
    Que = sys.stdin.readline().rstrip()
    if Que == "1":
        flip = not(flip)
    else:
        Query = Que.split()
        F = Query[1]
        if (F == "1") ^ flip:
            S.appendleft(Query[2])
        else:
            S.append(Query[2])
print("".join(S) if not flip else "".join(S)[::-1])
### BUGGY CODE ###

D,G = map(int, input().split())

num_of_problems, complete_bonus = {},{}

for i in range(1, D+1):
    num_of_problems[i], complete_bonus[i] = map(int, input().split())

import itertools

min_num_of_solve = sum(num_of_problems.values())

for solve_order in itertools.permutations(num_of_problems.keys()): #解く順番を変えて総当り
    score_sum = 0
    num_of_solve = 0

    for j in range(len(solve_order)):
        for k in range(num_of_problems[solve_order[j]]):
            score_sum += solve_order[j]*100
            num_of_solve += 1
            if score_sum >= G:
                break
        
        score_sum += complete_bonus[solve_order[j]]
        if score_sum >= G:
            break
    min_num_of_solve = min(min_num_of_solve, num_of_solve)
    
print(min_num_of_solve)

### FIXED CODE ###

import numpy as np

D, G, *pc = map(int, open(0).read().split())
pc = list(zip(*[iter(pc)]*2))
p, c = np.array([]), np.array([])
for (x,y) in pc:
    p = np.append(p, x)
    c = np.append(c, y)
    
import numpy as np
import math

base_points = np.array([i*100 for i in range(1, D+1)])

ans = []

for i in range(2**D):
    bit_flag = np.array(list(map(int, format(i, '0%db' %D))))
    points = sum(bit_flag * (c + p*base_points))
    solved_num = sum(bit_flag * p)
    
    if points >= G:
        ans.append(solved_num)

    else:
        remained = G - points
        remained_problems = sorted((bit_flag==False) * np.array(range(1, D+1)), reverse=True)
        i = 0

        while True:
            if remained <= 0:
                break
                
            highest_p = remained_problems[i]

            if math.ceil(remained / (highest_p * 100)) <= p[highest_p - 1]:
                solved_num += math.ceil(remained / (highest_p * 100))
                remained -= (math.ceil(remained / (highest_p * 100)) * highest_p * 100)
            else:
                solved_num += p[highest_p - 1]
                remained -= (highest_p * 100 * p[highest_p - 1] + c[highest_p - 1])
                i += 1

        ans.append(solved_num)
        
print(int(min(ans)))
### BUGGY CODE ###

import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = [int(x) for x in input().split()]

x = max(a)
maxc = 0
maxy = 0
for y in a:
    if x == y:
        continue
    if maxc < comb(x, y):
        maxc = comb(x, y)
        maxy = y

print(str(x) + ' ' + str(maxy))


### FIXED CODE ###

import math

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
x = max(a)
a.remove(x)
maxi = 0
mind = x
for i in range(len(a)):
    d = abs((x+1) // 2 - a[i])
    if d < mind:
        maxi = i
        mind = d
print(str(x) + ' ' + str(a[maxi]))
### BUGGY CODE ###

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

rev = 1

for i in range(n):
  cs = input().split()
  #print( cs )
  if( cs[0] == '1' ) :
    rev *= -1
  else:
    cf = cs[1]
    cfs = cs[2]
    if rev == 1 :
      if cf == '1' :
        s =  cfs + s 
      else:
        s =  s + cfs
    else: #rev == -1 :
      if cf == '1' :
        s =  s + cfs
      else:
        s =  cfs + s

if rev == 1 :
 print( s )
else:
 res = ''.join(list(reversed( s )))
 print (res)
  
  

### FIXED CODE ###

from collections import deque

s = input()
n = int(input())
d = deque()
#initial 
for ele in s:
  d.append(ele)
#print(d)

rev = 1

for i in range(n):
  cs = input().split()
  #print( cs )
  if( cs[0] == '1' ) :
    rev *= -1
  else:
    cf = cs[1]
    cfs = cs[2]
    if rev == 1 :
      if cf == '1' :
        #s =  cfs + s 
        d.appendleft(cfs)
      else:
        #s =  s + cfs
        d.append( cfs )
    else: #rev == -1 :
      if cf == '1' :
        #s =  s + cfs
        d.append( cfs )
      else:
        #s =  cfs + s 
        d.appendleft(cfs)

      
if rev == 1 :
 print( ''.join(list(d)) )
else:
 res = ''.join(list(reversed( d )))
 print (res)
### BUGGY CODE ###

import fractions
from itertools import combinations
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
def compromise(x1, x2):
    f = fractions.gcd(x1, x2)
    return f == 1

a, b = map(int, input().split())
cfs = cf(a, b)
club = []
for i in range(len(cfs)):
    if i == 0:
        club.append(cfs[i])
    else:
        flag = True
        for c in club:
            if not compromise(cfs[i], c):
                flag = False
                break
        if flag:
            club.append(cfs[i])
print(len(club))


### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a, b = map(int, input().split())
apri = set(prime_factorize(a))
bpri = set(prime_factorize(b))
print(len(apri & bpri)+1)