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

S = input()
T = input()

def swap(s,c1,c2):
    a = "0"
    s = s.replace(c1,a)
    s = s.replace(c2,c1)
    s = s.replace(a,c2)
    return s

for i in range(len(S)):
    if S[i] == T[i]:
        continue
    else:
        S = swap(S,S[i],T[i])

if S == T:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

S=input()
T=input()

Rs = {}
Rt = {}
for i in range(len(S)):
    if S[i] in Rs.keys():
        if Rs[S[i]] != T[i]:
             print("No")
             exit()
    else:
        Rs[S[i]] = T[i]

    if T[i] in Rt.keys():
        if Rt[T[i]] != S[i]:
            print("No")
            exit()
    else:
        Rt[T[i]] = S[i]
print("Yes")
### BUGGY CODE ###

def factorization(n):
    lst, temp = [], n
    for i in range(2, int(n**0.5//1+1)):
        if temp %i ==0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            lst.append([i, cnt])
    if temp != 1:
        lst.append([temp, 1])
    if lst == []:
        lst.append([n, 1])
    return lst

mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

soinsu = {}
factrized_a = []
for i in range(n):
    lst = factorization(a[i])
    factrized_a.append(lst)
    for sosu, josu in lst:
        try:
            before_josu = soinsu[sosu]
        except KeyError:
            before_josu = 0
        soinsu[sosu] = max(before_josu, josu)

ans = 0
for i in range(n):
    lst = factrized_a[i]
    copied_soinsu = soinsu.copy()
    for sosu, josu in lst:
        copied_soinsu[sosu] -= josu
    bi = 1
    for sosu, josu in copied_soinsu.items():
        bi = bi * (sosu**josu) % mod
    ans = (ans + bi) % mod

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

mod = 10**9 + 7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

num_lcm = lcm(*a) % mod
ans = 0
for i in range(n):
    ans = (ans + num_lcm * a_[i] % mod) % mod

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

from fractions import gcd

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

def lcm(x, y):
    return (x * y) // gcd(x, y)
l = a[0]
for i in range(n):
    if i == 0:
        continue
    l = lcm(l, a[i])
sum = 0
for i in range(n):
    sum += l // a[i]
    sum %= 1000000007
print(sum)


### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

def lcm(x, y):
    return (x * y) // gcd(x, y)
def main():
    n = int(sys.stdin.readline())
    a = list(map(int,input().split()))
    
    l = a[0]
    for i in range(n):
        l = lcm(l, a[i])
    sum = 0
    for i in range(n):
        sum += l // a[i]
    print(sum % 1000000007)
main()
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]


dp = [1] * n

for i in range(n):
    for j in range(0, i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 100), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)
### BUGGY CODE ###

# # https://atcoder.jp/contests/dp/tasks/dp_d
# def main():

#     N, W = map(int, input().split())
#     wv = [list(map(int, input().split())) for _ in range(N)]
#     w = [wv[0] for _ in range(N)]
#     v = [wv[1] for _ in range(N)]
#     # dp_v[i][limited_w]:
#     # 重さ制限がlimited_wで、０からi-1番目までの品物を選んだときの価値の最大値
#     dp_v = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

#     for i in range(N):
#         for weight in range(W + 1):
#             # 重さ制限weightのもとで品物iを選べるなら選び、価値を更新
#             if weight >= w[i]:
#                 dp_v[i + 1][weight] = max(dp_v[i][weight - w[i]] + v[i], dp_v[i][weight])
#             else:
#                 dp_v[i + 1][weight] = max(dp_v[i + 1][weight], dp_v[i][weight])


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

def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    vdp = [[0 for _ in range(W+1)] for _ in range(N+1)]

    for i in range(N):
        for weight in range(W+1):
            # 品物iを（選べるなら）選ぶ
            if weight >= w[i]:
                vdp[i+1][weight] = max(vdp[i][weight - w[i]] + v[i],
                                       vdp[i][weight])
            # 品物iを選ばない
            vdp[i+1][weight] = max(vdp[i+1][weight], vdp[i][weight])
    print(vdp[N][W])


if __name__ == '__main__':
    main()


### FIXED CODE ###

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])
### BUGGY CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))

min_dist = abs(X - min(L))

ans = 1

for d in range(min_dist, 0, -1):
    b = all((x - X) % d == 0 for x in L)
    if b:
        print(d)
        break


### FIXED CODE ###

import math
from functools import reduce

def gcd(ns):
    return reduce(math.gcd, ns)

N, X = map(int, input().split())
L = list(map(int, input().split()))

diff = [abs(x - X) for x in L]

if len(diff) == 1:
    print(diff[0])
else:
    print(gcd(diff))
### BUGGY CODE ###

N = int(input())
X = list(map(int, list(input())))

B = sum(X)

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b*A[-i-1]
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
#print(x)

for i in range(N):
  call = 0
  if X[i] == 0:
    y = (x + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)

### FIXED CODE ###

N = int(input())
X = input()
B = X.count('1')
#print(B, 'B')

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b * int(A[-i-1])
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
x1 = x % (B+1)
if B > 1:
  x2 = x % (B-1)
#print('x', len(X))

for i in range(N):
  call = 0
  if X[i] == '0':
    y = (x1 + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x2 - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)
### BUGGY CODE ###

X=int(input())
max=1
for j in range(2,X):
    for i in range(1,X):
        if i**j<=X and i**j>max:
            max=i**j
print(max)

### FIXED CODE ###

import numpy as np
X=int(input())
Y=int(np.sqrt(X))+1
max=1
for j in range(2,Y+1):
    for i in range(1,Y+1):
        if i**j<=X and i**j>max:
            max=i**j
print(max)
### BUGGY CODE ###

S = str(input())
Q = int(input())

qs = [input().split() for i in range(Q)]

for q in qs:
    if q[0] == '1':
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S = S + q[2]

print(S)

### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())

d = deque([S[i] for i in range(len(S))])
#print(d)

flg = 0

for i in range(Q):
    query = input()
    if query[0] == '1':
        flg = flg%2 + 1
    else:
        t, f, c = query.split()
        if f == '1':
            if flg % 2 == 0:
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if flg % 2 == 0:
                d.append(c)
            else:
                d.appendleft(c)
if flg % 2 == 0:
    print(''.join(list(d)))
else:
    tmp = ''.join(list(d))
    print(tmp[::-1])
### BUGGY CODE ###

N=int(input())
S=[]
for i in range(N):
    S.append(str(input()))

S_set=set(S)

c_max=0
ans=[]
for i in S_set:
    c= S.count(i)
    if c > c_max:
        c_max = c
        ans=[]
        ans.append(i)
    elif c == c_max:
        ans.append(i)

ans=sorted(ans)
for j in ans:
    print(j)
    


        
        
    




### FIXED CODE ###

import collections

N=int(input())
S=[]
for i in range(N):
    S.append(str(input()))

c = collections.Counter(S)

ans = c.most_common()[0][1]

a=sorted([i[0] for i in c.items() if i[1] == ans])
            
for i in a:
    print(i)
### BUGGY CODE ###

def solve():
    H, N = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    dp = [float('inf')]*(H+10**4)
    dp[0] = 0
    for h in range(1,H+10**4):
        for i in range(N):
            if A[i][0]<=h:
                dp[h] = min(dp[h],dp[h-A[i][0]]+A[i][1])
    ans = min(dp[H:])
    return ans
print(solve())

### FIXED CODE ###

#動的計画法
import numpy as np
H, N = map(int, input().split())

A=np.empty(N,dtype=int)
B=np.empty(N,dtype=int)
for i in range(N):
    A[i],B[i]=map(int,list(input().split(" ")))

DP=np.empty(H+1,dtype=int)

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  t = hp-A
  t[t<0] = 0
  min_power = min(DP[t]+B)
  return magic+min_power

#DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')
### BUGGY CODE ###

import copy
import collections

N = int(input())

l = list(map(int,input().split()))
lc = copy.copy(l)
for i in range(N):
  l.pop(i)
  c = collections.Counter(l)
  cnt = 0
  for v in c.values():
    cnt+=v*(v-1)//2
  l = copy.copy(lc)
  print(cnt)

### FIXED CODE ###

import collections
N = int(input())
l = list(map(int,input().split()))
c = collections.Counter(l)
cnt = 0
for v in c.values():
    cnt += v*(v-1)//2
    
for i in range(N):
  print(cnt - c[l[i]] + 1)
### BUGGY CODE ###

from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split()))

    A = [0] + A
    b = A[:]
    n = N // 2 + 1
    m = sum(b[n:])
    for i in range(n - 1, 0, -1):
        sum_ = sum([v for j, v in enumerate(b) if not j % i])
        if A[i] != sum_ % 2:
            b[i] = (b[i] + 1) % 2
        m += b[i]

    print(m)
    if m:
        print(*[i for i, v in enumerate(b) if v])


main()


### FIXED CODE ###

from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split()))

    A = [0] + A
    b = A[:]
    n = N // 2 + 1
    m = sum(b[n:])
    for i in range(n - 1, 0, -1):
        sum_ = sum([b[j] for j in range(i, N + 1, i)])
        if A[i] != sum_ % 2:
            b[i] = (b[i] + 1) % 2
        m += b[i]

    print(m)
    if m:
        print(*[i for i, v in enumerate(b) if v])


main()
### BUGGY CODE ###

import fractions
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = 1
c = 0
key = 1
key1 = 1
l = []
while key == 1:
    if a[0] % b == 0:
        b *= 2
        c += 1
    else:
        b //= 2
        c -= 0
        key = 0
for i in range(n):
    if a[i] % b == 0:
        if (a[i]//b) % 2 == 0:
            key1 = 0
            break
        else:
            l.append(a[i]//b)
    else:
        key1 = 0
        break
if key1 == 0 or c == 0:
    print(0)
else:
    d = l[0]
    for i in range(1,n):
        d = d* l[i]// fractions.gcd(d,l[i])
    d = d*b//2
    if (m//d)%2 == 0:
        print((m//d)//2)
    else:
        print((m//d)//2+1)

### FIXED CODE ###

import fractions
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = 1
c = 0
key = 1
key1 = 1
l = []
while key == 1:
    if a[0] % b == 0:
        b *= 2
        c += 1
    else:
        b //= 2
        c -= 0
        key = 0
for i in range(n):
    if a[i] % b == 0:
        if (a[i]//b) % 2 == 0:
            key1 = 0
            break
        else:
            l.append(a[i]//b)
    else:
        key1 = 0
        break
if key1 == 0 or c == 0:
    print(0)
else:
    d = l[0]
    for i in range(1,n):
        d = d*l[i]// fractions.gcd(d,l[i])
        if m < d:
            break
    d = d*b//2
    if (m//d)%2 == 0:
        print((m//d)//2)
    else:
        print((m//d)//2+1)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
P = np.array(list(map(int, input().split())))
M = 0
for i in range(n - k + 1):
    M = max(M,P[i:i + k].sum())

ans = (M + k) / 2
print(ans)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
P = np.array([0] + list(map(int, input().split())))
C = np.cumsum(P)
#print(C)
M = 0
for i in range(n - k + 1):
    #print(C[i + k],C[i])
    M = max(M, C[i + k] - C[i])

ans = (M + k) / 2
print(ans)
### BUGGY CODE ###

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

order = []

for i in range(N):
    order.append(A.index(i+1)+1)
    
print(' '.join(map(str, order)))


### FIXED CODE ###

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

student = [0] * N
for i in range(N):
  student[A[i]-1] = i + 1
  
print(' '.join(map(str, student)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())

def warshall_floyd(d,n):
    for i in range(n):
        d[i*n+i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i*n+j] = min(d[i*n+j],d[i*n+k] + d[k*n+j])
    return d

def main():
    n,w,l = inpm()
    d = [10**20 for _ in range(n**2)]
    for _ in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x*n+y] = z
        d[y*n+x] = z
    d = warshall_floyd(d,n)
    d = tuple(d)
    e = [10**20 for _ in range(n**2)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i*n+j] <= l:
                e[i*n+j] = 1
                e[j*n+i] = 1
    q = inp()
    e = warshall_floyd(e,n)
    e = tuple(e)
    for _ in range(q):
        s,t = inpm()
        s -= 1
        t -= 1
        ans = e[s*n+t]
        if ans == 10**20:
            print(-1)
            continue
        print(ans-1)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline
 
def main():
    n,w,l = map(int,input().split())
    d = [[10**15 for _ in range(n)] for _ in range(n)]
    for _ in range(w):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0
    d = floyd_warshall(d)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    for i in range(n):
        G[i][i] = 0
    G = floyd_warshall(G)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        ans = G[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(int(ans)-1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from decimal import *
n, k = map(int,input().split())

ans = Decimal(0)
for i in range(1,n+1):
    count = 0
    if i < k-1:
        while i < k:
            i *= 2
            count += 1
    ans += Decimal(1/n) * Decimal((1/2)**count)
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(1,n+1):
    count = 0
    if i < k:
        while i < k:
            i *= 2
            count += 1
    ans += 1/n * (1/2)**count
print(ans)
### BUGGY CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
q = int(input())
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        dic[s[a]].remove(a)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)


### FIXED CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)
### BUGGY CODE ###

import sys
from collections import deque
from collections import  Counter
import statistics
import math

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, len(s)):
        li.append(s[i:j+1])
li = list(set(li))
li.sort()
print(li[k-1])

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, i+k+1):
        li.append(s[i:j+1])
li = list(set(li))
li.sort()
print(li[k-1])
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M, S, T, *UVAB = map(int, open(0).read().split())
if N < 2 or M < 1:
    raise ValueError()

A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

### FIXED CODE ###

from heapq import heappush, heappop

INF = float("inf")
def dijkstra(E, r):
    D = [INF] * len(E)
    D[r] = 0

    Q = [(0, r)]
    while Q:
        dist, cur = heappop(Q)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, (cand, nxt))

    return D


N, M, S, T, *UVAB = map(int, open(0).read().split())
A = [[] for _ in range(N + 1)]
B = [[] for _ in range(N + 1)]
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A[u].append((v, a))
    A[v].append((u, a))
    B[u].append((v, b))
    B[v].append((u, b))

A = dijkstra(A, S)
B = dijkstra(B, T)

init = 10 ** 15

ans = []
cur = INF
for a, b in zip(reversed(A[1:]), reversed(B[1:])):
    cur = min(cur, a + b)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)
### BUGGY CODE ###

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

if a.count(0) > 0:
  print(0)
  exit()
  
ans = a[0]
for i in range(1,n):
  ans *= a[i]
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

if 0 in a:
  print(0)
  exit()

ans = 1
for i in a:
  ans *= i
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[set() for j in range(N)] for i in range(3)]
for u,v in UV:
    es[0][u].add(v)

nex = {}
for i in range(2):
    for j in range(N):
        if hash(tuple(es[i][j])) in nex:
            es[i+1][j] = nex[hash(tuple(es[i][j]))]
            continue
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]
        nex[hash(tuple(es[i][j]))] = es[i+1][j]

INF = float('inf')
dist = [INF]*N
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    for to in es[2][v]:
        if dist[to] != INF: continue
        dist[to] = dist[v]+1
        if to == T:
            print(dist[to])
            exit()
        q.append(to)

print(-1)

### FIXED CODE ###

from collections import deque
import sys
inputs = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,inputs().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[] for i in range(3*N)]
for u,v in UV:
    es[u].append(v+N)
    es[u+N].append(v+2*N)
    es[u+2*N].append(v)

q = deque([S])
INF = float('inf')
dist = [INF] * (3*N)
dist[S] = 0

while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] != INF: continue
        dist[to] = dist[v] + 1
        if to==T:
            print(dist[to] // 3)
            exit()
        q.append(to)
print(-1)
### BUGGY CODE ###

n = int(input())
a = sorted([int(i) for i in input().split()])
for i in set(a):
  if a.count(i)== 1:
    a.remove(i)
if len(a) <= 3:
  print(0)
else:
  if a.count(max(a)) == 3:
    print(a[-1]*a[-4])
  else:
    print(a[-1]*a[-3])
  
    

### FIXED CODE ###

import collections
N = int(input())
A = collections.Counter(list(map(int, input().split())))
seihou = []
tyouhou = []
ans = 0

for i in A.keys():
    if A[i] >= 2:
        tyouhou.append(i)
    if A[i] >= 4:
        seihou.append(i)

if len(seihou) >= 1:
    ans = max(seihou)**2

if len(tyouhou) >= 2:
    c = max(tyouhou)
    tyouhou.remove(c)
    ans = max(ans, c*max(tyouhou))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = input()
A = list(map(int,input().split()))
flag = False
while 1:
    a = A[0]
    A = A[1:]
    if a in A:
        flag = True
        break
    if len(A) == 0:
        break


if flag:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
A = set(A)
if N == len(A):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[[s=='.' for s in list(input())] for _ in range(h)]
#h,w=1000,1000
#a=[[True]*w]*h
mod=10**9+7
dp=np.zeros((h,w),np.int64)

novisited=np.array(a)
novisited[0,:]=False
novisited[:,0]=False
memo=np.zeros((h,w),np.int64)
for i in range(h):
      if a[i][0]:
            memo[i,0]=1
      else:
            break
for i in range(w):
      if a[0][i]:
            memo[0,i]=1
      else:
            break
def dp(i,j):
      if not novisited[i][j]:
            return memo[i,j]
      else:
            memo[i,j]=(dp(i-1,j)+dp(i,j-1))%mod
            novisited[i][j]=False
            return memo[i,j]

print(dp(h-1,w-1))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)