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

import sys
from queue import Queue


def main():
    input = sys.stdin.readline
    N = int(input())
    tree = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        tree[u-1].append([v-1, w])
        tree[v-1].append([u-1, w])

    color = [None] * N
    v_que = Queue()
    v_que.put(0)
    
    c = True
    c_que = Queue()
    c_que.put(c)

    while not v_que.empty():
        v = v_que.get()
        c = c_que.get()
        if color[v] is not None:
            continue
        color[v] = c
        for e in tree[v]:
            v_que.put(e[0])
            c_que.put(c if e[1] % 2 == 0 else not c)

    for c in color:
        print(int(c))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from queue import Queue


def main():
    input = sys.stdin.readline
    N = int(input())
    tree = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        tree[u-1].append([v-1, w])
        tree[v-1].append([u-1, w])

    color = [None] * N
    v_que = Queue()
    v_que.put(0)
    
    c = True
    c_que = Queue()
    c_que.put(c)

    while not v_que.empty():
        v = v_que.get()
        c = c_que.get()
        if color[v] is not None:
            continue
        color[v] = c
        for e in tree[v]:
            v_que.put(e[0])
            c_que.put(c if e[1] % 2 == 0 else not c)

    for c in color:
        print(int(c))


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

import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, s, edges):
    hq = [(0, s)]
    cost = [float('inf')] * n
    cost[s] = 0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edges[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[-1]

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    circles = []
    circles.append([xs, ys, 0])
    for _ in range(n):
        circles.append(list(map(int, input().split())))
    circles.append([xt, yt, 0])
    edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
        for j in range(i + 1, n + 2):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            d = (dx ** 2 + dy ** 2) ** 0.5
            r = circles[i][2] + circles[j][2]
            edges[i].append([max(0, d - r), j])
            edges[j].append([max(0, d - r), i])

    ans = dijkstra(n + 2, 0, edges)
    print(ans)
    
main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, s, edges):
    hq = [(0, s)]
    cost = [float('inf')] * n
    cost[s] = 0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edges[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[-1]

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    circles = []
    circles.append([xs, ys, 0])
    for _ in range(n):
        circles.append(list(map(int, input().split())))
    circles.append([xt, yt, 0])
    edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
        for j in range(i + 1, n + 2):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            d = (dx ** 2 + dy ** 2) ** 0.5
            r = circles[i][2] + circles[j][2]
            edges[i].append([max(0, d - r), j])
            edges[j].append([max(0, d - r), i])

    ans = dijkstra(n + 2, 0, edges)
    print(ans)
    
main()
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
an = []
ans = []
for i in range(x):
    for j in range(y):
        an.append(lisa[i]+lisb[j])
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for i in range(z):
    for nu in an:
        ans.append(lisc[i]+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

from collections import Counter
from itertools import product

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = []
        while minPFs[x] > 1:
            anss.append(minPFs[x])
            x //= minPFs[x]
        return anss

    maxA = max(As)
    minPFs = getMinPFs(maxA)
    As.sort()

    cntA = Counter(As)

    ans = 0
    setA = set()
    for A in As:
        if cntA[A] == 1:
            PFs = getPrimeFactors(A, minPFs)
            cnt = Counter(PFs)
            ps = list(cnt.keys())
            es = [range(cnt[p]+1) for p in ps]
            L = len(ps)
            for nums in product(*es):
                d = 1
                for i in range(L):
                    d *= ps[i]**nums[i]
                if d in setA:
                    break
            else:
                ans += 1

        setA.add(A)

    print(ans)


solve()


### FIXED CODE ###

from collections import Counter
from itertools import product

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = []
        while minPFs[x] > 1:
            anss.append(minPFs[x])
            x //= minPFs[x]
        return anss

    maxA = max(As)
    minPFs = getMinPFs(maxA)
    As.sort()

    cntA = Counter(As)

    ans = 0
    setA = set()
    for A in As:
        if cntA[A] == 1:
            PFs = getPrimeFactors(A, minPFs)
            cnt = Counter(PFs)
            ps = list(cnt.keys())
            es = [range(cnt[p]+1) for p in ps]
            L = len(ps)
            for nums in product(*es):
                d = 1
                for i in range(L):
                    d *= ps[i]**nums[i]
                if d in setA:
                    break
            else:
                ans += 1

        setA.add(A)

    print(ans)


solve()
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

# ある数の取り得る状態は以下
# (1)部分集合Pに含まれない
# (2)部分集合Pに含まれ、和に使われている
# (3)部分集合Pに含まれ、和に使われていない

# dp[j][k] = 部分集合Pに含まれ(j)、総和がkになっている場合の数
dp = [[0] * (S + 1) for j in range(2)]
dp[0][0] = 1

for i in range(N):
  nextline = [[0] * (S + 1) for j in range(2)]
  for k in range(S, -1, -1):
    # (1)部分集合Pに含まれない
    nextline[0][k] += dp[0][k]
    nextline[0][k] += dp[1][k]
    nextline[0][k] %= DIV

    # (2)部分集合Pに含まれ、和に使われている
    if k + A[i] <= S:
      nextline[1][k + A[i]] += dp[0][k]
      nextline[1][k + A[i]] += dp[1][k]
      nextline[1][k + A[i]] %= DIV

    # (3)部分集合Pに含まれ、和に使われていない
    nextline[1][k] += dp[0][k]
    nextline[1][k] += dp[1][k]
    nextline[1][k] %= DIV
    
  dp = nextline

print((dp[0][-1] + dp[1][-1]) % DIV)


### FIXED CODE ###

# 解説AC
# Tの部分集合をUとすると
# A[i]番目の項目について、
# (1)Tに選ばれない
# (2)Uに選ばれない
# (3)Uに選ばれる
# の3通りの遷移がある
# (1)(2)の場合も含めて数え上げていく（その場合、和は変わらない）

import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353

dp = [0] * (S + 1)
dp[0] = 1
for i in range(N):
  newline = [0] * (S + 1)
  for j in range(len(dp)):
    # 選択肢(1)(2)の場合
    newline[j] += dp[j] * 2
    newline[j] %= DIV
    # 選択肢(3)の場合
    if j + A[i] <= S:
      newline[j + A[i]] += dp[j]
      newline[j + A[i]] %= DIV
  dp = newline

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

import math

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

is_prime = [1] * 1000001
D = [0] * 1000001

for i in range(2, 1001):
    if is_prime[i]:
        D[i] = i
        j = 2 * i
        while j <= 1000000:
            if is_prime[j]:
                D[j] = i
                is_prime[j] = 0
            j += i
for i in range(1001, 1000001):
    if is_prime[i]:
        D[i] = i

count = [0] * 1000001
for a in A:
    k = a
    pre = 0
    while k != 1:
        if pre != D[k]:
            count[D[k]] += 1
        pre = D[k]
        k = int(k / D[k])

ans = 'pairwise coprime'
for x in count:
    if x == N:
        print('not coprime')
        exit()
    if x > 1:
        ans = 'setwise coprime'
print(ans)


### FIXED CODE ###

import math

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

g = 0
for a in A:
    g = math.gcd(g, a)
if g != 1:
    print('not coprime')
    exit()

is_prime = [1] * 1000001
D = [0] * 1000001

for i in range(2, 1001):
    if is_prime[i]:
        D[i] = i
        j = 2 * i
        while j <= 1000000:
            if is_prime[j]:
                D[j] = i
                is_prime[j] = 0
            j += i
for i in range(1001, 1000001):
    if is_prime[i]:
        D[i] = i

count = [0] * 1000001
for a in A:
    k = a
    pre = 0
    while k != 1:
        if pre != D[k]:
            count[D[k]] += 1
            if count[D[k]] == 2:
                print('setwise coprime')
                exit()
        pre = D[k]
        k = int(k / D[k])
print('pairwise coprime')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
n= int(input())
a= [int(input()) for i in range(n)]
memo=[]
def solve(num,ans):
    if num==2:
        print(ans)
    else:
        ans+=1
        tmp=a[num-1]
        if tmp in memo:
            print('-1')
        else:
            memo.append(tmp)
            solve(tmp,ans)
solve(a[0],1)

### FIXED CODE ###

n= int(input())
a= [int(input()) for i in range(n)]
b=1
for i in range(n):
    b=a[b-1]
    if b==2:
        print(i+1)
        exit(0)
print(-1)
### BUGGY CODE ###

n =int(input())
values = list(map(int, input().split()))
#import operator
#from functools import reduce
#a = reduce(operator.mul, values)
a = 1

for i in range(n):
  a = a*values[i]

if  a <= 10**18:
  print(a)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
values =list(map(int, input().split()))
a=1
t = 10**18
for i in range(n):
  if values[i] == 0:
    a = 0
    break
  if a > t:
    continue
  else:
    a=a*values[i]
 
if a <= t:
  print(a)
else:
  print(-1)
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    S = [int(s) for s in input().split()]
    T = [int(t) for t in input().split()]

    DP = [[0 for j in range(M+1)] for i in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for i in range(1, N + 1): DP[i][0] = 1
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1]) % mod
            else: 
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1] - DP[i][j]) % mod
    print(DP[N][M])
    return

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    S = [int(s) for s in input().split()]
    T = [int(t) for t in input().split()]

    DP = [[0 for j in range(M+1)] for i in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for i in range(1, N + 1): DP[i][0] = 1
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1]) % mod
            else: 
                DP[i+1][j+1] = (DP[i+1][j] + DP[i][j+1] - DP[i][j]) % mod
    print(DP[N][M])
    return

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

line = int(input())
number =7
cnt1 =0
cnt2 =1
if line %2 ==0 or line%5 ==0:
  print(-1)
  cnt1 +=2

while cnt1 ==0:
  if number%line !=0:
    number += 7*10**cnt2
    cnt2 +=1
  else:
    cnt1 +=1
if cnt1 ==1:
  print(cnt2)

### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return tuple(map(int, input().split()))

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return tuple(map(int, input().split()))

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-1)
### BUGGY CODE ###

def main():
    S = input()
    mod = 10**9+7
    N = len(S)

    s = S[-1]
    dp = [0]*13
    if s=="?":
        dp[:10] = [1]*10
    else:
        dp[int(s)] = 1

    dig = 1
    for c,s in enumerate(S[:-1][::-1],1):
        dig = dig*10%13
        dp2 = [0]*13
        if s=="?":
            for i in range(10):
                for j,n in enumerate(dp):
                    dp2[(i*dig+j)%13] += n
        else:
            i = int(s)
            for j,n in enumerate(dp):
                dp2[(i*dig+j)%13] += n
        dp = [n%mod for n in dp2]
    print(dp[5])
main()

### FIXED CODE ###

S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])
### BUGGY CODE ###

from scipy.special import perm, comb

mod = 10 ** 9 + 7
N, M = map(int, input().split())

A = perm(M, N, exact=True) % mod

B = 0
for i in range(N + 1):
    B += (-1) ** i * comb(N, i, exact=True) * perm(M - i, N - i, exact=True) % mod

print(A * B % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
N, M = map(int, input().split())

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % mod
            self.inv[i] = -self.inv[mod % i] * (mod // i) % mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % mod) % mod

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

comb = Combination(M + 100)

A = comb.npr(M, N) % mod

B = 0
for i in range(N + 1):
    B += (-1) ** i * comb.ncr(N, i) * comb.npr(M - i, N - i) % mod

print(A * B % mod)
### BUGGY CODE ###

# 入力
k,s=map(int,input().split())
a = [x+y+z for x in range(k+1) for y in range(k+1) for z in range(k+1)\
    if s == x+y+z]
print(len(a))


### FIXED CODE ###

# 入力
k,s=map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= (s-x-y) <= k:
            count += 1
print(count)
### BUGGY CODE ###

H,W = map(int,input().split())
grids = [[s for s in input()] for _ in range(H)]

col_cnt = [[0 for _ in range(W)]for _ in range(H)]
for i in range(W):
  tmp_cnt = 0
  prvjj = 0
  for j in range(H):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      col_cnt[j][i] = 0
      for jj in range(prvjj,j):
        col_cnt[jj][i] = tmp_cnt
      prvjj = j+1
      tmp_cnt = 0
  for jj in range(prvjj,H):
    col_cnt[jj][i] = tmp_cnt

row_cnt = [[0 for _ in range(W)]for _ in range(H)]
for j in range(H):
  tmp_cnt = 0
  prvii = 0
  for i in range(W):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      row_cnt[j][i] = 0
      for ii in range(prvii,i):
        row_cnt[j][ii] = tmp_cnt
      prvii = i+1
      tmp_cnt = 0
  for ii in range(prvii,W):
    row_cnt[j][ii] = tmp_cnt

print(max([row_cnt[j][i]+col_cnt[j][i]-1 for i in range(W) for j in range(H)]))

### FIXED CODE ###

import sys

H,W = map(int,input().split())
grids = [[s for s in sys.stdin.readline()] for _ in range(H)]

col_cnt = [[0 for _ in range(W)]for _ in range(H)]
for i in range(W):
  tmp_cnt = 0
  prvjj = 0
  for j in range(H):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      col_cnt[j][i] = 0
      for jj in range(prvjj,j):
        col_cnt[jj][i] = tmp_cnt
      prvjj = j+1
      tmp_cnt = 0
  for jj in range(prvjj,H):
    col_cnt[jj][i] = tmp_cnt

ans = -float('inf')
for j in range(H):
  tmp_cnt = 0
  prvii = 0
  for i in range(W):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      for ii in range(prvii,i):
        ans = max(ans,col_cnt[j][ii]+tmp_cnt-1)
      prvii = i+1
      tmp_cnt = 0

  for ii in range(prvii,W):
    ans = max(ans,col_cnt[j][ii]+tmp_cnt-1)

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

import heapq
N, M = map(int, input().split())

n_list = list(map(int, input().split()))
heapq.heapify(n_list)

for i in range(M):
    b, c = map(int, input().split())
    for i in range(b):
        n = heapq.heappop(n_list)
        if c > n:
            heapq.heappush(n_list, c)
        else:
            heapq.heappush(n_list, n)
            break

print(sum(n_list))



### FIXED CODE ###

import heapq

def main():
    N, M = map(int, input().split())
    n_list = map(int, input().split())
    n_dic = {}
    for n in n_list:
        n_dic.setdefault(n, 0)
        n_dic[n] += 1
    
    for i in range(M):
        b, c = map(int, input().split())
        n_dic.setdefault(c, 0)
        n_dic[c] += b
    
    com_list = []

    for score, num in n_dic.items():
        heapq.heappush(com_list, (-score, num))
    
    taken = 0
    result = 0

    while True:
        score, num = heapq.heappop(com_list)
        score = -score
        if N - taken > num:
            result += score * num
            taken += num
        else:
            result += score * (N - taken)
            break
    
    print(result)

main()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=1000000007
c=0
import itertools
a=list(itertools.combinations(A,2))
for i in range(len(a)):
  c+=(a[i][0]*a[i][1])%MOD
e=c//MOD
print(c-e*MOD)
  
       

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c=0
d=sum(A)
for i in range(0,N-1):
    d-=A[i]
    c+=A[i]*d
    if(c>10**9+7):
        c%=(10**9+7)
print(c)
### BUGGY CODE ###

H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0
for y1 in range(H):
  for x1 in range(W):
    for y2 in range(H):
      for x2 in range(W):
        if grid[y2][x2]=="#" or grid[y1][x1]=="#":
          continue
        q=deque()
        q.append([y1,x1,0])
        seen=[[False for j in range(W)] for i in range(H)]
        while q:
          node=q.popleft()
          y=node[0]
          x=node[1]
          dist=node[2]
          if seen[y][x]:
            continue
          if grid[y][x]=="#":
            continue
          if y==y2 and x==x2:
            if ans<dist:
              ans=dist
          seen[y][x]=True
          if y-1>=0:
            q.append([y-1,x,dist+1])
          if y+1<H:
            q.append([y+1,x,dist+1])
          if x-1>=0:
            q.append([y,x-1,dist+1])
          if x+1<W:
            q.append([y,x+1,dist+1])
            
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0

INF=10**9
ans=0
for i in range(H):
  for j in range(W):
    dist=[[INF for j in range(W)] for i in range(H)]
    q=deque()
    q.append([i,j,0])
    while q:
      node=q.popleft()
      y=node[0]
      x=node[1]
      d=node[2]
      if grid[y][x]=="#":
        continue
      if dist[y][x]<=d:
        continue
      if ans<d:
        ans=d
      dist[y][x]=d
      cases=((0,1),(0,-1),(1,0),(-1,0))
      for c in cases:
        if 0<=y+c[0]<H and 0<=x+c[1]<W:
          q.append([y+c[0],x+c[1],d+1])
      
print(ans)
### BUGGY CODE ###

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

b=[a[0],a[1]]
ans=a[0]
for i in range(2,n):
    cnt=0
    d=1
    for l in range(len(b)-1):
        if min(b[l],b[l+1])>cnt:
            d=l+1
            cnt=min(b[l],b[l+1])
    if min(b[0],b[-1])>cnt:
        b.append(a[i])    
        ans+=min(b[0],b[-1])
    else:
        b.insert(d,a[i])
        ans+=cnt
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
if n==2:
    exit(print(max(a)))
b=[a[0],a[1]]
ans=a[0]
a=a[1:]
from math import floor
for i in range(n-2):
    num=floor(i/2)
    ans+=a[num]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0] * N
for i in range(N):
  for j in range(N):
    if A[j] == i+1:
      B[i] = j+1
print(*B)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [[] for i in range(N)]
for i in range(N):
  B[i] = [A[i], i+1]
B.sort()
ans = [0 for i in range(N)]
for i in range(N):
  ans[i] = B[i][1]
print(*ans)
### BUGGY CODE ###

import numpy as np
import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c
L = len(C)
A = np.array(C)

ans = 1
f = np.ones(L + 1, dtype="int")
for i in range(2, L):
    g = f[:i-1]
    ans += np.sum(g[A[:i-1] == A[i]])
    f[i + 1] = ans

print(ans)

### FIXED CODE ###

import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))