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

from collections import defaultdict,deque
import copy 

N ,M ,K = [int(i) for i in input().split(' ')]
AB = defaultdict(deque)

arrive = [-1] * N

for _ in range(M):
    a, b = [int(i) for i in input().split(' ')]
    AB[a].append(b)
    AB[b].append(a)

CD = defaultdict(list)
for _ in range(K):
    c, d = [int(i) for i in input().split(' ')]
    CD[c].append(d)
    CD[d].append(c)

def DFS_size(s, Graph):
    stack = deque([s])
    global arrive
    size = 1
    tree = set()
    while stack:
        v = stack[-1]
        arrive[v-1] = 1
        tree.add(v)
        if Graph[v]:
            w = Graph[v].popleft()
            if arrive[w-1] == -1:
                if not w in stack:
                    arrive[w-1] =1
                    stack.append(w)
        else:
            stack.pop()

    return tree

tree_all =[]
tree_size = [None] *N
for i in range(1,N+1):
    if arrive[i-1] == -1:
        Graph = copy.deepcopy(AB)
        tree = DFS_size(i,Graph)
        size = len(tree)
        for t in tree:
            tree_size[t-1] = size - 1 - len(AB[t]) - sum(1 for i in CD[t] if i in tree)

print(*tree_size)


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, M, K = map(int, input().split())

def dfs(v):
    size = 1
    for w in fr[v]:
        if ~roots[w]: continue
        roots[w] = roots[v]
        size += dfs(w)
    return size

fr = defaultdict(set)
for _ in range(M):
    a, b = [int(x) -1 for x in input().split()]
    fr[a].add(b)
    fr[b].add(a)
bl = defaultdict(set)
for _ in range(K):
    a, b = [int(x) - 1 for x in input().split()]
    bl[a].add(b)
    bl[b].add(a)

roots = [-1] * N
sizes = [-1] * N

for v in range(N):
    if ~roots[v]: continue
    roots[v] = v
    sizes[v] = dfs(v)

ans = []
for v in range(N):
    w = roots[v]
    res = sizes[w] - len(fr[v]) - sum(1 for u in bl[v] if roots[u] == w) -1
    ans.append(res)

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

n, k = map(int, input().strip().split(' '))
a = list(map(str, input().strip().split(' ')))
MOD = 1000000007
# 一周期内
bn = 0
for i in range(n-1):
  for j in range(n-1-i):
    if int(a[i]) > int(a[i+j+1]):
      bn = bn + 1
# 次の周期も考える
bm = 0
for i in range(n):
  for j in range(n):
    if int(a[i]) > int(a[j]):
      bm = bm + 1
if k % 2 == 0:
  bm = (bm % MOD) * ((k // 2) % MOD) * (k-1 % MOD)
else:
  bm = (bm % MOD) * (k % MOD) * (((k-1) // 2) % MOD)
s = (bn % MOD) * (k % MOD) + (bm % MOD)
print(s % MOD)

### FIXED CODE ###

n, k = map(int, input().strip().split(' '))
a = list(map(str, input().strip().split(' ')))
MOD = 1000000007
# 一周期内
bn = 0
for i in range(n-1):
  for j in range(n-1-i):
    if int(a[i]) > int(a[i+j+1]):
      bn = bn + 1
# 次の周期も考える
bm = 0
for i in range(n):
  for j in range(n):
    if int(a[i]) > int(a[j]):
      bm = bm + 1
if k % 2 == 0:
  bm = (bm % MOD) * ((k // 2) % MOD) * (k-1 % MOD)
else:
  bm = (bm % MOD) * (k % MOD) * (((k-1) // 2) % MOD)
s = (bn % MOD) * (k % MOD) + (bm % MOD)
print(s % MOD)
### BUGGY CODE ###

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

ans=0
for i in range(n):
	del x[0]
	ans=ans+x[0]
	del x[0]
print(ans)

### FIXED CODE ###

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

ans=0
for i in range(n):
	ans=ans+x[(i*2)+1]

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

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
a, b = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()


for i in range(0, 10**7):
    if int(i * 0.08) == a and int(i * 0.1) == b:
        print(i)
        break
else:
    print(-1)


### FIXED CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
a, b = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()


for i in range(0, 10**7):
    if int(i * 0.08) == a and int(i * 0.1) == b:
        print(i)
        break
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

cost_max = 0

for i in range(2 ** N):
    x = 0
    y = 0

    for j in range(N):
        if ((i >> j) & 1) == 1:
            x += V[j]
            y += C[j]
    if cost_max < (x - y):
        cost_max = x - y

print(cost_max)



### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

cost = 0
for i in range(N):
    if V[i] > C[i]:
        cost += (V[i] - C[i])

print(cost)
### BUGGY CODE ###

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

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

p_list = []
t = zip(a, b)
ts = sorted(t)
a, b = zip(*ts)
for ai, bi in zip(a, b):
    for i in range(bi):
        p_list.append(ai)

p_list.sort()

print(p_list[k-1])




### FIXED CODE ###

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

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

p_list = []
t = zip(a, b)
ts = sorted(t)
a, b = zip(*ts)
ans = 0
count = 0
for ai, bi in zip(a, b):
    count += bi
    if count >= k:
        ans = ai
        break

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

#ABC144.C
N = int(input())
cnt = N+1
for i in range(1,N+1):
    if N % i ==0:
        S = N//i
        cnt = min(cnt,S+i)
print(cnt-2)

### FIXED CODE ###

#ABC144.C
N = int(input())
cnt = N-1
for i in range(2,int(N**0.5)+2):
    if N%i == 0:
        S = N//i + i -2
        if S <= cnt:
            cnt =S
print(cnt)
### BUGGY CODE ###

import sys
import math
import copy
a = int(input());
b = [int(input()) for i in range(a)];
c = 0;
for i in range(a):
    if max(b) > b[i]:
        print(max(b));
    elif max(b) == b[i]:
        d = copy.copy(b);
        del d[i]
        e = max(d);
        print(e);


### FIXED CODE ###

import sys
import math
import copy
a = int(input());
b = [int(input()) for i in range(a)];
c = 0;
first = max(b);
g = b.copy();
h = g.index(first);
del g[h];
second = max(g);

for i in range(a):
    if first > b[i]:
        print(first);
    elif first == b[i]:
        print(second);
### BUGGY CODE ###

# coding: utf-8


def main():
    n = int(input())
    my_polls_list = []
    for _ in range(n):
        my_polls_list.append(input())

    my_polls_set = set(my_polls_list)
    my_polls_dict = {}
    for poll in my_polls_set:
        if poll not in my_polls_dict:
            my_polls_dict[poll] = my_polls_list.count(poll)
        else:
            my_polls_dict[poll] += my_polls_list.count(poll)
    max_poll = max(my_polls_dict.values())

    for key, value in my_polls_dict.items():
        if value != max_poll:
            my_polls_set.remove(key)

    my_polls_set = sorted(my_polls_set)
    for poll in my_polls_set:
        print(poll)

    return 0


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8


def main():
    n = int(input())
    polls_dict = {}
    for _ in range(n):
        poll = input()
        if poll not in polls_dict:
            polls_dict[poll] = 1
        else:
            polls_dict[poll] += 1

    max_poll = max(polls_dict.values())
    
    polls_set = set()
    for key, value in polls_dict.items():
        if value == max_poll:
            polls_set.add(key)

    polls_set = sorted(polls_set)
    for poll in polls_set:
        print(poll)
    
    return 0


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

import sys

def main():
    N = input().strip()
    while True:
        ngram_list=[]
        #round 1
        for i in range(len(N)-1):
            ngram_list.append(N[i:i+2])
        #round 2
        if "ST" in ngram_list:
            idx=ngram_list.index("ST")
            if idx+2 > len(N):
                N = N[:idx]
            else:
                N=N[:idx]+N[idx+2:]
        else:
            return print(len(N))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = input().strip()
    stack = []
    for s in N:
        if len(stack)==0:
            stack.append(s)
        elif stack[-1]=="S" and s=="T":
            stack.pop()
        else:
            stack.append(s)
    print(len(stack))


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

K = int(input())
def pregcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
def gcd(a, b, c):
    d = pregcd(a, pregcd(b, c))
    return d

count = 0
for n in range(1, K+1):
    for m in range(1, K+1):
        for l in range(1, K+1):
            count += gcd(n, m, l)
print(count)

### FIXED CODE ###

K = int(input())
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
count = 0
temp = list()
for n in range(1, K+1):
    for m in range(1, n):
        temp.append(gcd(n, m))
for l in range(1, K+1):
    for j in range(len(temp)):
        p = gcd(l, temp[j])
        count += 2 * p
    for k in range(1, K+1):
        q = gcd(l, k)
        count += q
print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        mda = md[: (n - 1) % K]
        roop = (n - 1) // K
        res = (
            n
            - 1
            - (x % m + sum(md) * roop + sum(mda)) // m
            - md.count(0) * roop
            - mda.count(0)
        )
        print(res)


main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()
### BUGGY CODE ###

import sys

def dijkstra(m, start, goal, matrix):
  defnode = {}
  cost = [sys.maxint for i in xrange(m+1)]
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print cost[goal]
      return
    node = minnode

while True:
  n, m = map(int, raw_input().split())
  if n == 0 and m == 0:
    break
  cost = [[sys.maxint for i in xrange(m+1)] for j in xrange(m+1)]
  time = [[sys.maxint for i in xrange(m+1)] for j in xrange(m+1)]
  for i in xrange(n):
    a, b, c, t = map(int, raw_input().split())
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(raw_input())
  for i in xrange(k):
    p, q, r = map(int, raw_input().split())
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)

### FIXED CODE ###

import sys

def dijkstra(m, start, goal, matrix):
  defnode = [False] * (m+1)
  cost = [sys.maxint] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print cost[goal]
      return
    node = minnode

while True:
  n, m = map(int, raw_input().split())
  if n == 0 and m == 0:
    break
  cost = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  time = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  for i in xrange(n):
    a, b, c, t = map(int, raw_input().split())
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(raw_input())
  for i in xrange(k):
    p, q, r = map(int, raw_input().split())
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)
### BUGGY CODE ###

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

while True:
    a=n
    if (n-k)>0:
        n=n-k
        a=n
    else:
        b=n-k
        break
   
if abs(a)>abs(b):
    print(str(abs(b)))
else:
    print(str(abs(a)))


### FIXED CODE ###

n,k=map(int,input().split())
a=n
b=(n//k)
c=n-k*b
d=c-k

  
if abs(c)>abs(d):
    print(str(abs(d)))
else:
    print(str(abs(c)))
### BUGGY CODE ###

N, Q = map( int, input().split())
s = input()
TD = [list( input().split()) for _ in range(Q)]
l = -1
r = N
while r-l >= 2:
    m = (l+r)//2
    now = m
    fall = False
    for i in range(Q):
        t, d = TD[i]
        if d == "L":
            if s[now] == t:
                if now == 0:
                    fall = True
                    break
                now -= 1
        else:
            if s[now] == t:
                # if now = N-1:
                #     fall = True
                #     break
                if not now == N-1:
                    now += 1
    if fall == True:
        l = m
    else:
        r = m
L = l
l = max(L-2,-1)
r = N
while r-l >= 2:
    m = (l+r)//2
    now = m
    fall = False
    for i in range(Q):
        t, d = TD[i]
        if d == "L":
            if s[now] == t:
                if not now == 0:
                    now -= 1
        else:
            if s[now] == t:
                if now == N-1:
                    fall = True
                    break
                now += 1
    if fall == True:
        r = m
    else:
        l = m
R = r
print( max(0, R - L-1))


### FIXED CODE ###

N, Q = map( int, input().split())
s = input()
TD = [list( input().split()) for _ in range(Q)]
l = -1
r = N
while r-l >= 2:
    m = (l+r)//2
    now = m
    fall = False
    for i in range(Q):
        t, d = TD[i]
        if d == "L":
            if s[now] == t:
                if now == 0:
                    fall = True
                    break
                now -= 1
        else:
            if s[now] == t:
                # if now = N-1:
                #     fall = True
                #     break
                if not now == N-1:
                    now += 1
    if fall == True:
        l = m
    else:
        r = m
L = l
l = -1
r = N
while r-l >= 2:
    m = (l+r)//2
    now = m
    fall = False
    for i in range(Q):
        t, d = TD[i]
        if d == "L":
            if s[now] == t:
                if not now == 0:
                    now -= 1
        else:
            if s[now] == t:
                if now == N-1:
                    fall = True
                    break
                now += 1
    if fall == True:
        r = m
    else:
        l = m
R = r
print( max(0, R - L-1))
### BUGGY CODE ###

def backtrack(i, j, memo):
    if (i, j) in memo:
        return 0
    memo[i, j] = True
    l1, l2 = L[i], L[j]
    count = 0
    for l3 in L[j + 1:]:
        if l3 < l1 + l2 and l2 < l1 + l3 and l1 < l2 + l3:
            count += 1
        else:
            break
    return count


if __name__ == '__main__':
    input()
    L = [int(x) for x in input().split()]
    L.sort()
    total = 0
    memo = {}
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            total += backtrack(i, j, memo)
    print(total)

### FIXED CODE ###

from bisect import bisect_left, bisect_right


def count(i, j):
    l1, l2 = L[i], L[j]
    low = l2 - l1
    high = l2 + l1
    start = bisect_right(L, low, j + 1)
    end = bisect_left(L, high, j + 1)
    return end - start


if __name__ == '__main__':
    input()
    L = [int(x) for x in input().split()]
    L.sort()
    total = 0
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            total += count(i, j)
    print(total)
### BUGGY CODE ###

s=str(input())
s=list(s)
st=["A"]
q=int(input())
ta=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    ta=ta+1
  else:
    if (temp[2]=="1" and ta%2==0) or (temp[2]=="2" and ta%2!=0):
      st.insert(0,temp[4])
    else:
      st.append(temp[4])
l=st.index("A")
ans=st[0:l]+s+st[l+1:len(st)]
if ta%2!=0:
  ans.reverse()
print("".join(ans))

### FIXED CODE ###

s=str(input())
s=list(s)
q=int(input())
sb=[0]*(q+1)
sa=[0]*(q+1)
sbi=0
sai=0
ta=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    ta=ta+1
  else:
    if (temp[2]=="1" and ta%2==0) or (temp[2]=="2" and ta%2!=0):
      sb[sbi]=temp[4]
      sbi=sbi+1
    else:
      sa[sai]=temp[4]
      sai=sai+1
lsb=sb.index(0)
lsa=sa.index(0)
sb.reverse()
ans=sb[len(sb)-lsb:len(sb)]+s+sa[0:lsa]
if ta%2!=0:
  ans.reverse()
print("".join(ans))
### BUGGY CODE ###

import sys

first = sys.stdin.readline().strip().split()
N = int(first[0])  # 数列の要素数
M = int(first[1])  # 数列の最大値
Q = int(first[2])

inp = list()

for _ in range(Q):
    inp.append(sys.stdin.readline().strip())


max_score = 0
As = list()


def loop(row, start, idx):

    global max_score

    if idx == N:
        # As.append(row)
        score = 0
        for item in inp:
            a, b, c, d = map(int, item.split())
            if row[b - 1] - row[a - 1] == c:
                score += d
        max_score = max(score, max_score)

    else:
        for i in range(start, M+1):
            loop(row + [i], i, idx+1)


loop([], 1, 0)

print(max_score)


### FIXED CODE ###

import sys

first = sys.stdin.readline().strip().split()
N = int(first[0])  # 数列の要素数
M = int(first[1])  # 数列の最大値
Q = int(first[2])

inp = list()

for _ in range(Q):
    inp.append(sys.stdin.readline().strip())


max_score = 0
As = list()


def loop(row, start, idx):

    global max_score

    if idx == N:
        # As.append(row)
        score = 0
        for item in inp:
            a, b, c, d = map(int, item.split())
            if row[b - 1] - row[a - 1] == c:
                score += d
        max_score = max(score, max_score)

    else:
        for i in range(start, M+1):
            loop(row + [i], i, idx+1)


loop([], 1, 0)

print(max_score)
### BUGGY CODE ###

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

memo = [1]
cnt = 1
to = 1
while cnt <= k:
    to = a[to-1]
    if to not in set(memo):
        memo.append(to)
        cnt += 1
    else:
        break
        
idx = memo.index(to)
kidx = ((k - len(memo))%(len(memo)-idx))
if cnt ==k:
    print(memo[-1])
else:
    print(memo[idx:][kidx])

### FIXED CODE ###

import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()
### BUGGY CODE ###

n,w = map(int,input().split())
wv_list = [map(int,input().split()) for _ in range(n)]
dp = [0]*(w+1)

for ww,vv in wv_list:
    for i in range(w, ww-1, -1):
        t = dp[i-ww] + vv
        if dp[i] < t:
            dp[i] = t
print(max(dp))

### FIXED CODE ###

n,w = map(int,input().split())
wv_list = [map(int,input().split()) for _ in range(n)]
dp = [0]*(w+1)

for ww,vv in wv_list:
    for i in range(w, ww-1, -1):
        t = dp[i-ww] + vv
        if dp[i] < t:
            dp[i] = t
print(max(dp))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int):

    res = 0
    for i in range(1,N):
        a = (N-i) % i 
        b = (N-i) // i 

        if a == 0:
            if b > i:
                res += b
            else:
                break

    print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

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

def solve(N: int):
    divisors =  make_divisors(N)
    res = 0
    for i in divisors:
        t = i-1
        if t > 0 and N // t == N % t:
            res += t
    print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

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

N = int(input())
lst = []
count = 0
for z in range(N):
    lst.append(sorted(input()))
for i in range(N):
    for j in range(i+1,N):
        if lst[i] == lst[j]:
            count += 1
print(count)

### FIXED CODE ###

T = int(input())
dct ={}
for z in range(T):
    s = "".join(sorted(input()))
    if s in dct:
        dct[s] += 1
    else:
        dct[s] = 1
v = 0
for elem in dct.values():
    v += (elem*(elem-1))//2
print(v)
### BUGGY CODE ###

import numpy as np
import itertools
a1row = np.array(list(map(int,input().split())))
a2row = np.array(list(map(int,input().split())))
a3row = np.array(list(map(int,input().split())))
flag = 'No'
L = list(range(0,101))
for a1,a2,a3 in itertools.product(L,L,L):
    if all(a1row - a1 == a2row - a2) and all(a2row - a2 == a3row - a3):
        flag = 'Yes'
        break
print(flag)


### FIXED CODE ###

import numpy as np
import itertools
a1row = np.array(list(map(int,input().split())))
a2row = np.array(list(map(int,input().split())))
a3row = np.array(list(map(int,input().split())))
amatrix = np.array([a1row,a2row,a3row])
a1a2row = amatrix[0,:]-amatrix[1,:]
a2a3row = amatrix[1,:]-amatrix[2,:]
a1a2col = amatrix[:,0]-amatrix[:,1]
a2a3col = amatrix[:,1]-amatrix[:,2]
flag1 = all(a1a2row == a1a2row[0])
flag2 = all(a2a3row == a2a3row[0])
flag3 = all(a1a2col == a1a2col[0])
flag4 = all(a2a3col == a2a3col[0])
if flag1*flag2*flag3*flag4:
    print('Yes')
else:
    print('No')