Harryxun/stf_run huggingface dataset:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X = MAP()

# a_0 = 1, p_0 = 1
a, p = [1], [1]
for i in range(N):
    # 漸化式
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def f(N, X):
    if N == 0:
        if X <= 0:
            return 0
        if X == 0:
            return 1
    elif X <= a[N-1] + 1:
        return f(N-1, X-1)
    elif X > a[N-1] + 1:
        return p[N-1] + 1 + f(N-1, X - (a[N-1] + 1 + 1))

print(f(N, X))


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X = MAP()

# a_0 = 1, p_0 = 1
a, p = [1], [1]
for i in range(N):
    # 漸化式
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def f(N, X):
    if N == 0:
        if X <= 0:
            return 0
        if X > 0:
            return 1
    elif X <= a[N-1] + 1:
        return f(N-1, X-1)
    elif X > a[N-1] + 1:
        return p[N-1] + 1 + f(N-1, X - (a[N-1] + 1 + 1))

print(f(N, X))
import fractions
from functools import reduce
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
#print(n)
n=sorted(set(n),reverse = True)
bs = n[0]
#print(n)
#c=len(n)


def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)

def lcm_o():
        global n
        return reduce(lcm_b, n)

def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                if n[j] % t == 0 and (n[j] / t) % 2 == 1:
                        n[j] = int(n[j]/t)
                else: return 0
        return i-1

if len(n) > 0:
        
        c = chk(n[-1])
        
        if  c != 0:
                v = lcm_o()*(2**(c-1))
                
                if v > M:
                        print(0) 
                else:
                        v = M//v
                        if v%2==1: v+=1
                        print(int(v//2))
        
        else: print(0)
elif N==1:
        v = int(bs*0.5)
        v = M//v
        if v%2==1: v+=1
        print(int(v//2))

### FIXED CODE ###

N,M= [int(i) for i in input().split()]
print("Yes" if N*500 >= M else "No")
import sys
lines = sys.stdin.readlines()

S = str(lines[0])
X = []
A = []
p =1
for i in range(len(S)):
  A.append(p)
  p = p*10%2019

a = 0
for i in range(len(S)):
  a = (a + int(S[len(S)-i-1])*A[i]) %2019
  X.append(a)

X.sort()


### FIXED CODE ###

S = str(input())

#10**nのmod計算
A = []
p =1
for i in range(len(S)):
  A.append(p)
  p = p*10%2019

#左からi文字以降の数字列のmod計算
X = []
a = 0
for i in range(len(S)):
  a = (a + int(S[len(S)-i-1])*A[i]) %2019
  X.append(a)
X.sort()
flag =1
n = 0

#modが同じになる組み合わせ、またはもともとmodが0になる数字列の個数の総和計算
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += int(flag*(flag-1)/2)
    flag = 1
n += int(flag*(flag-1)/2)
if X[len(X)-1]==0:
  n +=1
print(n)
import fractions

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

d = list(map(int, input().split()))

m = (d[0] - x).abs()
for di in d:
  m = fractions.gcd(m, (di - x).abs())

print(m)

### FIXED CODE ###

import fractions

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

d = list(map(int, input().split()))

m = abs(d[0] - x)
for di in d:
  m = fractions.gcd(m, abs(di - x))

print(m)
# coding: utf-8
import sys
import numpy as np

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

# dp
N = ir()
INF = 10 ** 8
dp = np.array([INF] * 100001)
dp[0] = 0
for i in range(5, 0, -1):
    num = 9 ** i
    for j in range(100000):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

for i in range(6, 0, -1):
    num = 6 ** i
    for j in range(100000):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

num = 1
for j in range(100000):
    dp[j+num] = min(dp[j+num], dp[j]+1)

answer = dp[N]
print(answer)


### FIXED CODE ###

N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t = i
    while t>0:
        cnt+=t%6
        t//=6
    t=N-i
    while t>0:
        cnt+=t%9
        t//=9
    ans=min(ans,cnt)
print(ans)
-*- coding: utf-8 -*-
 
import math
 
l = rawinput().split()
print(math.ceil(l[0] + l[1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
 
l = list(map(int, input().split()))
print(math.ceil((l[0] + l[1])/2))
import math
a,b,x=map(int,input().split())
c1=a*a*b/2
if x>c1:
    ans=math.atan((a*a*a)/((2*a*a*b)-(2*x)))
    ans=math.degrees(ans)
    print(90-ans)
else:
    ans=math.atan((2*x)/(a*b*b))
    ans=math.degrees(ans)
    print(90-ans)
    

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
c1=a*a*b/2
if x==a*a*b:
    print(0.0)
    exit(0)
if x>c1:
    ans=math.atan((a*a*a)/((2*a*a*b)-(2*x)))
    ans=math.degrees(ans)
    print(90-ans)
else:
    ans=math.atan((2*x)/(a*b*b))
    ans=math.degrees(ans)
    print(90-ans)
from math import gcd
from functools import reduce
N = int(input())
a = list(map(int, input().split()))

list_ans = []

for i in range(N):
    remove_a = a.pop(0)
    #print("a is",a)
    ans = reduce(gcd, a)
    list_ans.append(ans)
    a.append(remove_a)
    #print("fix a is",a)

print(max(list_ans))

### FIXED CODE ###

from fractions import gcd

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

L = [0]
R = [0]

for i in range(N):
    L.append(gcd(L[i], A[i]))  # 0, gcd(0,A[0]), gcd(0,A[0],A[1]) , ...
    R.append(gcd(R[i], A[N - i -1])) # 0 , gcd(0, A[N-1]), gcd(0, A[N-1], A[N-2]))..

R.reverse() # R is gcd(0,A[N-1]...A[0]), gcd(0,A[N-1]...A[1]),....
# pairs are 
#  L     :R
#  0    : (0,A[N-1],A[n-2], ... A[1])
#  A[0] : (0,A[N-1],A[n-2], ... A[2])
#  ...
#  A[0,1,..N-3] :(0,A[N-1]
#  A[0,1,..N-2] :(0)
print(max( (gcd(L[i], R[i+1]) for i in range(N))))
n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
  if a[i]==i:
    b+=0
  else:
    b+=1
if b==0or2:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
  if a[i]==i+1:
    b+=0
  else:
    b+=1
if b==0 or b==2:
  print("YES")
else:
  print("NO")
N, M = map(int, input().split())

AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans = [-1] * N
ans[0] = 0

from collections import deque
que = deque
que.insert(0)

while que:
    s = que.popleft()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.put(v)

print("Yes")
print(*ans[1:], sep="\n")

### FIXED CODE ###

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

AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a, b in AB:
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans = [-1] * N
ans[0] = 0

import queue
que = queue.Queue()
que.put(0)

while que.qsize():
    s = que.get()
    for v in es[s]:
        if ans[v] == -1:
            ans[v] = s+1
            que.put(v)

print("Yes")
print(*ans[1:], sep="\n")
import math
def factorization(n):
    arr = []
    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
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
a, b = map(int, input().split(' '))
gc = math.gcd(a, b)
r = []
r = factorization(gc)
if len(r) == 1:
    print(1)
else:
    print(len(r)+1)

### FIXED CODE ###

def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a


def factorization(n):
    arr = []
    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
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
a, b = map(int, input().split(' '))
gc = gcd(a, b)
r = []
r = factorization(gc)
if r[0][0] == 1:
    print(1)
else:
    print(len(r)+1)
from collections import deque
h,w = map(int,input().split())
map = [list(input()) for _ in range(h)]
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque([])
    q.append((0,0))
    d = [([-1]*m)for _ in range(n)]

    d[0][0] = 0

    while q:
        x,y = q.popleft()
        if (x,y) == (h-1,w-1):
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w and d[nx][ny]==-1 and map[nx][ny]!="#":
                q.append((nx,ny))
                d[nx][ny]= d[x][y]+1
    if map[h-1][w-1]:
        return h*w - d[h-1][w-1] - 1 - sum(1 for i in range(h) for j in range(w) if map[i][j] == "#")
    else:
        return -1

print(bfs())

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
map = [list(input()) for _ in range(h)]
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque([])
    q.append((0,0))
    d = [([-1]*w)for _ in range(h)]

    d[0][0] =  ~-sum(1 for i in range(h) for j in range(w) if map[i][j] == ".")

    while q:
        x,y = q.popleft()
        if (x,y) == (h-1,w-1):
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<h and 0<=ny<w and d[nx][ny]==-1 and map[nx][ny]!="#":
                q.append((nx,ny))
                d[nx][ny]= d[x][y] -1
    return d[h-1][w-1]
print(bfs())
from sys import stdin, stdout


def main():
    line = stdin.readline()
    parts = line.split()
    n = int(parts[1])
    m = int(parts[2])
    stdout.write(str((n-1)*(m-1)))


main()


### FIXED CODE ###





a,b=map(int,input().split())
print((a-1)*(b-1))
if (inp[0]<8000000000):
    if (inp[0]+inp[1]-inp[2] < -2 * (inp[0]*inp[1])**0.5):
        print("Yes")
    else:
        print("No")
else:
    if(inp[0]**2+inp[1]**2+inp[2]**2-2*(inp[0]*inp[1]+inp[1]*inp[2]+inp[0]*inp[1])<0):
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

inp = list(map(int,input().split()))
a =inp[0]
b = inp[1]
c = inp[2]
if (c - a- b > 0):
    if (0< a**2 +b**2 + c**2- 2*(a*b + b*c + a*c)):
        print("Yes")
    else:
        print("No")
else:
    print("No")
I=lambda:map(int,input().split())
n,m=I()
n+=1
g=[[] for _ in range(n)]
v=[0  for _ in range(n)]

for _ in range(m):
  a,b=I()
  g[a]+=[b]
  g[b]+=[a]
l=[]
v[1]=1
def bfs(x,l):
  for j in g[x]:
    if v[j]==0:
      v[j]=1
      return [j]+bfs(j,l)
      break
  else:
    return l
z=bfs(1,l)[::-1]+[1]+bfs(1,l)
print(len(z))
print(*z)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
I=lambda:map(int,input().split())
n,m=I()
g=[set() for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a].add(b)
  g[b].add(a)

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      l=dfs(j)
      l.append(j)
      return l
      break
  else:
    return []
z=dfs(1)+[1]+dfs(1)[::-1]
print(len(z))
print(*z)
s=int(input())
k=input()
if len(s) <=k:
  print(s)
else:
  print(s[:k] + '...')

### FIXED CODE ###

s=int(input())
k=input()
if len(k) <=s:
  print(k)
else:
  print(k[:s] + '...')
N = int(input())
H = list(map(int,input().split()))
cnt = 0
for i in range(N):
  if H[i]-H[i+1]=1:
    H[i] = H[i]-1
  elif H[i]-H[i+2]>1:
    cnt = 1
    break
if cnt == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
H.reverse()
cnt = 0
for i in range(N-1):
  if H[i+1]-H[i]==1:
    H[i+1] = H[i+1]-1
  elif H[i+1]-H[i]>1:
    cnt = 1
    break
if cnt == 0:
  print('Yes')
else:
  print('No')
S,T = map(str,input().split())
A,B = map(str,input().split())
U = input()
if U == S:
  print(A-1,B)
else:
  print(A,B-1)

### FIXED CODE ###

S,T = map(str,input().split())
A,B = map(int,input().split())
U = input()
if U == S:
  print(A-1,B)
else:
  print(A,B-1)
from fractions import gcd
#from functools import reduce
a=int(input())
li=list(map(int,input().split()))
left_gcd=[]
left_gcd.append(li[0])
right_gcd=[]
right_gcd.append(li[a-1])

for i in range(a-1):
    left_gcd.append(math.gcd(left_gcd[i],li[i+1]))
k=0
for i in range(a-1,0,-1):
    right_gcd.append(math.gcd(right_gcd[k],li[i-1]))
    k=k+1
# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)
#print(right_gcd)
#print(left_gcd)
num_li=[]
num_li.append(right_gcd[a-2])
num_li.append(left_gcd[a-2])
#s=2
for i in range(a):
    ans=math.gcd(left_gcd[(a-3)-i],right_gcd[i])
    #print(left_gcd[(a-3-i)],right_gcd[i])
  
    #print(ans)
    num_li.append(ans)
    

print(max(num_li))


### FIXED CODE ###

 
#from functools import reduce
def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x
 
a=int(input())
li=list(map(int,input().split()))
left_gcd=[0]
#left_gcd.append(li[0])
right_gcd=[0]
#right_gcd.append(li[a-1])

for i in range(a):
    left_gcd.append(gcd(li[i],left_gcd[i]))
    right_gcd.append(gcd(li[a-1-i],right_gcd[i]))
    #k=k+1
# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)
#print(right_gcd)
#print(left_gcd)
num_li=[]
#num_li.append(right_gcd[a-2])
#num_li.append(left_gcd[a-2])
#s=2
for i in range(a):
    ans=gcd(left_gcd[(a-1)-i],right_gcd[i])
    #print(left_gcd[(a-3-i)],right_gcd[i])
  
    #print(ans)
    num_li.append(ans)
    

print(max(num_li))
import sys
# A,B,C = [int(n) for n in input().split()]
N,K = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())
bucket = [0]*(N+1)
A = [int(n) for n in input().split()]
s = set(A)
for a in A:
    bucket[a]+=1
bucket = [n for n in bucket if n != 0]
rc = len(s) - K
ans = 0
for r in range(rc):
    tminid = bucket.index(min(bucket))
    ans += bucklet[tminid]
    bucket[tminid]=200006
print(ans if ans >=0 else 0)


### FIXED CODE ###

import sys
# A,B,C = [int(n) for n in input().split()]
N,K = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())
bucket = [0]*(N+1)
A = [int(n) for n in input().split()]
dic = {}
for a in A:
    if not(a in dic):
        dic[a]=1
    else:
        dic[a]+=1
val = sorted(dic.values())
# print(val)
rc = len(val) - K
ans = 0
for r in range(rc):
    ans += val[r]
print(ans if ans >=0 else 0)
import math
a,b,n=map(int, input().split()) 
max = -10000
tmp = 0

for i in range(1, n+1):
    tmp = math.floor(a * i / b) - math.floor(i / b)
    if max < tmp:
        max = tmp

print(max)

### FIXED CODE ###

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

max = int(b/k)

for i in range(1,max+1):
    tmp = k * i
    if a <= tmp and b >= tmp:
        print('OK')
        exit()

print('NG')
def main():
    s = input()
    n = len(s)
    ans = 0
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            x = int(s[i:j])
            p = 2 ** max(0, i - 1)
            q = 2 ** max(0, n - j - 1)
            ans += x * p * q

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    ans = 0
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            x = int(s[i:j])
            p = 2 ** max(0, i - 1) * 2 ** max(0, n - j - 1)
            ans += x * p

    print(ans)


if __name__ == '__main__':
    main()
# -*- coding: UTF-8 -*-

nums = input()
set_nums = list(set(nums))
other = sum(nums) - sum(set_nums)
set_nums.remove(other)
print(set_nums[0])

### FIXED CODE ###

nums = map(int, input().split())
d = {}
for n in nums:
  d.setdefault(n, 0)
  d[n] += 1
print(list(d.keys())[list(d.values()).index(1)])
x=map(int,input().split())
if x.count(7)==1 and x.count(5)==2:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

x=[i for i in map(int,input().split())]
if x.count(5)==2 and x.count(7):
  print('YES')
else:
  print('NO')
dp = [[-1 for i in range(6005)] for j in range(6005)]

def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    A.append(a)
    B.append(b)

print(f(0, 0))


### FIXED CODE ###

dp = [[-1 for i in range(6005)] for j in range(6005)]


def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

N, T = [int(i) for i in input().split()]
data = []
A, B = [], []

for i in range(N):
    a, b = [int(j) for j in input().split()]
    data.append([a,b])
    A.append(a)
    B.append(b)

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

for idx in range(N, -1, -1):
    for time in range(T, -1, -1):
        if time == T:
            dp[idx][time] = 0
            continue
        if idx == N:
            dp[idx][time] = 0
            continue
        if A[idx]+time >= T:
            fval = 0
        else:
            fval = dp[idx+1][time+A[idx]]
        dp[idx][time] = max(dp[idx+1][time], B[idx] + fval)

print(dp[0][0])
N,M=list(map(int,input().split(" ")))
l=[]
l=[list(map(int,input().split(" "))) for i in range(n)]
drink=0
price=0
i=0
l.sort(key=lambda x: x[0])
while drink<M:
    pri=l[i][0]
    num=l[i][1]
    i+=1
    drink+=num
    price+=pri*num
if drink>M:
    price-=(drink-m)*pri
print(price)


### FIXED CODE ###

n,m=list(map(int,input().split(" ")))
l=[]
l=[list(map(int,input().split(" "))) for i in range(n)]
drink=0
price=0
i=0
l.sort(key=lambda x: x[0])
while drink<m:
    pri=l[i][0]
    num=l[i][1]
    i+=1
    drink+=num
    price+=pri*num
if drink>m:
    price-=(drink-m)*pri
print(price)
S = input()

count = 0
tf = True
if S[0] != "A" or S[1] == "C" or S[-1] == "C":
    tf = False

for i in range(len(S)):
	if tf:
		break
    if i == 0:
        continue
    if S[i] == "C":
        count += 1
    elif not S[i].islower():
        tf = False

if tf and count == 1:
    print("AC")
else:
    print("WA")


### FIXED CODE ###

S = input()

count = 0
ans = True

if S[0] != "A":
    ans = False
if not "C" in S[2:-1]:
    ans = False
for s in S:
    if s.isupper():
        count += 1
if count > 2:
    ans = False

print("AC" if ans else "WA")
x = input().split()
#x = "3 5 0 4 3 6 2 7 2 5 3 3 4 0 5 3 7 5 3 7 2 7 5 7 0 7 2 9 3 2 9 1 3 6 2 0 2 4 6 4 2 3 3 5 7 4 0 6 9 7 6 7 9 8 5 2 2 0 4 7 6 5 5 4 6 3 2 3 0 5 4 3 3 6 2 3 4 2 4 0 8 9 4 6 5 4 3 5 3 2 0 8 2 1 3 4 5 7 8 6 4 0 3 5 2 6 1 2 5 3 2 1 6 9 2 5 6".split()
#x = "2 4 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 2 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 2 9 9 9 0 9 9 2 9 9 9 9 9 9 9 0 -1 -1 -1 -1 8 1 1 8".split()
h = int(x[0])
w = int(x[1])
d = []
for i in range(10):
    d.append(
        list(map(int, x[2 + i * 10 : 2 + i * 10 + 10]))
    )
a = []
for i in range(h):
    a.append(
        list(map(int, x[102 + i * w: 102 + i * w + w]))
    )
#d = [[0] * 10] * 10
for k in range(10):
    for i in range(10):
        for j in range(10):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

#for k in range(0, 10):
#    print(c[k])
#for k in range(0, 10):
#    print(d[k])
#print(d[8][1])

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] != 1 or a[i][j] != -1:
            ans += d[a[i][j]][1]
print(ans)


### FIXED CODE ###

n = int(input())
l = list(map(int , input().split()))
l.sort(reverse=True)
#print(l[0], sum(l[1:]))
if l[0] < sum(l[1:]):
    print('Yes')
else:
    print('No')
import sys
from collections import deque

input = sys.stdin.readline
n, u, v = map(int, input().split())

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, dep, p):
    stack = deque([[cur, pre, dep, p]])
    while stack:
        cur, pre, dep, p  = stack.pop()
        memo[cur][p] = dep
        for e in E[cur]:
            if e != pre:
                stack.push(e, cur, dep + 1, p)

dfs(u - 1, - 1, 0, 0)
dfs(v - 1, -1, 0, 1)

# print(memo)
ans = 0
for a, b in memo:
    ans = max(ans, b - 1)
print(ans)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline
n, u, v = map(int, input().split())

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, p):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        if pre != -1:
            memo[cur][p] = memo[pre][p] + 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur])

dfs(u - 1, - 1, 0)
dfs(v - 1, -1, 1)

# print(memo)
ans = 0
for a, b in memo:
    if a <= b:
        ans = max(ans, b - 1)
print(ans)
def prepare(n,arr):
    nodeArr = [[] for i in range(n)]
    for ar in arr:
        nodeArr[ar[0]-1].append([ar[1]-1,ar[2]])
        nodeArr[ar[1]-1].append([ar[0]-1,ar[2]])
    return nodeArr

def dfs(parent,currentNode,distance):

    if len(nodeArr[currentNode]) == 1:
        if currentNode != 0:
            # 末点
            # res[currentNode] = distance
            return

    for next in nodeArr[currentNode]:
        nextNode = next[0]
        nextNodeDistance = next[1]
        if nextNode == parent:
            continue
        dfs(currentNode,nextNode,distance + nextNodeDistance)
    res[currentNode] = distance


n = int(input())

arr = []

for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

nodeArr = prepare(n, arr)


if n == 1:
    print(1)
else:
    res = [-1 for i in range(n)]

    dfs(-1,0,0)

    result = [(re % 2) for re in res]

    for re in res:
        print(re % 2)



### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)
def prepare(n,arr):
    nodeArr = [[] for i in range(n)]
    for ar in arr:
        nodeArr[ar[0]-1].append([ar[1]-1,ar[2]])
        nodeArr[ar[1]-1].append([ar[0]-1,ar[2]])
    return nodeArr

def dfs(currentNode,distance):
    res[currentNode] = distance
    for next in nodeArr[currentNode]:
        nextNode = next[0]
        nextNodeDistance = next[1]
        if res[nextNode] == -1:
            dfs(nextNode,distance + nextNodeDistance)




n = int(input())

arr = []

for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

nodeArr = prepare(n, arr)


if n == 1:
    print(1)
else:
    res = [-1 for i in range(n)]

    dfs(0,0)

    result = [(re % 2) for re in res]

    for re in res:
        print(re % 2)