Harryxun/stf_run huggingface dataset:
def loc_decide(loc, w, num):
    location = [i for i in range(len(loc)) if loc[i] == num][0]
    row = location // w
    column = location % w
    return [row, column]

h, w, d = map(int, input().split())
loc = []
for _ in range(h):
    tmp = list(map(int, input().split()))
    for i in range(len(tmp)):
        loc.append(tmp[i])
n = int(input())
mem = []
for _ in range(n):
    start, end = map(int, input().split())
    dist = 0
    if start == end:
        print(dist)
        mem.append([start, end, dist])
    else:
        judge = [i for i in range(len(mem)) if mem[i][0]==start and mem[i][1]==end]
        if len(judge) >=1:
            print(mem[judge[0][2]])
        else:
            for i in range(start, end+1, d):
                if i == start:
                    prev_loc = loc_decide(loc, w, i)
                else:
                    next_loc = loc_decide(loc, w, i)
                    dist += (abs(next_loc[0]- prev_loc[0]) + abs(next_loc[1] - prev_loc[1]))
                    prev_loc = next_loc
            mem.append([start, end, dist])
            print(dist)

### FIXED CODE ###

h, w, d = map(int, input().split())
d_x = [-1] * (h*w + 1)
d_y = [-1] * (h*w + 1)
for i in range(h):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        d_x[tmp[j]] = i
        d_y[tmp[j]] = j

dist = [-1] * (h*w + 1) 
for i in range(h*w):
    j = h*w - i
    if h*w - j < d:
        dist[j] = 0
    else:
        dist[j] = dist[j+d] + abs(d_x[j+d] - d_x[j]) + abs(d_y[j+d] - d_y[j])
    
q =  int(input())
for _ in range(q):
    start, end = map(int, input().split())
    print(dist[start]- dist[end])
N=int(input())
S,T=input().split()
for i in range(N):
  print(S[i]T[i],end="")

### FIXED CODE ###

N=int(input())
S,T=input().split()
for i in range(N):
  print(S[i],T[i],sep="",end="")
n=int(input().split())
l=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  if l[i] == i+1 and l[i+1] == i+2:
    l[i]=change
    change=l[i+1]
    l[i+1]=l[i]
    cnt+=1
print(cnt)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  if l[i] == i+1:
    l[i],l[i+1]=l[i+1],l[i]
    cnt+=1
if l[-1]==n:
  cnt+=1
print(cnt)
def resolve():
    l, P = map(int, input().split())
    S = input()[::-1]

    ans = 0
    # 10^r: 2^r * 5^r の為、10と同じ素数
    if P == 2 or P == 5:
        for i in range(l):
            s = int(S[i])
            if s % P == 0:
                ans += i + 1
        return print(ans)

    cnts = [0] * (l + 1)
    cnts[0] = 1
    num, d = 0, 1
    for i in range(l):
        s = int(S[i])
        num += s * d
        d *= 10
        num %= P
        d %= P
        cnts[num] += 1

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2
    print(ans)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    l, P = map(int, input().split())
    S = input()

    ans = 0
    # 10^r: 2^r * 5^r の為、10と同じ素数
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += i + 1
        return print(ans)

    cnts = [0] * P
    cnts[0] = 1
    num, d = 0, 1
    for s in S[::-1]:
        s = int(s)
        num = (num + (s * d)) % P
        d = (10 * d) % P
        cnts[num] += 1

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2
    print(ans)


if __name__ == "__main__":
    resolve()
import sys
sys.setrecursionlimit(100000)

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 
V=[ [ 0 for i in range(W) ] for j in range(H) ]

ret=0
def dfs(x,y,current):
	global ret
	V[x][y]=1
	if current==".":
		ret+=1
	else:
		ret+=0

	for dx,dy in D:
		if 0<=x+dx<H and 0<=y+dy<W:
			if V[x+dx][y+dy]==0:
				if S[x+dx][y+dy] != current:
					if current==".":
						dfs(x+dx,y+dy,"#")
					else:
						dfs(x+dx,y+dy,".")
	return ret


ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans


### FIXED CODE ###

from collections import deque

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 


V=[ [ 0 for i in range(W) ] for j in range(H) ]


def dfs(x,y,current):
	bc=0	#black count
	wc=0	#white count
	q = deque([]) 
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.popleft()

		if current == "#":	  bc+=1
		else:  wc+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				next=S[x+dx][y+dy] 
				if V[x+dx][y+dy]==0 and current !=next:
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy,next) )

	return bc*wc




ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#" and V[x][y]==0:
			ans+=dfs(x,y, "#")

print ans
k = int(input())
s = input()

print(s if len(s) <= k else s[0:k] + '...')


### FIXED CODE ###

n = input()
n1 = int(n[-1])

hon = [2,4,5,7,9]
pon = [0,1,6,8]

if hon.count(n1):
    print('hon')
elif pon.count(n1):
    print('pon')
else:
    print('bon')
def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

### FIXED CODE ###

def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'
n = int(input())
a = [i in int(input().split())]
for  i in range(1,n+1):
    v  = a[i]
    j = i-1
    while a[j]>v and j>=0:
        a[j+1] = a[j]
        j -=1
    a[j] = v
    print(*a)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
for  i in range(n):
    v  = a[i]
    j = i-1
    while a[j]>v and j>=0:
        a[j+1] = a[j]
        j -=1

    a[j+1] = v
    print(*a)
n, m = map(int, input())

if n == m:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

if n == m:
    print("Yes")
else:
    print("No")
b

### FIXED CODE ###

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

ans = []

for i in range(N):
    mae = sum(W[:i])
    usiro = sum(W[i:]) 
    abus = abs((mae)-(usiro))
    ans.append(abus)

print(min(ans))
import math
import sys

def p(n, r):
	if n < r:
		return 1
	return math.factorial(n) // math.factorial(n - r)

def main():
	input = sys.stdin.readline
	N,K = map(int,input().split())
	E = [[] for _ in range(N)]
	MOD = 10**9+7
	#辺の定義
	for _ in range(N-1):
	  u,v = map(int,input().split())
	  u -= 1
	  v -= 1
	  E[u].append(v)
	  E[v].append(u)

	if N == 1:
		print(K)
		sys.exit()
	#colorが塗られたかどうか
	color = [-1 for _ in range(N)]
	dp = [-1 for _ in range(N)]
	#dfsで色を塗っていく
	stack = []
	color[u] = 1
	ans = K
	for i,v in enumerate(E[u]):
		stack.append(v)
		ans *= (K-i-1)
		ans %= MOD

	while stack:
		u = stack.pop()
		color[u] = 1
		length = 0
		for v in E[u]:
			if color[v] == -1:
				stack.append(v)
				length += 1
		if dp[length] == -1:
			tmp = 1
			for i in range(K-1-length,K-1):
				tmp *= i
				tmp %= MOD
			#tmp = p(K-2,length) % MOD
			ans *= tmp
			dp[length] = tmp
		else:
			ans *= dp[length]
		ans %= MOD

	#各頂点の色を出力
	print(ans%MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

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

print(min(b,a*n))
import sys
import os
f = open('../../input.txt', 'r')
sys.stdin = f

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

dp = [0]*(n-1)

for i in range(1,n-1):
    temp = 10**10
    for j in range(1, min(k+1, i+1) ):
        temp = min(temp, abs(h[i] - h[i-j]) + dp[i-j])
    dp[i] = temp

print(dp[n-2])


### FIXED CODE ###

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

dp = [0]*n

for i in range(1,n):
    temp = 10**10
    for j in range(1, min(k+1, i+1) ):
        temp = min(temp, abs(h[i] - h[i-j]) + dp[i-j])
    dp[i] = temp

print(dp[n-1])
n = int(input())

arm_list = []
for i in range(n):
    array = list(map(int, input().split()))
    a = array[0] - array[1]
    b = array[0] + array[1] - 1
    arm_list.append([a, b])

arm_list.sort(key=lambda x:x[1])


count = 1
a = arm_list[0][1]
b = arm_list[1][0]
for i in range(1, n-1):
    if a < b:
        count += 1
        a = arm_list[i][1]
        b = arm_list[i+1][0]
    else:
        b = arm_list[i+1][0]

if a < b:
    count += 1



print(count)

### FIXED CODE ###

n = int(input())

arm_list = []
for i in range(n):
    array = list(map(int, input().split()))
    a = array[0] - array[1]
    b = array[0] + array[1] - 1
    arm_list.append([a, b])

arm_list.sort(key=lambda x:x[1])

if n == 1:
    print(1)
    exit()
count = 1
a = arm_list[0][1]
b = arm_list[1][0]
for i in range(1, n-1):
    if a < b:
        count += 1
        a = arm_list[i][1]
        b = arm_list[i+1][0]
    else:
        b = arm_list[i+1][0]

if a < b:
    count += 1



print(count)
s = input()
K = int(input())
substring = []
for i in range(len(s) + 1):
	for j in range(i + 1, len(s) + 1):
		if j == i + 1:
			substring.append(s[i])
		else:
			substring.append(s[i:j])
substring.sort()
if K <= 1 or len(s) <= 1:
	print(s)
else:
	print(substring[K + 1])

### FIXED CODE ###

s = input()
K = int(input())
substr = set()
for i in range(len(s)):
    for j in range(i+1, i+K+1):
        substr.add(s[i:j])
print(sorted(substr)[K-1])
import numpy as np

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]

rcvs = np.array(rcvs, dtype = "int16")

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

rewards = np.array([[0 for _ in range(C)] for _ in range(R)], dtype="int16")


for rcv in rcvs:
    rewards[rcv[0],rcv[1]] = rcv[2]

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
dp = np.array(dp)
answer = 0

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        dp[i+1,j+1,0] = max(dp[i,j+1])
        dp[i+1,j+1,1] = dp[i+1,j+1,0] + reward
        
        for k in range(4): # move downside without selecting
            candidate = dp[i+1,j,k]
            dp[i+1,j+1,k] = max(dp[i+1,j,k], dp[i+1,j+1,k])
        for k in range(3):
            dp[i+1,j+1,k+1] = max(dp[i+1,j,k]+reward,dp[i+1,j+1,k+1])
print(max(dp[-1,-1]))

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))
temp = int(input())

if temp >= 30:
    print('Yes')
else:3
    print('No')
    

### FIXED CODE ###

temp = int(input())

if temp >= 30:
    print('Yes')
else:
    print('No')
a,b,c = list(map(int, input().split()))
k = int(input())
m = max(a,b,c)
l = m
for i in range(k):
    l *= 2
print(sum([a,b,c].remove(m))+l)

### FIXED CODE ###

a,b,c = list(map(int, input().split()))
k = int(input())
m = max(a,b,c)
l = m
for i in range(k):
    l *= 2
print(sum([a,b,c])-m+l)
# -*- coding: utf-8 -*-


def main():
    n, x = map(int, input().split())
    lst = [input() for i in range(n)]
    print(n, x)
    print(lst)
    
    d = []
    for i in range(n + 1):
        if i == 0:
            d.append(0)
        else:
            d.append(d[i - 1] + int(lst[i - 1]))
    print(d)
    
    bound = 0
    
    for n, i in enumerate(d):
        if i <= x:
            bound += 1
        else:
            break
    print(bound)




if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    n, x = map(int, input().split())
    lst = list(map(int,input().split()))
    lst = lst[:n]

    d = []
    for i in range(n + 1):
        if i == 0:
            d.append(0)
        else:
            d.append(d[i - 1] + int(lst[i - 1]))

    bound = 0

    for n, i in enumerate(d):
        if i <= x:
            bound += 1
        else:
            break
    print(bound)


if __name__ == '__main__':
    main()
N, X = map(int,input().split())
Ln = list(map(int,input().split()))
 
cnt = 1
sum = 0
 
for i in range(1, N+1):
  sum += Ln[i]
  if sum > X:
    break
  cnt += 1
 
print(cnt)

### FIXED CODE ###

N, X = map(int,input().split())
Ln = list(map(int,input().split()))
 
cnt = 1
sum = 0
 
for i in range(0, N):
  sum += Ln[i]
  if sum > X:
    break
  cnt += 1
 
print(cnt)
from scipy.misc import comb
n, k = map(int, input().split())
for i in range(1, k+1):
	print( comb(k-1, i-1, exact=True)*comb(n-k+1, i, exact=True)%(10**9+7) )


### FIXED CODE ###

from scipy.misc import comb
n, k = map(int, input().split())
for i in range(1, k+1):
	print( comb(k-1, i-1, exact=True)*comb(n-k+1, i, exact=True)%(10**9+7) )
a = input()
print('ACL'*a)

### FIXED CODE ###

a = int(input())
print('ACL'*a)
n, m = map(int,input().split())
lst = []
for _ in range(m):
    lst.append(list(map(int,input().split())))

number = [[] for _ in range(n)]
for v in lst:
    keta,num = v[0]-1,v[1]
    if not number[keta]:
        number[keta] = num
    else:
        if number[keta] != num:
            print(-1)
            exit()

if number[0] == 0:
    print(-1)
    exit()

if not number[0]:
    number[0] = [1]

for i in range(m):
    if not number[i]:
        number[i] = 0

print(''.join([str(i) for i in number]))

### FIXED CODE ###

n, m = map(int,input().split())
lst = []
for _ in range(m):
    lst.append(list(map(int,input().split())))

number = [[] for _ in range(n)]
for v in lst:
    keta,num = v[0]-1,v[1]
    if number[keta] == []:
        number[keta] = num

    if number[keta] != num:
        print(-1)
        exit()

if n == 1:
    if not number[0]:
        print(0)
    else:
        print(''.join([str(i) for i in number]))
elif n == 2:
    if number[0] == 0:
        print(-1)
        exit()
    else:
        if not number[0]:
            number[0] = 1
        if not number[1]:
            number[1] = 0
        print(''.join([str(i) for i in number]))
else:
    if number[0] == 0:
        print(-1)
        exit()
    else:
        if not number[0]:
            number[0] = 1
        if not number[1]:
            number[1] = 0
        if not number[2]:
            number[2] = 0
        print(''.join([str(i) for i in number]))
N=int(input())
X=input()
X_int=int(X, 2)


def calc(n,count):
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)


for i in range(N):
    if X[i]=="1":
        now=X_int-2**(N-1-i)
    else:
        now=X_int+2**(N-1-i)

    #print(int(nowbin, 2))
    print(calc(now,0))

### FIXED CODE ###

N=int(input())
X=input()
def calc(n,count):
    if n==0:
        return count
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)

popcount=X.count("1")
if popcount==1:
    plus=0
    for i in range(N):
        x=X[i]
        if x=="1":
            plus+=pow(2,N-i-1,popcount+1)
    for i in range(N):
        x=X[i]
        if x=="1":
            print(0)
        else:
            ans=plus+pow(2,N-i-1,popcount+1)
            ans%=(popcount+1)
            print(calc(ans,1))
    exit()


plus=0
minus=0
for i in range(N):
    x=X[i]
    if x=="1":
        plus+=pow(2,N-i-1,popcount+1)
        minus+=pow(2,N-i-1,popcount-1)
        plus%=(popcount+1)
        minus%=(popcount-1)

for i in range(N):
    x=X[i]
    if x=="1":
        ans=minus-pow(2,N-i-1,popcount-1)
        ans%=(popcount-1)
        print(calc(ans,1))

    else:
        ans=plus+pow(2,N-i-1,popcount+1)
        ans%=(popcount+1)
        print(calc(ans,1))
import math


def lcm(x, y):
  return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)
# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)
# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - A+1 - (x + y - z)
print(not_d)


### FIXED CODE ###

""" import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(int(not_d))
 """

a, b, c, d = map(int, input().split())

total = b - a + 1


def lem(A, B):
	AB = A * B
	while B != 0:
		A, B = B, A % B
	return AB // A


bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = total - bsep + asep
print(ans)
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ list(sys.stdin.readline().strip()) for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]
n = int(input())

for i in range(2,int(n**(1/2)+1)):
    divisor_lst = []
    if n%i==0:
        j = n//i
        divisor_lst.append([i,j])

n_x = divisor_lst[-1][0]
n_y = divisor_lst[-1][1]

print(n_x+n_y-2)

### FIXED CODE ###

n = int(input())

need_lst = []
for i in range(1,int(n**(1/2)+1)):
    if n%i==0:
        need = i+n//i
        need_lst.append(need-2)

print(min(need_lst))
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    for _ in range(len(array)):
        if index < 1:
            return []
        elif index <= array[_][0]:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        dp = cut(dp, a)
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))


### FIXED CODE ###

import random
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    if index < 1:
        return []
    if index <= array[0][0]:
        return [(index, array[0][1])]
    for _ in range(len(array)-1, 0, -1):
        if array[_ - 1][0] < index:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        if a <= dp[-1][0]:
            dp = cut(dp, a)
        else:
            dp += [(a, 0)]
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))
import itertools
n = int(input())
names = [input() for i in range(n)]
names = [i for i in names if i[0] in "MARCH"]


print(len(list(itertools.combinations(seq,3))))

### FIXED CODE ###

import itertools
n = int(input())
counters = {"M":0,"A":0,"R":0,"C":0,"H":0}

for _ in range(n):
  s = input()[0]
  
  if s in "MARCH":
  	counters[s] += 1
res = 0
for i in list(itertools.combinations(["M","A","R","C","H"],3)):
  res += counters[i[0]] * counters[i[1]] * counters[i[2]]

print(res)
n=int(input())
if n%9==0
 print('Yes')
else:
  print('No')

### FIXED CODE ###

n=input()
result = sum(list(map(int, str(n))))
if result%9==0:
  print('Yes')
else:
  print('No')