Harryxun/stf_run huggingface dataset:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
def join(s):
    return ''.join(s)

###########

n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    aa,bb=ii()
    a[j],b[j]=min(aa,bb)-1,max(aa,bb)-1
table=[[0 for i in range(n)] for j in range(32)]


for k in range(n):
    table[0][k]=bisect.bisect_right(x,x[k]+l)-1
for j in range(1,32):
    for k in range(n):
        table[j][k]=table[j-1][table[j-1][k]]
for j in range(q):
    day=0
    cur=a[j]
    for k in reversed(range(32)):
        if table[k][cur]<=b[j]:
            day=(day+2**k)%mod
            cur=table[k][cur]
    print day


### FIXED CODE ###

import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
def join(s):
    return ''.join(s)

###########

n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    aa,bb=ii()
    a[j],b[j]=min(aa,bb)-1,max(aa,bb)-1
table=[[0 for i in range(n)] for j in range(32)]


for k in range(n):
    table[0][k]=bisect.bisect_right(x,x[k]+l)-1
for j in range(1,32):
    for k in range(n):
        table[j][k]=table[j-1][table[j-1][k]]
for j in range(q):
    day=0
    cur=a[j]
    for k in reversed(range(32)):
        if table[k][cur]<b[j]:
            day+=2**k
            cur=table[k][cur]
    print day+1
N = int(input())
S = list(input())
c = 0
a = 0
cw = [0] * N
cb = [0] * N
tw = 0
tb = 0
for i in range(N):
    if S[i] == '.':
        tw += 1
        cw[i] = tw
        cb[i] = tb
    else:
        tb += 1
        cb[i] = tb
        cw[i] = tw
A = cw[N]
for i in range(N):
    A = min(A, cb[i] + cw[N - 1] - cw[i])
print(A)


### FIXED CODE ###

N = int(input())
S = list(input())
c = 0
a = 0
cw = [0] * N
cb = [0] * N
tw = 0
tb = 0
for i in range(N):
    if S[i] == '.':
        tw += 1
        cw[i] = tw
        cb[i] = tb
    else:
        tb += 1
        cb[i] = tb
        cw[i] = tw
A = cw[i]
for i in range(N):
    A = min(A, cb[i] + cw[N - 1] - cw[i])
print(A)
a,b,c = map(int,input().split())
if a < b < c:
	print("Yes")
else:
	print("No"

### FIXED CODE ###

a,b,c = map(int,input().split())
if a < b < c:
	print("Yes")
else:
	print("No")
# coding: utf-8
import sys

def getMin(X, K):
    minVal = sys.maxsize
    if K == 1:
        return X[0]
    
    for l in range(0, len(X)-K):
        minVal = min(minVal, abs(X[l]) + abs(X[K + l - 1] - X[l]))
            
    return minVal

def solve(X, K):
    ans = min(getMin(X, K), getMin(X[::-1], K))
    return ans

if __name__ == "__main__":
    N, K = map(int, input().split())
    X = map(int, input().split())
    print(solve(X, K))



### FIXED CODE ###

# coding: utf-8

def getMin(X, K):
    minVal = float('inf')
    for l in range(len(X)-K+1):        
        minVal = min(minVal, abs(X[l]) + abs(X[K + l - 1] - X[l]))
        minVal = min(minVal, abs(X[K + l - 1]) + abs(X[l] - X[K + l - 1]))
    return minVal

if __name__ == "__main__":
    N, K = map(int, input().split())
    X = list(map(int, input().split()))
    print(getMin(X, K))
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(N + 1)]
a = []
t = 0
mod = 10 ** 9 + 7
for i in range(N):
  x = int(input())
  if t != x:
    table[x].append(i)
    t = x
  a.append(x)
#print(table)
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  if j < len(table[a[i]]):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
  if i + 1 < N: 
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
  #print(dp)
print(dp[-1])

### FIXED CODE ###

import sys
from bisect import bisect_left as bl
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(2 * pow(10, 5) + 1)]
a = []
t = 0
mod = 10 ** 9 + 7
for i in range(N):
  x = int(input())
  if t != x:
    table[x].append(i)
    t = x
  a.append(x)
#print(table[4], table[3])
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  k = bl(table[a[i]], i)
  if j < len(table[a[i]]) and (table[a[i]][k] == i):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
  if i + 1 < N: 
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
  #print(dp)
print(dp[-1])
from math import ceil
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

"""
目標とする最長の長さをxとして、それをk回で達成
できるか
aをソートしたので、途中でkを超えることが判明したら打ち切る
"""

def isOK(x):
    cnt = 0
    for _a in a:
        if _a<=x:
            return True
        cnt+=_a//x
        if cnt>k:
            return False
    return True

ng = 0
ok = 10**9+1

while abs(ng-ok)>0.1:
    mid = (ng+ok)/2
    if isOK(mid):
        ok = mid
    else:
        ng = mid
ok = ceil(ok)
if isOK(ok-1):
    print(ok-1)
else:
    print(ok)

### FIXED CODE ###

from math import ceil
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

"""
目標とする最長の長さをxとして、それをk回で達成
できるか
aをソートしたので、途中でkを超えることが判明したら打ち切る
"""

def isOK(x):
    cnt = 0
    for _a in a:
        if _a<=x:
            return True
        try:
            cnt+=_a//x
        except:
            return False
        if cnt>k:
            return False
    return True

ng = 0
ok = 10**9+1

while abs(ng-ok)>0.1:
    mid = (ng+ok)/2
    if isOK(mid):
        ok = mid
    else:
        ng = mid
    if ok < 1:
        break
ok = ceil(ok)
if isOK(ok-1):
    print(ok-1)
else:
    print(ok)
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        m = 0
        while s[i][m] == '.':
            a[i][m] = num
            m += 1
        if m < w:
            if s[i][j] == '#':
                a[i][m] = num
                m += 1
            for j in range(m, w):
                if s[i][j] == '#':
                    num += 1
                a[i][j] = num

if q:
    for i in q:
        m = i
        while m < h and a[m][j] == 0:
            m += 1
        if m >= h:
            m = i
            while m > 0 and a[m][j] == 0:
                m -= 1
        a[i][:] = a[m][:]
for i in range(h):
    print(*a[i][:])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = []
p = []
q = []
for i in range(h):
    s.append(input())
    if s[i].count('#') > 0:
        p.append(i)
    else:
        q.append(i)

a = [[0]*w for i in range(h)]
num = 0
if p:
    for i in p:
        num += 1
        m = 0
        while s[i][m] == '.':
            a[i][m] = num
            m += 1
        if m < w:
            if s[i][m] == '#':
                a[i][m] = num
                m += 1
            if m < w:
                for j in range(m, w):
                    if s[i][j] == '#':
                        num += 1
                    a[i][j] = num

if q:
    for i in q:
        m = i
        while m < h and a[m][0] == 0:
            m += 1
        if m >= h:
            m = i
            while m > 0 and a[m][0] == 0:
                m -= 1
        a[i][:] = a[m][:]
for i in range(h):
    print(*a[i][:])
from math import factorial
N,K = map(int, input().split())
mod = 10**9 + 7
def com(n,r):
    return int(factorial(n) / factorial(r) / factorial(n-r))
for i in range(1,K+1):
    comb = com(N-K+1,i)
    sec = com(K-1,i-1)
    print((comb * sec)%mod)

### FIXED CODE ###

from math import factorial
N,K = map(int, input().split())
mod = 10**9 + 7
def com(n,r):
    if n<r:
        return 0
    return int(factorial(n) // factorial(r) // factorial(n-r))
for i in range(1,K+1):
    comb = com(N-K+1,i)
    sec = com(K-1,i-1)
    print((comb * sec)%mod)
s = input()
ans = list(s)
alpha = [chr(i) for i in range(97, 97+26)]
if len(s) == 26 and s == "".join(alpha): print(-1)
else:
    for i in range(len(s)):
        if alpha[i] == ans[i]:
            if i == len(s) - 1:
                ans.append(alpha[i+1])
            else: continue
        else:
            ans = alpha[:i]
            ans[-1] = alpha[i]
            break
    print("".join(ans))

### FIXED CODE ###

# coding: utf-8
# Your code here!
 
S=list(input())
 
 
S=list(map(lambda x : ord(x)-97,S))
 
alpha=[0]*26
for s in S:
    alpha[s]=1
 
if len(S)!=26:
    for i in range(26):
        if alpha[i] == 0:
            S.append(i)
            ans=S[:]
            ans=list(map(lambda x :chr(x+97), ans))
            print("".join(ans))
            exit()
else:
    for i in range(26)[::-1]:
        if alpha[S[i]:].count(0)>0:
            for j in range(S[i],26):
                if alpha[j]==0:
                    ans=S[:i]+[j]
                    ans=list(map(lambda x :chr(x+97), ans))
                    print("".join(ans))
                    exit()
        else:
            alpha[S[i]]=0
 
print(-1)
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

import numpy as np
a = list(np.cumsum(a))

import bisect
print(a)

ma = bisect.bisect_right(a,a[-1]/2)+1
mi = bisect.bisect_left(a,a[-1]/2)-1

ma = ma if ma < n-1 else n-2
mi = mi if mi > 0 else 0
mid = mi+1 if n>2 else mi

print(min(abs(a[-1]-a[ma]*2), abs(a[-1]-a[mi]*2), abs(a[-1]-a[mid]*2)))

### FIXED CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

import numpy as np
a = list(np.cumsum(a))

ans = 100000000000000000

for i in range(n-1):
    ans = min(ans, abs(a[-1]-a[i]*2))

print(ans)
S = str(input())
T = str(input())
ans = 10000
for i in range(len(S)-len(T)+1):
    c = S[i:] 
    cnt = 0
    for j in range(len(T)):
        if str(T[j]) != str(c[j]):
            cnt += 1
    if cnt = 0:
        ans = 0
    elif  ans > cnt and cnt >=1:
        ans = cnt
print (ans)

### FIXED CODE ###

D, T, S =map(int, input().split())
if T >= D/S:
    print ("Yes")
else:
    print ("No")
s = input()
s = [i for i in s]
p = str()
for j in range(len(s)):
  if j < len(s):
    if s[j] == s[j + 1]:
      print('Bad')
      exit()
print('Good')

### FIXED CODE ###

s = input()
s = [i for i in s]
p = str()
for j in range(len(s) - 1):
  if s[j] == s[j + 1]:
    print('Bad')
    exit()
print('Good')
# input
A, B = map(int, input().input())

if A >= 9 or B >= 9:
    print(':(')
else:
    print('Yay')

### FIXED CODE ###

# input
A, B = map(int, input().split())

if A >= 9 or B >= 9:
    print(':(')
else:
    print('Yay!')
import math
import numpy as np
n = int(input())
a = list(map(int, input().split()))

dgt = int(math.sqrt(max(a)))+1
dp = np.zeros(dgt)

for i in range(n):
    k = np.array(list( bin(a[i])[2:].zfill(dgt)), dtype=int)
    dp += k

res = 0
for i in range(dgt):
    if dp[-i-1] > 0:
        res += 2**i*int(dp[-i-1])*int(n-dp[-i-1]) % (10**9+7)
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7

res = 0
for dig in range(61):
    one = 0
    for i in a:
        if i & (1<<dig) != 0:
            one += 1
    res = (res + one*(n-one)*(1<<dig))%MOD
print(res)
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80*4
    mid = L//2
    dp = [[[False]*(L+1) for _ in range(W+1)] for _ in range(H+1)]
    for h in range(H+1):
        dp[h][0][mid] = True
    for w in range(H+1):
        dp[0][w][mid] = True
    
    for h in range(H):
        for w in range(W):
            for l in range(L+1):
                c = A[h][w] - B[h][w]
                if 0 <= l-c <= L:
                    dp[h+1][w+1][l] = dp[h][w+1][l-c] or dp[h+1][w][l-c]
                if 0 <= l+c <= L:
                    dp[h+1][w+1][l] = dp[h+1][w+1][l] or dp[h][w+1][l+c] or dp[h+1][w][l+c]
    ans = 10**9
    for l in range(L+1):
        if dp[H][W][l]:
            ans = min(abs(l-mid), ans)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    P = W+1
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80
    dp = [[False]*(L+1) for _ in range((W+1)*(H+1))]
    dp[P+1][abs(A[0][0]-B[0][0])] = True
    
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0: continue
            c = abs(A[h][w] - B[h][w])
            for l in range(L-c+1):
                b1 = abs(l-c)
                b2 = abs(l+c)
                dp[(h+1)*P+w+1][l] = dp[h*P+w+1][b1] or dp[(h+1)*P+w][b1] or dp[h*P+w+1][b2] or dp[(h+1)*P+w][b2]

    for l in range(L+1):
        if dp[H*P+W][l]:
            print(l)
            break


if __name__ == "__main__":
    main()
import numpy as np

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

#階乗
def factorial(n):
    if n == 0:
        return 1
    else: 
        val = 1
        for i in np.arange(n)+1:
            val *= i
        return val

#組み合わせ数
def comb(a,b):
    return int(factorial(a)/factorial(b)/factorial(a-b) % (10^9 + 7))

for i in range(k):
    print(int(comb(k-1,i) * comb(n-k+1,i+1)  % (10^9 + 7)))

### FIXED CODE ###

import numpy as np

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

for i in range(k):
    print(int(comb(k-1,i, pow(10, 9) + 7) * comb(n-k+1,i+1, pow(10, 9) + 7)) % (pow(10, 9) + 7))
n,k=map(int, input().split())
a=[int(i) for in input().split()]
if n==k:
    print(1)
else:
    k-=1
    print((n+k-1)//k)

### FIXED CODE ###

n,k=map(int, input().split())
a=[int(i) for i in input().split()]
if n==k:
    print(1)
else:
    k-=1
    print((n+k-2)//k)
import operator

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

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

abs_val_dict = {}

if N == 0:
    print (X)

for i in range (X-N, X+N):
    if i not in p:
        abs_val_dict[i] = abs(i-X)
    
print(min(abs_val_dict.items(), key=operator.itemgetter(1))[0])

### FIXED CODE ###

import operator

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

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

abs_val_dict = {}

if N == 0:
    print (X)

for i in range (X-N, X+N):
    if i not in p:
        abs_val_dict[i] = abs(i-X)

if abs_val_dict != {}:
    print(min(abs_val_dict.items(), key=operator.itemgetter(1))[0])
a = int(input())
b = int(input())
op = "+" or "-"

print(a + op + b)


### FIXED CODE ###

A, op, B = input().split()

if op =="+":
    print(int(A) + int(B))
elif op == "-":
    print(int(A) - int(B))
import sys
sys.setrecursionlimit(1<<32)
def f(x,y):
    a[y][x]='0'
    for dx,dy in[[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[1,-1],[-1,1],[1,1]]:
        dx+=x;dy+=y
        if 0<=dx<w and 0<=dy<h and a[dy][dx]=='1':f(dx,dy)
while 1:
    w,h=map(int,input().split())
    if w==0:break
    a=[list(input().split()) for _ in[0]*h];b=0
    for i in range(w):
        for j in range(h):
            if a[j][i]=='1':
                b+=1;f(i,j)
    print(b)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
def f(x,y):
    if 0<=x<w and 0<=y<h and a[y][x]=='1':
        a[y][x]='0'
        for dx,dy in[[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[1,-1],[-1,1],[1,1]]:f(x+dx,y+dy)
while 1:
    w,h=map(int,input().split())
    if w==0:break
    a=[input().split() for _ in[0]*h];b=0
    for i in range(w):
        for j in range(h):
            if a[j][i]=='1':
                b+=1;f(i,j)
    print(b)
N, M= (int(i) for i in input().split())
if (N<M):
    X = list(int(i) for i in input().split())
    X.sort()
    Y = [X[i] - X[i-1] for i in range(1, len(X))].sort()
    print(sum(Y[0:M-N]))
else:
    print(0)


# -100 | -10 -3 0 2 9 | 17
# 0 | 90 97 100 102 109 | 117
#   90  7  3   2   7    6
# 90 7 7 6 3 2


"""
N個のコマ：N-1個の閉経路が存在する
各座標の距離を求める(M-1個)
M：座標の数　N:駒の数
移動しなくても通っている座標の数: N
M - N
"""



### FIXED CODE ###

N, M= (int(i) for i in input().split())
if (N<M):
    X = list(int(i) for i in input().split())
    X.sort()
    Y = [X[i] - X[i-1] for i in range(1, len(X))]
    Y.sort()
    print(sum(Y[0:M-N]))
else:
    print(0)


"""
N個のコマ：N-1個の閉経路が存在する
各座標の距離を求める(M-1個)
M：座標の数　N:駒の数
移動しなくても通っている座標の数: N
M - N
"""
import math
A, B, C, D = [int(i) for i in input().split()]
result = B+1 - A
def lcm(a, b):
    return (a * b) // math.gcd(a, b)
def wareru(min_num, max_num, waru):
    return (max_num)//waru - (min_num-1)//waru
result -= wareru(A, B, C) + wareru(A, B, D) - wareru(A, B, lcm(C,D))
print(result)

### FIXED CODE ###

import fractions
A, B, C, D = [int(i) for i in input().split()]
result = B+1 - A
def lcm(a, b):
    return (a * b) // fractions.gcd(a, b)
def wareru(min_num, max_num, waru):
    return (max_num)//waru - (min_num-1)//waru
result -= wareru(A, B, C) + wareru(A, B, D) - wareru(A, B, lcm(C,D))
print(result)
import math
N,X=map(int,input().split(" "))
x=np.array(list(map(int,input().split(' '))))
y=abs(x-X)
print(reduce(math.gcd,y))


### FIXED CODE ###

import numpy as np
from functools import reduce

def euclid(m,n):
    while n:
        m,n=n,m%n
    return m

N,X=map(int,input().split(" "))
x=np.array(list(map(int, input().split(' '))))
y=abs(x-X)
print(reduce(euclid,y))
import fractions
def func(x, y):
  tmp=fractions.gcd(x, y)
  return x*y//tmp

N, M=map(int, input().split())
if N==1:
  a=int(input())
  c=a//2
  if c>M:
    print(0)
  else:
    print(int((M/C-1)/2)+1)
  exit()

a=list(map(int, input().split()))
b=[a[i]//2 for i in range(N)]

c=func(b[0], b[1])
for i in range(2, N):
  c=func(c, b[i])
  
if c>M:
  print(0)
else:
  print(int((M/C-1)/2)+1)

### FIXED CODE ###

import fractions
def func(x, y):
  tmp=fractions.gcd(x, y)
  return x*y//tmp

N, M=map(int, input().split())
if N==1:
  a=int(input())
  c=a//2
  if c>M:
    print(0)
  else:
    print(int((M/c-1)/2)+1)
  exit()

a=list(map(int, input().split()))
b=[a[i]//2 for i in range(N)]

def f(x):
  out=0
  while x%2==0:
    out+=1
    x//=2
  return out

c=func(b[0], b[1])
for i in range(2, N):
  c=func(c, b[i])
  
p=[f(a[i]) for i in range(N)]
p.sort()
for i in range(N-1):
  if p[i]!=p[i+1]:
    print(0)
    exit()
    
if c>M:
  print(0)
else:
  print(int((M/c-1)/2)+1)
import math
a = [0]*3
for i in range(3):
    a[i] = list(map(int,input().split()))
n = int(input())
b = [0]*n
for i in range(n):
    b[i] = int(input())

for i in range(n):
    for j in range(3):
        for k in range(3):
            if a[j][k]==b[i]:
                a[j][k]=0
for i in range(3):
    if sum(a[i]) == 0:
        print("Yes")
        exit()
for i in range(3):
    if a[0][i]+a[1][i]+a[2][i] == 0 :
        print("Yes")
        exit()
if a[0][0]+a[1][1]+a[2][2] == 0:
    print("Yes")
    exit()
if a[0][2] + a[1][1] +a[2][0] == 0:
    print("Yes")
    eixt()
print("No")

### FIXED CODE ###

a = [0]*3
for i in range(3):
  a[i] = list(map(int, input().split()))
n = int(input())
b = [0]*n
for i in range(n):
  b[i] = int(input())

  
  

  
  
for i in range(n):
  for j in range(3):
    for k in range(3):
      if a[j][k] == b[i]:
        a[j][k] = 0


for i in range(3):
  if sum(a[i]) == 0:
    print("Yes")
    exit()
    
for i in range(3):
  if a[0][i] + a[1][i] + a[2][i] == 0:
    print("Yes")
    exit()
if a[0][0] + a[1][1] + a[2][2] == 0:
  print("Yes")
  exit()
if a[0][2] + a[1][1] + a[2][0] == 0:
  print("Yes")
  exit()
print("No")
def isp(str): return True if str == str[::-1] else False
a=int(input())
b=int(input())
ans=0
for i in range(a,b+1):
  i_s=str(i)
  if isp:
    ans+=1
    
print(ans)


### FIXED CODE ###

def isp(str): return True if str == str[::-1] else False
a,b= map(int, input().split())
ans=0
for i in range(a,b+1):
  i_s=str(i)
  if isp(i_s):
    ans+=1

print(ans)
H,W=map(int, input().split())
if H ==0 or W ==0:
    break
else:
    for i in range(0,H):
        for j in range (0,W):
            print("#", end="")
        print("")

### FIXED CODE ###

while True:
    H,W=map(int, input().split())
    if H ==0 and W ==0:
        break
    else:
        for i in range(0,H):
            for j in range (0,W):
                print("#", end="")
            print("")
        print("")
def c(i, p, f, g, k, vis):
    if vis[i]:
        return
    vis[i] = True
    w = f[i] + p
    k[i] = w
    ch = g[i]
    for x in ch:
        c(x, w, f, g, k, vis)


def main():
    import sys
    sys.setrecursionlimit(200000)
    n, q, *abpx = map(int, sys.stdin.read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    c(1, 0, f, g, k, vis)
    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def c(i, p, f, g, k, vis):
    if vis[i]:
        return
    vis[i] = True
    w = f[i] + p
    k[i] = w
    ch = g[i]
    for x in ch:
        c(x, w, f, g, k, vis)


def main():
    import sys
    sys.setrecursionlimit(300000)
    n, q, *abpx = map(int, sys.stdin.read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    c(1, 0, f, g, k, vis)
    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()
w = int(input())
nums = list(range(w + 1))
for _ in range(int(input())):
    a, b = map(int, input().split(", "))
    nums[a], nums[b] = nums[b], nums[a]
for x in nums[1:]:
    print(x)

### FIXED CODE ###

w = int(input())
nums = list(range(w + 1))
for _ in range(int(input())):
    a, b = map(int, input().split(","))
    nums[a], nums[b] = nums[b], nums[a]
for x in nums[1:]:
    print(x)
n = int(input())
if n % 9 == 0:
  print("Yes")
 else:
  print("No")

### FIXED CODE ###

N=int(input())
if N%9 == 0:
  print("Yes")
else:
  print("No")