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

import sys
from collections import defaultdict

def input():
    return sys.stdin.readline().strip()

def recordnum(a,b):
    if not (0 < a < H-1 and 0 < b < W-1):
        return 

    res = M[(a,b)]
    for i,j in vector:
        res += M[(a+i,b+j)]
    num[res] += 1
    return

def dfs(a,b,color):

    if visited[(a,b)]:
        return

    recordnum(a,b)
    visited[(a,b)] = True

    if color == "b":
        for i,j in vector:
            x = a+i
            y = b+j
            if 0 < x < H-1 and 0 < y < W-1 and M[(x,y)] == 0:
                dfs(x,y,"w")
    return

    

H,W,N = map(int,input().split())

M = defaultdict(int)
visited = defaultdict(int)
ab = []

for _ in range(N):
    a,b = map(int,input().split())
    ab.append((a-1,b-1))
    M[(a-1,b-1)] = 1


vector = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)]
num = [0]*10

for a,b in ab:
    dfs(a,b,"b")

num[0] = (H-2)*(W-2) - sum(num)

for i in num:
    print(i)

### FIXED CODE ###

"""
参考(神様)
https://atcoder.jp/contests/abc045/submissions/6046010
"""

###かぶるやつを考える.例えばあるマスのかぶり値が9だとしたら,
###周囲はすべて黒->j=9のが1つとカウントしてよい,他の値についても同様.

import sys
from collections import defaultdict,Counter

def input():
    return sys.stdin.readline().strip()

H,W,N = map(int,input().split())

covered = defaultdict(int)
vector = [(0,0),(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)]

for _ in range(N):
    a,b = map(int,input().split())

    for i,j in vector:
        x = a+i-1
        y = b+j-1

        if 0 < x < H-1 and 0 < y < W-1:
            covered[(x,y)] += 1

num = Counter(covered.values())
##print(num)
num[0] = (H-2)*(W-2)-sum(num.values())

for i in range(10):
    print(num[i])
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

primes = [0]*(m+1)
primes[1] = 1
for i in range(2, m+1):
    if primes[i] == 0:
        for j in range(1, m//i+1):
            primes[i*j] = i

count = [0]*(m+1)
for x in a:
    y = x
    while primes[y] != y:
        count[primes[y]] += 1
        p = primes[y]
        while y % p == 0:
            y //= p
    if primes[y] >= 2:
        count[primes[y]] += 1

if max(count) <= 1:
    print("pairwise coprime")
else:
    g = 0
    for x in a:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

primes = [0]*(m+1)
primes[1] = 1
for i in range(2, m+1):
    if primes[i] == 0:
        for j in range(1, m//i+1):
            primes[i*j] = i

count = [0]*(m+1)
for x in a:
    y = x
    while primes[y] != y:
        count[primes[y]] += 1
        p = primes[y]
        while y % p == 0:
            y //= p
    if primes[y] >= 2:
        count[primes[y]] += 1

if max(count) <= 1:
    print("pairwise coprime")
else:
    g = 0
    for x in a:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
### BUGGY CODE ###

# coding: utf-8

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

if X == 1:
    print('0 -1')
else:
    for i in range(1, len(S)):
        tmp = S[i]
        for A in range(S[i-1], S[i+1]):
            B = A - tmp
            if A**5 - B**5 == X:
                print(str(A) + ' ' + str(B))
                break
        else:
            continue
        break

### FIXED CODE ###

# coding: utf-8

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

for i in range(len(S)):
    tmp = S[i]
    for A in range(-1000, 1001):
        B = A - tmp
        if A**5 - B**5 == X:
            print(str(A) + ' ' + str(B))
            break
    else:
        continue
    break
### BUGGY CODE ###

from collections import defaultdict as dd
n, m = map(int, input().split())
H = [0] + list(map(int, input().split()))
#print(H)

dic_road = dd(set)
for i in range(m):
    a, b = map(int, input().split())
    dic_road[a].add(b)
    dic_road[b].add(a)

counter = 0
#highest = set()
not_highest = set()
for tenobo in range(1, n+1):
    if tenobo in not_highest:
        continue
    for compare in list(dic_road[tenobo]):
        if H[tenobo] <= H[compare]:
            break
    else:
        counter += 1
        not_highest = not_highest | dic_road[tenobo]

print(counter)

### FIXED CODE ###

from collections import defaultdict as dd

n, m = map(int, input().split())
H = [0] + list(map(int, input().split()))
# print(H)

road = set()
for i in range(m):
    a, b = map(int, input().split())
    road.add((a, b))

counter = 0
not_highest = set()
for a, b in road:
    if H[a] == H[b]:
        not_highest.add(a)
        not_highest.add(b)
    elif H[a] > H[b]:
        not_highest.add(b)
    elif H[b] > H[a]:
        not_highest.add(a)

print(n - len(not_highest))
### BUGGY CODE ###

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

h = int(m/n)+1
for a in range(h, 0, -1):
    q = m-a*n
    if q<0:
        continue
    elif q == 0:
        print(a)
        break
    else:
        if q%a == 0 and m%a == 0:
            print(a)
            break

### FIXED CODE ###

import sys

def make_divisors(num):
    divisors = []
    for i in range(1, int(num**0.5)+1):
        if num%i == 0:
            divisors.append(i)
            if num//i != i:
                divisors.append(num//i)
    divisors.sort()
    return divisors

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

divisors = make_divisors(m)

for i in range(1, len(divisors)+1):
    if divisors[i*-1] * n <= m:
        print(divisors[i*-1])
        sys.exit()
### BUGGY CODE ###

def d170(n,a):
    count=0
    dp=[0 for i in range(max(a)+1)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,max(a)+1,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

### FIXED CODE ###

def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    H, W = LI()
    hs = [[-1] for _ in range(H)]
    ws = [[-1] for _ in range(W)]
    for h in range(H):
        s = SI()
        for w, ss in enumerate(s):
            if ss == '#':
                hs[h].append(w)
                ws[w].append(h)
    for h in range(H):
        hs[h].append(W)
    for w in range(W):
        ws[w].append(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            i = bisect_left(hs[h], w)
            j = bisect_left(ws[w], h)
            ans = max(ans, hs[h][i] - hs[h][i - 1] + ws[w][j] - ws[w][j - 1] - 3)
    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
import numpy

def main():
    H, W = LI()
    S = []
    for i in range(H):
        S.append(list(SI()))
    S = (numpy.array(S) == '.')
    L = numpy.zeros((H, W), dtype=int)
    R = numpy.zeros((H, W), dtype=int)
    T = numpy.zeros((H, W), dtype=int)
    B = numpy.zeros((H, W), dtype=int)
    for i in range(H):
        L[i] = (L[i - 1] + 1) * S[i]
        R[-1 - i] = (R[-i] + 1) * S[-1 - i]
    for i in range(W):
        T[:, i] = (T[:, i - 1] + 1) * S[:, i]
        B[:, -1 - i] = (B[:, -i] + 1) * S[:, -1 - i]
    ans = numpy.max(L + R + T + B) - 3
    return ans

print(main())
### BUGGY CODE ###

def main():
    import sys
    N = int(input())
    A = []
    for i in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        row = [r - 1 for r in row]
        A.append(row)

    counter = [0] * (N + 1)
    finish = 0

    ans = 0
    s = set(range(N))
    done_s = set()
    while finish < N * (N - 1) // 2:
        checked = set()
        ans += 1

        exit_flg = True
        for n in s - done_s:
            # ある日程ですでにnは戦っている
            if n in checked:
                continue

            # nの対戦は終了
            if counter[n] == N - 1:
                continue

            checked.add(n)

            n_match = A[n][counter[n]]  # nの対戦相手
            n_match_match = A[n_match][counter[n_match]]  # nの対戦相手の対戦相手

            # nの対戦相手はある日の試合をすでに終えている
            if n_match in checked:
                continue

            # マッチング成立
            if n == n_match_match:
                exit_flg = False

                checked.add(n_match)

                finish += 1
                counter[n] += 1
                counter[n_match] += 1

                if counter[n] == N - 1:
                    done_s.add(n)
                if counter[n_match] == N - 1:
                    done_s.add(n_match)

        # 一つも組み合わせられなかった
        if exit_flg:
            print(-1)
            exit()

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())

# 初期化
G = [None] * (10 ** 6 + 1)  # グラフ
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        
# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)
### BUGGY CODE ###

N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n+1)]
    for i in range(n//2):
        p=(i+1)**2
        if p>n:
            for j in range(i**2,n+1):
                A[j]=i
            break
        else:
            for j in range(i**2,p):
                A[j]=i
    return A
A=sq(N)
for n in range(1,N+1):
    c=0
    for x in range(1,A[n]):
        p=n-x**2
        if p<0:
            break
        else:
            for y in range(1,A[p]+1):
                q=p-y**2-x*y
                if q<0:
                    break
                else:
                    for z in range(1,A[q]+1):
                        if q==z**2+y*z+z*x:
                            c=c+1
    print(c)

### FIXED CODE ###

N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n+1)]
    for i in range(n//2):
        p=(i+1)**2
        if p>n:
            for j in range(i**2,n+1):
                A[j]=i
            break
        else:
            for j in range(i**2,p):
                A[j]=i
    return A
A=sq(N)
a=A[N]
L=[0 for j in range(N+1)]
for x in range(1,a+1):
    for y in range(1,a+1):
        for z in range(1,a+1):
            p=x**2+y**2+z**2+x*y+y*z+z*x
            if p<=N:
                L[p]=L[p]+1
            else:
                break
for i in range(1,N+1):
    print(L[i])
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i in range(w)] for i in range(h)]

q=deque()
#i,j,ans
q.append([0,0,0])

while(len(q)>0):
    i,j,ans=q.popleft()

    if(s[i][j]=='#'):
        ans+=1

    if(dp[i][j]>ans):
        dp[i][j]=ans

    if(j<w-1):
        q.append([i,j+1,ans])

    if(i<h-1):
        q.append([i+1,j,ans])

print(dp[h-1][w-1])



### FIXED CODE ###

h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i in range(w)] for i in range(h)]


if(s[0][0]=='#'):
    dp[0][0]=1
else:
    dp[0][0]=0

for i in range(h):
    for j in range(w):

        if(s[i][j-1] != s[i][j]):
            left = dp[i][j-1]+1
        else:
            left = dp[i][j-1]

        if(s[i-1][j] != s[i][j]):
            top = dp[i-1][j]+1
        else:
            top = dp[i-1][j]

        dp[i][j] = min(dp[i][j],left,top)

print((dp[h-1][w-1]+1)//2)
### BUGGY CODE ###

n=int(input())
dist=[[-1 for i in range(n)] for i in range(n)]
for i in range(n-1):
  dist[i][i]=0
  a,b,c=map(int,input().split())
  dist[a-1][b-1]=c
  dist[b-1][a-1]=c

Q,K=map(int,input().split())
distFromK=[-1 for i in range(n)]

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  num=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[num]==-1:
    distFromK[num]=d
  else:
    distFromK[num]=min(d,distFromK[num])
  targets=dist[num]
  for i in range(len(targets)):
    if i==parent or i==num:
      continue
    if targets[i]==-1:
      continue
    stack.append([i,targets[i]+d,num])
    
for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])


### FIXED CODE ###

n=int(input())
dist=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  dist[a-1].append([b-1,c])
  dist[b-1].append([a-1,c])  

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

INF=10**9+1
distFromK=[-1 for i in range(n)]

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[v]==-1:
    distFromK[v]=d
  else:
    distFromK[v]=min(distFromK[v],d)
  targets=dist[v]
  for child in targets:
    if child[0]==parent or child[0]==v:
      continue
    stack.append([child[0],d+child[1],v])

for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])
### BUGGY CODE ###

N = int(input())
S = str(input())
slist = list(S)
MIN=N
for i in range(N):
    change=0
    change+=slist[:i].count("W")
    change+=slist[i+1:].count("E")
    MIN=min(MIN,change)
print(MIN)

### FIXED CODE ###

#C
N = int(input())
S = list(str(input()))
look_east = [0]
E = 0
W = 0
for s in S:
    if s == "E":
        look_east.append(look_east[-1]+1)
        E+=1
    else:
        look_east.append(look_east[-1])
        W+=1

ans = N
for i in range(N):
    we = look_east[i]
    if S[i] == "E":
        change = i-we + E-(we+1)
    else:
        change = i-we + E-(we)
        
    ans = min(ans,change)
        
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def ans() :
    n, m  = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    for i in range(m):
        a[-1] = a[-1] >> 1
        a.sort()

    print(sum(a))

if __name__ == '__main__':
    ans()

### FIXED CODE ###

# -*- coding: utf-8 -*-

import heapq

def ans() :
    n, m  = map(int, input().split())
    aa = map(int, input().split())
    a = []
    for i in aa:
        heapq.heappush(a, int(i) * (-1))

    for i in range(m):
        head = heapq.heappop(a)
        head = (-1) * (-head // 2)
        heapq.heappush(a, head)

    print(-sum(a))

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

import math
a,b,c,d,e,f = map(int,input().split())
max_sugar = f*e*100/(100+e)
box = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    if water > f:
      break
    sugar_range = math.ceil(max_sugar/c)
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        if sugar > max_sugar:
          break
        amount = water + sugar
        if amount == 0:
          break
        conc = 100*sugar / amount
        if amount <= f and conc <= e*100/(100+e):
          box[conc] = [amount,sugar]
new_box = sorted(box.items(),reverse = True)
print(str(new_box[0][1][0]) + " " +str(new_box[0][1][1]))

### FIXED CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_nodo = e/(e+100)
answer = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    max_sugar = water*e/100
    sugar_range = int(math.ceil(max_sugar/c))
    if water >= f:
      break
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        total = water + sugar
        nodo = sugar / total
        if total > f:
          break
        if sugar > max_sugar:
          break
        answer[nodo] = [total,sugar]
ans = max(answer.items(),key = lambda x:x[0])[1]

#print(answer)
print(str(ans[0]) + " " + str(ans[1]))
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
read=sys.stdin.read
N,M,*alst=map(int,read().split())
mod=10**9+7
dp = [1, 1 if 1 not in alst else 0]


@lru_cache(maxsize=None)
def a(n):
  if n==0:
    return dp[0]
  elif n==1:
    return dp[1]
  else:
    if n not in alst:
      return (a(n-2)+a(n-1))%mod
    else:
      return 0


print(a(N))


### FIXED CODE ###

def main():
  N,M,*alst=map(int, open(0).read().split())
  alst=set(alst)
  mod=10**9+7
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if 1 not in alst else 0]
  for i in range(2, N+1):
    if i not in alst:
      dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
main()
### BUGGY CODE ###

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

ans = 0
den = int(1e9 + 7)
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        ans = (ans + ((a[i] % den) * (a[j] % den) % den)) % den

print(ans)

### FIXED CODE ###

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

ans = 0
den = int(1e9 + 7)
sum_a = [0 for i in range(len(a))]
sum_a[-1] = a[-1]
for i in range(len(a) - 1, 1, -1):
    sum_a[i - 1] = sum_a[i] + a[i - 1]
for i in range(len(a) - 1):
    ans = (ans + a[i] * sum_a[i + 1]) % den

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

import sys
import itertools


x = int(input())
for a in itertools.count():
    for b in itertools.count(a):
        a5b5 = a**5 + b**5
        if a5b5 == x:
            print(a, -b)
            sys.exit(0)
        if x < a5b5:
            break

### FIXED CODE ###

import sys
import itertools


x = int(input())
for b in itertools.count():
    for a in itertools.count(b):
        a5b5 = a**5 + b**5
        if a5b5 == x:
            print(a, -b)
            sys.exit(0)
        a5b5 = a**5 - b**5
        if a5b5 == x:
            print(a, b)
            sys.exit(0)
        if x < a5b5:
            break
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# まずは桁数を増やす→数字の大きい順に並べる
N, M = lr()
A = lr()
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = [(matches[a], a) for a in A]
A.sort(key = lambda x: x[1], reverse=True)
A.sort(key = lambda x: x[0])
top_match = A[0][0]
dp = [None] * (N+1)
dp[0] = []
used = set()
for match, num in A:
    if match in used:
        continue
    used.add(match)
    for x in range(N+1):
        if x - match < 0:
            continue
        if dp[x] == None and dp[x-match] != None:
            dp[x] = dp[x-match] + [num]
        elif dp[x] != None and dp[x-match] != None:
            if len(dp[x-match]) >= len(dp[x]):
                dp[x] = dp[x-match] + [num]
            elif len(dp[x-match]) >= 1 and len(dp[x-match]) == len(dp[x]) - 1:
                y = list(map(str, dp[x][::-1])); y.sort(reverse=True)
                z = [str(num)] + list(map(str, dp[x-match][::-1])); z.sort(reverse=True)
                y = int(''.join(y))
                z = int(''.join(z))
                if z > y:
                    dp[x] = dp[x-match] + [num]

X = dp[N]
X.sort(reverse=True)
answer = ''.join(list(map(str, X)))
print(answer)
# 37


### FIXED CODE ###

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

dp = [0] * N + [-1] * 9
for i in range(1, N+1):
    dp[i] = max(dp[i-int('0255456376'[a])] * 10 + a for a in A)

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

n,*a=map(int,open(0).read().split())
b=[]
for i,j in zip(a[::2],a[1::2]):
    b=[j]+b+[i]
if n%2:
    b=[a[-1]]+b[::-1]
print(*b)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
b=a[1::2][::-1]+a[::2]
if n%2:
    b=[a.pop(-1)]+a[::2][::-1]+a[1::2]
print(*b)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
  ans = ans*A[i]
if ans > 10**18:
  print('-1')
  exit()
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  if A[i]==0:
    print('0')
    exit()
ans = 1
for i in range(N):
  ans = ans*A[i]
  if ans > 10**18:
    print('-1')
    exit()
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.insert(0,0)
hist = [0 for _ in range(N+1)]
a = 1
cnt = 0
hist[a] = 1
while True:
    cnt += 1
    a = A[a]
    if hist[a]==1:
        cnt = -1
        break
    if a==2:
        break
print(cnt)

### FIXED CODE ###

N = int(input())
G = {}
for i in range(1,N+1):
    a = int(input())
    G[i] = a
cur = 1
hist = [0 for _ in range(N+1)]
hist[cur] = 1
cnt = 0
while True:
    cur = G[cur]
    cnt += 1
    if cur == 2:break
    if hist[cur]==1:break
    hist[cur]=1
if cur==2:
    print(cnt)
else:
    print(-1)