Harryxun/stf_run huggingface dataset:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

print(max([len(d) for d in D]))

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

print(max([len(d) for d in D]))

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])
import math 
a = int(input)
print(math.pi * 2 * a)


### FIXED CODE ###

import math 
a = int(input())
ans = 2 * a * math.pi
print(ans)
a=int(input())
b=int(input())
c=int(input())
if a < b and b < c:
 print("Yes")
else:
   print("No") 


### FIXED CODE ###

c=input().split(" ")
a=int(c[0])
b=int(c[1])
c=int(c[2])
if a < b and b < c:
 print("Yes")
else:
   print("No")
MOD = 10**9 + 7


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena-1, MOD)
            pre = ((pre_pow * 3) % MOD) * a + pre_pow * pre_hatena
            post_pow = pow(3, post_hatena-1, MOD)
            post = ((post_pow * 3) % MOD) * c + post_pow * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 10**9 + 7


def main():
    S = input()
    N = len(S)
    pre_hatena = S[:1].count("?")
    a = S[:1].count("A")
    post_hatena = S[2:].count("?")
    c = S[2:].count("C")

    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "B":
            pre_pow = pow(3, pre_hatena-1, MOD)
            pre = ((pre_pow * 3) % MOD) * a + pre_pow * pre_hatena
            post_pow = pow(3, post_hatena-1, MOD)
            post = ((post_pow * 3) % MOD) * c + post_pow * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "A":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "C":
            c -= 1
    print(ans)


if __name__ == '__main__':
    main()
A,B=map(int,input().split())
B-A=N
X=N*(N+1)//2
print(X-B)

### FIXED CODE ###

A,B=map(int,input().split())
N=B-A
X=N*(N+1)//2
print(X-B)
x,y,z = map(int, input().split())

if (x == y and y != z) or (x==z and y !=z) or (a !=b and b==c):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

x,y,z = map(int, input().split())

if (x == y and y != z) or (x==z and y !=z) or (x !=y and y==z):
  print("Yes")
else:
  print("No")
a,b,c,x,y = map(int,input().split())
fx = x
fy = y
fl = 0
val = int(0)
fmin = min(x,y)
if a>2*c:
  val += 2*c*x
  y = y - x
  x = 0
  fl += 1
if y<0:
  y=0
if b>2*c:
  if fl == 1:
    val += 2*c*y
    y = 0
  else:
    val += 2*c*y
    x = x - y
    y = 0 
if x<0:
  nx = 0
else:
  nx = x
if y<0:
  ny = 0
else:
  ny = y
if a+b>2*c:
  nnx = nx - min(nx,ny)
  nny = ny - min(nx,ny)
  val += 2*c*min(nx,ny)
print(val+a*nnx+b*nny)

### FIXED CODE ###

a,b,c,x,y = map(int,input().split())
fx = x
fy = y
fl = 0
val = int(0)
fmin = min(x,y)
if a>2*c:
  x = 0
  y = y - fx
  val += 2*c*fx
  fl += 1
if y < 0:
  y = 0
if b>2*c:
  if fl == 1:
    val += 2*c*y
    y = 0
  else:
    val += 2*c*y
    x = x -y
    y = 0 
if x < 0:
  x = 0
nx = x
ny = y
if a+b>2*c:
  x = x - min(nx,ny)
  y = y - min(nx,ny)
  val += 2*c*min(nx,ny)
print(val+a*x+b*y)
import math
N = input()
for val in range(1,N+1):
	x = map(float,raw_input().split(' '))
	d = math.sqrt((x[0]-x[3])**2 - (x[1]-x[4])**2)
	s = x[2]+x[5]
	r = math.fabs(x[2]-x[5])
	if r >= d:
		if x[2] > x[5]:
			print '2'
		else:
			print '-2'
	elif s < d:
		print '0'
	else:
		print '1'

### FIXED CODE ###

import math
N = input()
answers = []
for val in range(1,N+1):
	x = map(float,raw_input().split(' '))
	d = (x[0]-x[3])**2 + (x[1]-x[4])**2
	d = math.sqrt(d)
	d = math.fabs(d)
	s = x[2]+x[5]
	r = math.fabs(x[2]-x[5])
	if d > s:
		answers.append(0)
	elif d == s:
		answers.append(1)
	elif d < s:
		if d < r:
			if x[2] > x[5]:
				answers.append(2)
			else:
				answers.append(-2)
		elif d >= r:
			answers.append(1)
for val in answers:
	print val
lst = [1,2,3]
l = list(map(int, input().split()))
lst.remove(l[0])
lst.remove(l[1])
print(lst)

### FIXED CODE ###

lst = [1,2,3]
l = [int(input()) for i in range(2)]
lst.remove(l[0])
lst.remove(l[1])
print(lst[0])
a, b, c = input()
if a <= c and c <= b:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

v = input().split(' ')
if int(v[0]) <= int(v[2]) and int(v[2]) <= int(v[1]):
    print('Yes')
else:
    print('No')
numbers = map(int, input().split())
number_list = [i+numbers[0] for i in range(numbers[1]-numbers[0])]
count = 0
for i in numbers_list:
  if number_list % numbers[2] == 0:
    count+=1
print(count)

### FIXED CODE ###

numbers = [i for i in map(int, input().split())]
number_list = [i+numbers[0] for i in range(numbers[1]-numbers[0]+1)]
count = 0
for i in number_list:
  if i % numbers[2] == 0:
    count+=1
print(count)
N , L= map(int,input().split())
lst = list()
Str = ''
for i in range(L):
    lst.append(input())
lst.sort()
for j in lst:
    Str += j
print(Str)


### FIXED CODE ###

N,L=map(int, input().split())
S=[]
for i in range(N):
    S.append(input())
S.sort()
result=''
for j in range(N):
    result+=S[j]     
print(result)
N=int(input())
L=[int(i) for i in input().split()]
L1=sorted(L)
a=L1[N//2]
b=L1[N//2-1]
for i in range(N):
  if L[i]<a:
    print(a)
  else:
    print(b)

### FIXED CODE ###

N,M,X=(int(i) for i in input().split())
L=[int(i) for i in input().split()]
a=0
b=0
for i in range(M):
  if L[i]<X:
    a+=1
  else:
    b+=1
print(min(a,b))
from itertools import groupby

def count(s):
    l = []
    c = 0
    for key,value in groupby(s):
        l.append(list(value))
    for i in l:
        c += len(i)//2
    return c


if __name__=="__main__":
    s = list(input())
    k = int(input())
    c = 0
  	c += count(s*k)
    print(c)



### FIXED CODE ###

from itertools import groupby

def count(s):
    l = []
    c = 0
    for key,value in groupby(s):
        l.append(list(value))
    for i in l:
        c += len(i)//2
    return c
s = list(input())
k =int(input())
if k <= 10**5:
    print(count(s*k))
else:
    d2 = count(s*3)-count(s*2)
    d3 = count(s*4)-count(s*3)
    if d2 != d3:
        if k%2 == 1:
            print(d2*((k-2)//2+1) + count(s*2) + d3*((k-2)//2))
        else:
            print(d2*((k-2)//2) + count(s*2) + d3((k-2)//2))
    else:
        print(d2*(k-2) + count(s*2))
n = int(input())
h = [int(i) for i in input().split()]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

f_inf = float('inf')
dp = [f_inf] * (10**5+10)
dp[0] = 0
for i in range(n-1):
    dp[i + 1] = chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]))
    # n-2の時は2つ先はない
    if i < n-2:
        dp[i + 2] = chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]))
print(dp[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())) + [0]*K, dtype=np.int64)
H = np.array(h)
dp = np.full(N + K, 10 ** 10, dtype=np.int64)
dp[0] = 0
for i in range(1, N):
    dp[i:i + K] = np.minimum(dp[i:i + K],
                             np.abs(H[i:i + K] - H[i - 1]) + dp[i - 1])
print(dp[N - 1])
from math import ceil
a,b = map(int, input().split())
print(ceil((a+b)/2)

### FIXED CODE ###

from math import ceil
a,b = map(int, input().split())
print(ceil((a+b)/2))
N = input()
if "7" in N:
  print("Yes"):
else:
  print("No")

### FIXED CODE ###

N = input()
if "7" in N:
  print("Yes")
else:
  print("No")
import math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
g = A.pop()
for a in A:
    g = math.gcd(g, a)
if K <= max(A) and K % g == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]


def gcd(x, y):
    if x < y:
        return gcd(y, x)
    elif y == 0:
        return x
    else:
        return gcd(y, x % y)


g = A[0]
for a in A:
    g = gcd(g, a)
if K <= max(A) and K % g == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
n = int(input())
l = list(map(int, input().split()))

l = l+l
xl = []
for i in range(2):
    a = 0
    m = False
    for j in range(i, n+i):
        if m is False:
            a += l[j]
            m = True
        else:
            a -= l[j]
            m = False
    xl.append(a)
    
for i in range(2, n):
    xl.append3(xl[-2] - l[i-2]*2 + l[i-1]*2)
    
print(" ".join(map(str, xl)))

### FIXED CODE ###

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

l = l+l
xl = []
for i in range(2):
    a = 0
    m = False
    for j in range(i, n+i):
        if m is False:
            a += l[j]
            m = True
        else:
            a -= l[j]
            m = False
    xl.append(a)
    
for i in range(2, n):
    xl.append(xl[-2] - l[i-2]*2 + l[i-1]*2)
    
print(" ".join(map(str, xl)))
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
b = [list(map(int,input().split())) for i in range(n)]

ans = []

for i in a:
  count = 10**10
  check = 0
  for j in range(m):
    if count > abs(i[0]-b[j][0])+abs(i[1]-b[j][1]):
      check = j+1
      count = abs(i[0]-b[j][0])+abs(i[1]-b[j][1])
    
  ans.append(check)
for i in ans:
  print(i)

### FIXED CODE ###

n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
b = [list(map(int,input().split())) for i in range(m)]

ans = []

for i in a:
  count = 10**10
  check = 0
  for j in range(m):
    if count > abs(i[0]-b[j][0])+abs(i[1]-b[j][1]):
      check = j+1
      count = abs(i[0]-b[j][0])+abs(i[1]-b[j][1])
    
  ans.append(check)
for i in ans:
  print(i)
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)


N = int(input())
X = input()
f = 0
count = 1
ans = 0
fi = 0
for i in range(N-1, -1, -1):
    fi = toggle_nth_bit(int(X, 2), i)
    f = bin(toggle_nth_bit(int(X, 2), i))
    ans = fi % f.count("1")
    while ans != 0:
        count += 1
        if ans == 1:
            break
        ans = ans % bin(ans).count("1")

    print(count)
    count = 1



### FIXED CODE ###

def pc(x):
    return format(x, 'b').count('1')


N = int(input())
X = input()
Xo = int(X, 2)

count = 0
ans = 0
ori = pc(Xo)
X = list(X)

Xp = Xo%(ori + 1)
if ori == 1:
    Xm = 0
else:
    Xm = Xo % (ori - 1)

# for i in range(N-1, -1, -1):
for i in range(N):
    if ori == 1 and X[i] == '1':
        print(0)
        continue
    else:
        if X[i] == '1':
            # ans = Xm - pow(2, i, ori - 1)
            ans = Xm - pow(2, N-1-i, ori - 1)
            ans %= ori - 1
        else:
            # ans = Xp - pow(2, i, ori + 1)
            ans = Xp + pow(2, N-1-i, ori + 1)
            ans %= ori + 1
    count = 1
    while ans > 0:
        # count += 1
        # if ans == 1:
        #     break
        ans %= pc(ans)
        count += 1

   
    print(count)
    count = 1
NUM = int(input())
K = int(input())
POS = list(map(int, input().split()))
sum = 0
for i in POS:
    a = pow(i, 2)
    b = pow(abs((i - K)), 2)
    sum += min(a, b)
print(sum)



### FIXED CODE ###

N = int(input())
A = int(input())
 
print(pow(N, 2) - A)
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = [0, 0]
    end = [h-1, w-1]
    while now != end:
        nxt = None
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            nxt = now[:]
            nxt[0] += 1
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            if nxt != None:
                print("Impossible")
                return
            nxt = now[:]
            nxt[1] += 1
        now = nxt
    print("Possible")
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = (0, 0)
    end = (h-1, w-1)
    visited = set([now])
    while True:
        nxt = None
        #print(now)
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            nxt = (now[0]+1, now[1])
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            if nxt is not None:
                print("Impossible")
                return
            nxt = (now[0], now[1]+1)
        #print("next", nxt)
        if now[0]-1 >= 0 and a[now[0]-1][now[1]] == "#":
            if (now[0]-1,now[1]) not in visited:
                print("Impossible")
                return
        if now[1]-1 >= 0 and a[now[0]][now[1]-1] == "#":
            if (now[0],now[1]-1) not in visited:
                print("Impossible")
                return
        
        if now == end:
            break
        if nxt is None:
            print("Impossible")
            return
        now = nxt
        visited.add(nxt)
    print("Possible")
    
if __name__ == "__main__":
    main()
N = input()

count = 0
for i in range(1,N+1):
  if len(str(i)) % 2 != 0:
    count += 1

print(count)
  
  

### FIXED CODE ###

n = input()
count =0
for i in range(1,int(n)+1):
    if len(str(i)) % 2 != 0:
        count +=1 
print(count)
def moji_hanbetsu(S,N):
    if N % 2 == 1:
        ans = "no"
    else:
        n = int(N/2)
        s1 = S[0:n]
        s2 = S[-n:]
        if s1 == s2:
            ans="yes"
        else:
            ans ="no"
    return ans
 
N,S = input()

### FIXED CODE ###

N = int(input())
S = input()

if (N % 2) == 1:
    ans = "No"
else:
    n = int(N/2)
    s1 = S[0:n]
    s2 = S[-n:]
    if s1 == s2:
        ans="Yes"
    else:
        ans ="No"
print(ans)
H, W = (int(i) for i in input().split())
t = []
t.append(['.']*(H+2))

for j in range(H):
	tmp = input()
	tmp = '.' + tmp + '.'
	t.append(list(tmp))

t.append(['.']*(H+2))

def CheckBlock(i,k):
	if t[i][k-1] == '#': #check up
		return 0
	elif t[i-1][k] == '#': #check left
		return 1
	elif t[i+1][k] == '#': #check right
		return 2
	elif t[i][k+1] == '#': #check down
		return 3
	else:
		return 4

for i in range(1,W+1):
	for k in range(1,H+1):
		if t[i][k] == '#':
			marker = CheckBlock(i,k)
			if marker == 4:
				print('No')
				quit()
print('Yes')

### FIXED CODE ###

A,B = input().split()

if B >= A: print(int(A))
else: print((int(A)-1))
N = int(input())
A = list(map(int,input().split()))
ma = max(A)
xma = 1
for i in range(20):
    xma = xma  * 2
    if xma >= ma:
        break
ans = 0
a = 0
max_flag = False
for l in range(N):
    a = A[l]
    x = A[l]
    if max_flag:
       ma = max(A[l:N])
       xma = 1
       for i in range(20):
           xma = xma  * 2
           if xma >= ma:
               break
    if ma == A[l]:
        max_flag =True
    for j in range(l+1,N):
        a += A[j]
        x = x ^ A[j]
        if a == x:
            ans += 1
        elif a >= xma:
            break
print(ans + N)


### FIXED CODE ###

N = int(input())
S = input()
a = [0 for i in range(N)]
for i in S[1:]:
    if i == "E":
        a[0] += 1
for i,s in enumerate(S[:-1]):
    if S[i] == "E" and S[i+1] == "E":
        a[i+1] = a[i] - 1
    if S[i] == "E" and S[i+1] == "W":
        a[i+1] = a[i]
    if S[i] == "W" and S[i+1] == "E":
        a[i+1] = a[i]
    if S[i] == "W" and S[i+1] == "W":
        a[i+1] = a[i] + 1

print(min(a))
a , op, b = input().split()
if op == "+":
    print(a + b)
elif op == "-":
    print(a - b)

### FIXED CODE ###

a, op, b = input().split()

if op == "+":
    print(int(a) + int(b))
if op == "-":
    print(int(a) - int(b))
import numpy as np
n,m = map(int,input().split())
penalty = np.zeros(n)
did = np.zeros(n)
for i in range(m):
    p,s = input().split()
    p = int(p)
    if s == 'WA':
        if did[p-1]==0:
            penalty[p-1] +=1
    else:
        did[p-1]=1
penalty = penalty*did
print(int(sum(did)),int(sum(penalty)))
    

### FIXED CODE ###

n,m = map(int,input().split())
penalty = [0]*n
did = [0]*n
for i in range(m):
    p,s = input().split()
    p = int(p)
    if s == 'WA':
        if did[p-1]==0:
            penalty[p-1] +=1
    else:
        did[p-1]=1
for i in range(n):
    penalty[i]*=did[i]
print(sum(did),sum(penalty))
4
141421356 17320508 22360679 244949

### FIXED CODE ###

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

    mod_value = 10**9 + 7
    sum_ = 0
    b_sum = 0
    for i in range(len(A)-1):
        b_sum = b_sum + A[len(A)-i-1]
        sum_ = sum_ + (A[len(A)- i - 2]*b_sum) % mod_value
    print(sum_%mod_value)
main()
n = input()
l = map(int,[*n])
if int(n)%sum(l) == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = input()
l = map(int,list(n))
if int(n)%sum(l) == 0:
  print('Yes')
else:
  print('No')
b = input()
if b == A:
  print("T")
elif b == C:
  print("G")
elif b == G:
  print("C")
else:
  print("A")

### FIXED CODE ###

b = input()

if b == "A":
  print("T")
elif b == "C":
  print("G")
elif b == "G":
  print("C")
else:
  print("A")
from math import gcd

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

if K > max(A):
  print('IMPOSSIBLE')
  exit()

d = A[0]
for a in A:
  d = gcd(d,a)

if K % d == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

from fractions import gcd

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

if K > max(A):
  print('IMPOSSIBLE')
  exit()

d = A[0]
for a in A:
  d = gcd(d,a)

if K % d == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
n,m,q = map(int, raw_input().split(' ')) #2 3 -10
bis = map(int, raw_input().split(' '))
c = 0
for _ in range(m):
	if sum([u*v for u,v in zip(map(int,raw_input().split(' ')),bis)]) + q > 0:
      c+=1
print c


### FIXED CODE ###

n,m,q = map(int, raw_input().split(' ')) #2 3 -10
bis = map(int, raw_input().split(' '))
c = 0
for _ in range(n):
	if sum([u*v for u,v in zip(map(int,raw_input().split(' ')),bis)]) + q > 0:
		c+=1
print c
s = input()
l = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
for i in range(7):
    if s == l[i]:
        print(7%i)

### FIXED CODE ###

s = input()
l = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
for i in range(7):
    if s == 'SUN':
        print(7)
        break
    else:
        if s == l[i]:
            print(7-i)
import heapq

N, M = map(int, input().split())
l = [0 for i in range(N)]

for i in range(N):
    A, B = map(int, input().split())
    l[i] = [A,-B]
l.sort()

tmp = []
ans = 0

for i in range(1, M + 1):
    while l[i][0] <= i:
        heapq.heappush(tmp, l[i])
    ans -= heapq.heappop(tmp)[1]
print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
l = [0 for i in range(N)]

for i in range(N):
    A, B = map(int, input().split())
    l[i] = [A,-B]
l.sort()

tmp = []
ans = 0
j = 0

for i in range(1, M + 1):
    while j < N:
        A, B = l[j][0], -l[j][1]
        memo = [-B, A]
        if A <= i:
            heapq.heappush(tmp, memo)
            j += 1
        else:
            break
    if len(tmp) > 0:
        ans -= heapq.heappop(tmp)[0]
print(ans)
N,K=map(int, input().split())
P=list(map(int, input().split()))
C=list(map(int, input().split()))

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
#print(F)
#print(I)
#print(CN)
ans=-(10**9)*2
for i in range(N):
  cnt=C[i]
  #動かす回数が一周に満たない時
  if (K+1)<=I[i]:
    d=0
    nex=i
    for j in range(K+1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  #動かす回数が一周を超えるとき
  elif CN[i]<=0:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    acnt=cnt
    bcnt=C[i]
    syuukai=(K+1)//I[i]
    nokori=(K+1)%I[i]
    syuukai-=1
    nokori+=I[i]
    d=0
    nex=i
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      bcnt=max(d,bcnt)
    bcnt+=syuukai*CN[i]
    cnt=max(acnt,bcnt,(syuukai+1)*CN[i])
  ans=max(ans,cnt)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  R,C,K=map(int, input().split())
  M=[[0 for i in range(C)]for i in range(R)]
  for i in range(K):
    r,c,v=map(int, input().split())
    r-=1
    c-=1
    M[r][c]=v
  dp0=[[0 for j in range(C)] for i in range(R)]
  dp1=[[0 for j in range(C)] for i in range(R)]
  dp2=[[0 for j in range(C)] for i in range(R)]
  dp3=[[0 for j in range(C)] for i in range(R)]
  dp1[0][0]+=M[0][0]
  for r in range(R):
    for c in range(C):
      if 0<r:
        dp1[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c])+M[r][c],dp1[r][c])
        dp0[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c]),dp0[r][c])
      if 0<c:
        dp3[r][c]=max(dp2[r][c-1]+M[r][c],dp3[r][c],dp3[r][c-1])
        dp2[r][c]=max(dp1[r][c-1]+M[r][c],dp2[r][c],dp2[r][c-1])
        dp1[r][c]=max(dp0[r][c-1]+M[r][c],dp1[r][c],dp1[r][c-1])
        dp0[r][c]=max(dp0[r][c-1],dp0[r][c])
  ans=0
  for i in range(R):
    for j in range(C):
      ans=max(ans,dp1[i][j],dp2[i][j],dp3[i][j])
  print(ans)
if __name__ == '__main__':
    main()
seen = [0,0,0,0,0,0,0,0,0]
seen[0],seen[1],seen[2] = (map(int,input().split()))
seen[3],seen[4],seen[5] = (map(int,input().split()))
seen[6],seen[7],seen[8] = (map(int,input().split()))
over = False
N = int(input())
for x in range(N):
  num = int(input())
  if num in seen:
    seen[x] = "O"
if seen[0] == "O":
  if seen[1] == seen[2] == "O":
    over = True
  elif seen[3] == seen[6] == "O":
    over = True
  elif seen[4] == seen[8] == "O":
    over = True
elif seen[4] == "O":
  if seen[2] == seen[6] == "O":
    over = True
  elif seen[1] == seen[7] == "O":
    over = True
  elif seen[3] == seen[5] == "O":
    over = True
elif seen[8] == "O":
  if seen[6] == seen[7] == "O":
    over = True
  if seen[2] == seen[5] == "O":
    over = True
if not over:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

seen = [0,0,0,0,0,0,0,0,0]
seen[0],seen[1],seen[2] = (map(int,input().split()))
seen[3],seen[4],seen[5] = (map(int,input().split()))
seen[6],seen[7],seen[8] = (map(int,input().split()))
over = "No"
N = int(input())
for x in range(N):
  num = int(input())
  if num in seen:
    seen[seen.index(num)] = "O"
if seen[0] == "O":
  if seen[1] == "O" and seen[2] == "O":
    over = "Yes"
  if seen[3] == "O" and seen[6] == "O":
    over = "Yes"
  if seen[4] == "O" and seen[8] == "O":
    over = "Yes"
if seen[8] == "O":
  if seen[6] == "O" and seen[7] == "O":
    over = "Yes"
  if seen[2] == "O" and seen[5] == "O":
    over = "Yes"
if seen[4] == "O":
  if seen[6] == "O" and seen[2] == "O":
    over = "Yes"
  if seen[1] == "O" and seen[7] == "O":
    over = "Yes"
  if seen[3] == "O" and seen[5] == "O":
    over = "Yes"
print(over)