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

import sys
import os
import time

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    key = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
    time.sleep(1.99)
    print(7 - key.index(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    key = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
    print(7 - key.index(S))


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

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

anses = []
for i in range(n - k + 1):
  ans = 0
  for e in p[i:i + k]:
    ans += (e + 1) / 2
  anses.append(ans)
print(max(anses))


### FIXED CODE ###

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

ans = 0
for e in p[0:k]:
  ans += (e + 1) / 2
anses = [ans]

for i in range(n - k):
  ans -= (p[i] + 1) / 2
  ans += (p[k + i] + 1) / 2
  anses.append(ans)

print(max(anses))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if abs(i-j) == a[i]+a[j]:
            ans += 1
print(ans)


### FIXED CODE ###

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

L = {}
R = {}

for i in range(n):
    if i + a[i] in L:
        L[i + a[i]] = L[i + a[i]] + 1
    else:
        L[i + a[i]] = 1

    if i - a[i] in R:
        R[i - a[i]] = R[i - a[i]] + 1
    else:
        R[i - a[i]] = 1

#print(L,R,sep="\n")
ans = 0
for key in L.keys():
    if key in R:
        #print(L[key], R[key])
        ans += L[key] * R[key]
print(ans)

"""
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if abs(i-j) == a[i]+a[j]:
            ans += 1
print(ans)
"""
### BUGGY CODE ###

def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    a = max(s)-s
    dp = np.full((k+1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0
    for h in H:
        dh = d[h]
        dp2 = np.full((k+1, l), 10**13, dtype=np.int64)
        if k > 0:
            t = np.zeros((k, l), dtype=np.int64)
            s_plus_a = a+dp
            min_s = np.array([[j for j in i] for i in dp[:-1]], dtype=np.int64)
            for j in range(l-2, -1, -1):
                min_s[:, j] = np.minimum(min_s[:, j+1], min_s[:, j])
            for j in range(1, l):
                s_plus_a[:, j] = np.minimum(s_plus_a[:, j-1], s_plus_a[:, j])
            t = s_plus_a[:-1] - a
            dp2[1:, :] = np.minimum(min_s, t)
        for j in range(l):
            dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
        dp = dp2
    print(np.min(dp))


main()

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    sw = input()
    s.append([c for c in sw])

def val(s,k):
    global n
    for i in range(n):
        for j in range(n):
            if i+k >= n:
                ni = i+k-n
            elif i+k < 0:
                ni = i+k+n
            else:
                ni = i+k
            if j-k >= n:
                nj = j-k-n
            elif j-k < 0:
                nj = j-k+n
            else:
                nj = j-k

            if s[i][j] != s[nj][ni]:
                return False
    return True

res = 0
for k in range(0,n):
    if val(s,k):
        res += n
print(res)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
st=list(map(''.join,zip(*s)))

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

res = 0
for i in range(n):
    if plusa(st,i) == plusb(s,i):
        res += n

print(res)
### BUGGY CODE ###

import math, collections
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = list(map(int, input().split()))
al = collections.Counter(a)
res = [0]*(n+1)
for i in al:
    if al[i]==1:
        continue
    res[i] += combinations_count(al[i], 2)
sum_ = sum(res)
for i in a:
    if al[i]==1:
        print(sum_)
        continue
    if al[i]==2:
        print(sum_-res[i])
        continue
    print(sum_-res[i]+ combinations_count(al[i]-1, 2))

### FIXED CODE ###

import math, collections
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = list(map(int, input().split()))
al = collections.Counter(a)
res = [0]*(n+1)
dp = [0]*(n+1)
for i in al:
    if al[i]==1: 
        continue
    if dp[al[i]] == 0:
        res[i] += combinations_count(al[i], 2)
        dp[al[i]] += res[i]
    else: res[i] = dp[al[i]]
sum_ = sum(res)
for i in a:
    if al[i]==1:
        print(sum_)
        continue
    if al[i]==2:
        print(sum_-res[i])
        continue
    if dp[al[i]-1] == 0:
        dp[al[i]-1] = combinations_count(al[i]-1, 2)
        print(sum_-res[i]+ dp[al[i]-1])
    else: print(sum_-res[i]+ dp[al[i]-1])
### BUGGY CODE ###

l, r = list(map(int, input().split()))
ans = r*r
for j in range(r, l, -1):
    for i in range(j-1, l-1, -1):
        ans = min(ans, (i*j)%2019)
        if ans == 2:
            break
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
    
ans = 2019
for i in range(L, min(L+2019, R),1):
    for j in range(i+1, min(L+2019, R)+1,1):
        ans = min(ans, (i*j)%2019)

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

N,K = map(int, input().strip().split(' '))
H = list(map(int, input().strip().split(' ')))
min_cost = [float('inf')]*(N+1)
min_cost[0] = 0
for i in range(N-1):
  for k in range(1, min(K+1, N-i)):
    min_cost[i+k] = min(min_cost[i+k], min_cost[i]+abs(H[i]-H[i+k]))

print(min_cost[N-1])


### FIXED CODE ###

N,K = map(int, input().strip().split(' '))
H = list(map(int, input().strip().split(' ')))

dp = [float('inf')]*N
dp[0] = 0
for i in range(N-1):
  for d in range(1, min(K+1, N-i)):
    dp[i+d] = min(dp[i+d], dp[i]+abs(H[i+d]-H[i]))

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

S = input()
Q = int(input())
Query = []
for i in range(Q):
    Queryi = list(map(str, input().split()))
    Query.append(Queryi)
#print(S[::-1])
#print(Query)

for i in Query:
    if i[0] == '1':
        S = S[::-1]
    else: #i[0] == '2'
        if i[1] == '1':
            S = i[2] + S
        else: #i[1] == '2'
            S = S + i[2]

print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
d = deque(list(S))
tf = 1

for i in range(Q):
    Queryi = list(map(str, input().split()))
    if Queryi[0] == '1':
        tf *= -1
    else:   #Queryi[0] == '2'
        if tf == 1:
            if Queryi[1] == '1':
                d.appendleft(Queryi[2])
            else: #Queryi[1] == '0'
                d.append(Queryi[2])
        else: #tf = -1
            if Queryi[1] == '1':
                d.append(Queryi[2])
            else: #Queryi[1] == '1'
                d.appendleft(Queryi[2])

if tf == -1:
    d.reverse()

print(''.join(d))
### BUGGY CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b
for x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from pprint import pprint

MAX_bin = 20
N = int(input())
An = list(map(int, input().split()))

bin_rui = [[0 for _ in range(MAX_bin)] for _ in range(N+1)]

tmp_bin = [0 for _ in range(MAX_bin)]
for i,A in enumerate(An):
    binA = bin(A)[2:]
    tmpA = "0"*(MAX_bin - len(binA)) + binA

    for k in range(MAX_bin):
        bin_rui[i+1][k] = tmp_bin[k] + int(tmpA[k])
        tmp_bin[k] += int(tmpA[k])

# 尺取
renzoku = []
cnt = 1
l = 1
r = 1
while l <= N and r <= N:
    bin_l = bin_rui[l-1]
    bin_r = bin_rui[r]
    bin_diff = [0 for _ in range(MAX_bin)]
    # bin_r - bin_l
    for k in range(MAX_bin):
        bin_diff[k] = bin_r[k] - bin_l[k]

    if sum([1 for b in bin_diff if b > 1]) == 0:
        renzoku.append(cnt)
        cnt += 1
        r += 1
    else:
        cnt -= 1 
        l += 1

# pprint(renzoku)
print(sum(renzoku))


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
An = list(map(int, input().split()))

# 尺取
ans = 0
l = 0
r = 0
Asum = An[0]
Axor = An[0]
while l < N and r < N:
    if Asum == Axor:
        ans += r-l+1
        r += 1
        if r < N:
            Asum += An[r]
            Axor ^= An[r]
    else:
        if l < N:
            Asum -= An[l]
            Axor ^= An[l]
        l += 1

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

from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    A.sort()
    C = Counter(A)

    MAX = 2000005
    T = [0]*MAX

    ans = 0
    for a in A:
        if T[a]:
            continue
        else:
            if C[a] == 1:
                ans += 1
            for i in range(2*a, MAX, a):
                T[i] += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    C = Counter(A)

    MAX = 1000005
    T = [0]*MAX

    ans = 0
    for a in C.keys():
        if T[a]:
            continue
        else:
            for i in range(2*a, MAX, a):
                T[i] = 1

    ans = 0
    for a, n in C.items():
        if n == 1 and T[a] == 0:
            ans += 1

    print(ans)


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

from bisect import insort_left

N = int(input())
*A, = map(int, input().split())
operations = []
pos = []; zero = []; neg = [];
for a in A:
    if a > 0: insort_left(pos, a)
    elif a == 0: zero.append(a)
    else: insort_left(neg, a)
if N == 2:
    a, b = max(A), min(A)
    ans = a - b
    operations.append((a, b))
else:
    if len(neg) == 0:
        pos = zero + pos
        operations.append((pos[0], pos[-1]))
        neg = [pos[0] - pos[-1]]
        pos = pos[1:-1]
    elif len(pos) == 0:
        neg = neg + zero
        operations.append((neg[-1], neg[0]))
        pos = [neg[-1] - neg[0]]
        neg = neg[1:-1]
    else:
        neg = neg + zero
    neg = neg[::-1]
    while len(pos) > 1 and len(neg) > 1:
        n, p = neg.pop(), pos.pop()
        operations.append((p, n))
        pos.append(p-n)
    if len(neg) == 1:
        while len(pos) > 1:
            n, p = neg.pop(), pos.pop()
            operations.append((n, p))
            neg.append(n-p)
    else:
        while len(neg) > 1:
            n, p = neg.pop(), pos.pop()
            operations.append((p, n))
            pos.append(p-n)
    operations.append((pos[0], neg[0]))
    ans = pos[0] - neg[0]
print(ans)
for x, y in operations:
    print(x, y)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
operations = []
pos = []; zero = []; neg = [];
for a in A:
    if a > 0: pos.append(a)
    elif a == 0: zero.append(a)
    else: neg.append(a)
pos.sort(); neg.sort()
if N == 2:
    a, b = max(A), min(A)
    ans = a - b
    operations.append((a, b))
else:
    if len(neg) == 0:
        pos = zero + pos
        operations.append((pos[0], pos[-1]))
        neg = [pos[0] - pos[-1]]
        pos = pos[1:-1]
    elif len(pos) == 0:
        neg = neg + zero
        operations.append((neg[-1], neg[0]))
        pos = [neg[-1] - neg[0]]
        neg = neg[1:-1]
    else:
        neg = neg + zero
    neg = neg[::-1]
    while len(pos) > 1 and len(neg) > 1:
        n, p = neg.pop(), pos.pop()
        operations.append((p, n))
        pos.append(p-n)
    if len(neg) == 1:
        while len(pos) > 1:
            n, p = neg.pop(), pos.pop()
            operations.append((n, p))
            neg.append(n-p)
    else:
        while len(neg) > 1:
            n, p = neg.pop(), pos.pop()
            operations.append((p, n))
            pos.append(p-n)
    operations.append((pos[0], neg[0]))
    ans = pos[0] - neg[0]
print(ans)
for x, y in operations:
    print(x, y)
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *

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

import copy

N,M=map(int,input().split())
UV=[list(map(int,input().split())) for i in range(M)]
S,T=map(int,input().split())

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)
        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print(z//3)
                exit()
        stack.append([p,z])

print(-1)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *

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

import copy

N,M=map(int,input().split())
UV=[list(map(int,input().split())) for i in range(M)]
S,T=map(int,input().split())

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
visited1=set()
visited2=set()
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)

        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print(z//3)
                exit()
            else:
                visited.add(p)
        if z%3==1:
            if p in visited1:
                continue
            else:
                visited1.add(p)
        if z%3==2:
            if p in visited2:
                continue
            else:
                visited2.add(p)
        stack.append([p,z])

print(-1)
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
cnt = [0] * (10**6 + 1)
for a in A: cnt[a] += 1
checked = [True] * N
ans = 0
for i, a in enumerate(A):
    if not checked[i]: continue
    flag = True
    for j in range(i+1, N):
        if A[j] % a == 0:
            checked[j] = False
            if A[j] == a: flag = False
    if flag: ans += 1 
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
max_A = A[-1]
cnt = Counter(A)
admissible = [True] * (max_A + 1)
checked = [False] * (max_A + 1)
ans = 0
for a in A:
    if not admissible[a] or checked[a]: continue
    ans += 1
    i = 2
    while a * i <= max_A:
        admissible[a * i] = False
        i += 1
    checked[a] = True
    if cnt[a] > 1: ans -= 1
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
dp = [0] * N
 
for i in range(1, N):
  dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))
  
print(dp[N - 1])
 


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N
 
  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))
 
  return dp[N - 1]
 
print(solve())
### BUGGY CODE ###

n,k = (int(i) for i in input().split())
h = list(int(i) for i in input().split())
dp = [0]
for i in range(1,n):
    s = float("inf")
    for j in range(1,min(k,i)+1):
        s = min(s,dp[i-j]+abs(h[i]-h[i-j]))
    dp.append(s)
print(dp[-1])

### FIXED CODE ###

n,k = (int(i) for i in input().split())
h = list(int(i) for i in input().split())
dp = [0]
for i in range(1,n):
    s = float("inf")
    for j in range(1,min(k,i)+1):
        s = min(s,dp[i-j]+abs(h[i]-h[i-j]))
    dp.append(s)
print(dp[-1])
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

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

A = [None]*N
B = [None]*N
for i in range(N):
    a,b = list(map(int, input().split()))
    A[i] = a
    B[i] = b

INF = float('inf')
dp = [INF]*(H+1)
dp[H] = 0

for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(H,0,-1):
        aft = j - a
        if aft<=0:
            dp[0] = min(dp[0],dp[j]+b)
        else:
            dp[aft] = min(dp[aft],dp[j]+b)
print(dp[0])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

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

A = [None]*N
B = [None]*N
for i in range(N):
    a,b = list(map(int, input().split()))
    A[i] = a
    B[i] = b

INF = float('inf')
dp = [INF]*(H+1)
dp[H] = 0

for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(H,0,-1):
        aft = j - a
        if aft<=0:
            dp[0] = min(dp[0],dp[j]+b)
        else:
            dp[aft] = min(dp[aft],dp[j]+b)
print(dp[0])
### BUGGY CODE ###

import bisect

import sys
input = sys.stdin.readline

N=int(input())
S=list(input())
Q=int(input())

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
#print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        a=int(a)
        bag[S[a-1]].remove(a)
        S[a-1]=b
        bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                    cnt+=1
        print(cnt)

### FIXED CODE ###

import bisect

N=int(input())
S=list(input())
Q=int(input())

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
#print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        a=int(a)
        if S[a-1]!=b:
            bag[S[a-1]].remove(a)
            S[a-1]=b
            bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                        cnt+=1
        print(cnt)
### BUGGY CODE ###

def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    def find_double_town():
        visited_city = [0]
        first_twice = N_machi
        
        next_city = 0
        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            visited_city.append(next_city)
            if (len(visited_city) != len(set(visited_city))):
                first_twice = i + 1
                break
        
        return (next_city, first_twice)


    index_city, second_visit = find_double_town()
    if (index_city == 0):
        first_visit = 0
    else:
        next_city = 0        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            
            if (next_city == index_city):
                first_visit = i + 1
                break

    if (K_teleport >= first_visit):
        mod = (K_teleport - first_visit) % (second_visit - first_visit)
        next_city = index_city
        
    else:
        mod = K_teleport
        next_city = 0

    for i in range(mod):
        next_city = to_teleport[next_city] - 1

    ans = next_city + 1

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    visited_city = [1]
    order = [-1 for i in range(N_machi + 1)]
    order[1] = 0
    next_city = 1
    
    for i in range(N_machi):
        next_city = to_teleport[next_city - 1]
        tmp = order[next_city]
        
        if (tmp == -1):
            visited_city.append(next_city)
            order[next_city] = i + 1
        else:
            break
    
    first = order[next_city]
    len_loop = len(visited_city) - first
    
    if (K_teleport < first):
        ans = visited_city[K_teleport]
    else:
        mod = (K_teleport - first) % len_loop
        ans = visited_city[first + mod]
    
    print(ans)
        

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

table=[]
a=[9999,9999,9999]
b=[9999,9999,9999]
for i in range(3):
    table.append(list(map(int,input().split())))
    a[i]=min(table[-1])
    for j in range(3):
        b[j]=min(b[j],table[-1][j])
for q in range(a[0]+1):
    for w in range(a[1]+1):
        for e in range(a[2]+1):
            for r in range(b[0]+1):
                for t in range(b[1]+1):
                    for y in range(b[2]+1):
                        #print(q,w,e,r,t,y)
                        if q+r==table[0][0] and \
                        q+t==table[0][1] and \
                        q+y==table[0][2] and \
                        w+r==table[1][0] and \
                        w+t==table[1][1] and \
                        w+y==table[1][2] and \
                        e+r==table[2][0] and \
                        e+t==table[2][1] and \
                        e+y==table[2][2]:
                            print('Yes')
                            exit()
print('No')

### FIXED CODE ###

# coding: utf-8
data=[list(map(int,input().split())) for i in range(3)]
for i in range(101):
    for j in range(101):
        for k in range(101):
            for w in range(3):
                if not (data[0][w]-i==data[1][w]-j==data[2][w]-k):
                    break
            else:
                print('Yes')
                exit()
print('No')