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

def main():
  N=int(input())
  P=list(map(int,input().split()))
  sumCount=1
  for i in range(1,N):
    if(P[i]<=min(P[0:i+1])):
      sumCount=sumCount+1
  print(sumCount)
if __name__ == '__main__':
  main()

### FIXED CODE ###

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

num = p[0]
ans = 1

for i in range(1, n):
    if num >= p[i]:
        ans += 1
        num = p[i]

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

import bisect
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    b, c = [int(i) for i in input().split()]
    idx = bisect.bisect_left(a, c)
    if idx <= b:
        a[:idx] = [c for _ in range(idx)]
    else:
        a[:b] = [c for _ in range(b)]
        a[:idx] = a[b:idx] + a[:b]
print(sum(a))


### FIXED CODE ###

import bisect
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
d = []
cnt = 1
for i in range(n-1):
    if a[i+1] == a[i]:
        cnt += 1
    else:
        d.append([a[i], cnt])
        cnt = 1
d.append([a[n-1], cnt])


for i in range(m):
    b, c = [int(i) for i in input().split()]
    d.append([c, b])
d.sort(reverse=True)
ans = 0
j = 0
for i in range(n):
    if d[j][1] > 0:
        ans += d[j][0]
        d[j][1] -= 1
    if d[j][1] == 0:
        j += 1
print(ans)
### BUGGY CODE ###

import math
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if l[i] + l[j] > l[k]:
        ans += 1
        continue
      else:
        break

print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
count = 0
l = sorted(l)

for i in range(n-2):
  for j in range(i+1, n-1):
    k = bisect.bisect_left(l, l[i]+l[j])
    count += k -j - 1
print(count)
### BUGGY CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
  for j in range(k+1):
    for k in range(k+1):
      result = i + j + k
      if result == s:
        count += 1
print(count)

### FIXED CODE ###

line = input().split(" ")
k = int(line[0])
s = int(line[1])
count = 0
for i in range(k+1):
  for j in range(k+1):
    if s - i - j <= k and s - i - j >= 0:
      count += 1
print(count)
### BUGGY CODE ###

import copy
N = int(input())
X = list(map(int, input().split()))
for i in range(N):
    delX = copy.copy(X)
    delX.remove(X[i])
    delX.sort()
    print(delX[N // 2 - 1])
    # print(delX)
# print(N, X)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
for x in X:
    if x <= Y[N // 2 - 1]:
        print(Y[N // 2])
    else:
        print(Y[N // 2 - 1])
### BUGGY CODE ###

N = int(input())
ans = [0] * 10050

for x in range(1, 1105):
    for y in range(1, 1105):
        for z in range(1, 1105):

            f = x**2 + y**2 + z**2 + x*y + y*z + z*x

            if f < 10000:
                ans[f-1] = ans[f-1] + 1 


for i in range(N):
    print(ans[i])

### FIXED CODE ###

N = int(input())
ans = [0] * 10050

for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):

            f = x**2 + y**2 + z**2 + x*y + y*z + z*x

            if f < 10050:
                ans[f-1] = ans[f-1] + 1 


for i in range(N):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
heihou = [i ** 2 for i in range(N+1) if i**2 <= N]
print(heihou[-1])


### FIXED CODE ###

import math

N = int(input())

while math.sqrt(N) % 1 != 0:
    N -= 1

print(N)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N = int(input())
L = np.sort(np.array(list(map(int, input().split()))))

ans = 0
for i in range(N):
    for j in range(i + 1, N - 1):
        t = np.count_nonzero(L[j + 1:] < L[i] + L[j])
        if not t:
            continue
        else:
            ans += t

print(ans)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = index - j - 1
        ans += n

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

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
C = [0] + list(map(int, input().split()))
Ans = [0] * Q
sq = 1000
LR = list(map(int, sys.stdin.read().split()))
L = LR[::2]
R = LR[1::2]
B = [(l>>9<<20)|r for l, r in zip(L, R)]
Order = sorted(range(Q), key=lambda x: B[x])

pl = pr = 0
ans = 0
A = [0] * (N+1)
for idx_LR in Order:
    l = L[idx_LR]
    r = R[idx_LR]
    while pr < r:
        pr += 1
        c = C[pr]
        if A[c] == 0:
            ans += 1
        A[c] += 1
    while pl > l:
        pl -= 1
        c = C[pl]
        if A[c] == 0:
            ans += 1
        A[c] += 1
    while pr > r:
        c = C[pr]
        A[c] -= 1
        if A[c] == 0:
            ans -= 1
        pr -= 1
    while pl < l:
        c = C[pl]
        A[c] -= 1
        if A[c] == 0:
            ans -= 1
        pl += 1
    Ans[idx_LR] = ans
print("\n".join(map(str, Ans)))


### FIXED CODE ###

import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Idx = (L>>9&1).astype(np.bool)
    B[Idx] = L[Idx]>>9<<20|(1<<20)-R[Idx]
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0
table[0][0] = 1
dd = 1
for c in s[::-1]:
    dd = (10 ** d) % 13
    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * dd) % 13] += table[d][i]
    else:
        c = int(c)
        for i in range(13):
            table[d + 1][(i + c * dd) % 13] += table[d][i]
    d += 1
print(table[d][5] % mod)

### FIXED CODE ###

s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(map(lambda x:False if x=='#' else True ,input())) for i in range(H)]

L=[[0]*W for i in range(H)]
R=[[0]*W for i in range(H)]
D=[[0]*W for i in range(H)]
U=[[0]*W for i in range(H)]


for i in range(H):
	for j in range(1,W):
		if A[i][j]:
			L[i][j]=int(A[i][j-1])+L[i][j-1]

for i in range(H):
	for j in range(W-1)[::-1]:
		if A[i][j]:
			R[i][j]=int(A[i][j+1])+R[i][j+1]

for i in range(1,H):
	for j in range(W):
		if A[i][j]:
			U[i][j]=int(A[i-1][j])+U[i-1][j]


for i in range(H-1)[::-1]:
	for j in range(W):
		if A[i][j]:
			D[i][j]=int(A[i+1][j])+D[i+1][j]

ans=0
for i in range(H):
	for j in range(W):
		ans=max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]+1)

print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(lambda x:False if x=='#' else True ,input())) for i in range(H)]

L=[[0]*W for i in range(H)]
R=[[0]*W for i in range(H)]
D=[[0]*W for i in range(H)]
U=[[0]*W for i in range(H)]


for i in range(H):
	for j in range(1,W):
		if A[i][j]:
			L[i][j]=int(A[i][j-1])+L[i][j-1]

for i in range(H):
	for j in range(W-1)[::-1]:
		if A[i][j]:
			R[i][j]=int(A[i][j+1])+R[i][j+1]

for i in range(1,H):
	for j in range(W):
		if A[i][j]:
			U[i][j]=int(A[i-1][j])+U[i-1][j]


for i in range(H-1)[::-1]:
	for j in range(W):
		if A[i][j]:
			D[i][j]=int(A[i+1][j])+D[i+1][j]

ans=0
for i in range(H):
	for j in range(W):
		ans=max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]+1)

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

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

dp = [0]*N
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2,N):
  index = i - K
  if index < 0: index = 0
  ans = 10**9
  for j in range(index,i):
    ans = min(ans,dp[j] + abs(h[i] - h[j]))
  dp[i] = ans
print(dp[N-1])

### FIXED CODE ###

def main():
  N,K= map(int,input().split())
  h = list(map(int,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])

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

#abc055 b 
n=int(input())
ans=1
for i in range(1,n+1):
    ans*=i 
mod=10**9+7
print(ans%mod)

### FIXED CODE ###

#abc055 b
n=int(input())
ans=1
mod=10**9+7
for i in range(1,n+1):
    ans*=i
    ans=ans%mod

print(ans%mod)
### BUGGY CODE ###

N = int(input())
li = range(1, N)
print(sum(li))

### FIXED CODE ###

N = int(input())
print((1 + (N - 1)) * (N - 1) // 2)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)

def main():
    N = int(input())
    a = list(map(int,input().split()))
    memo = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        memo[i][i] = a[i]
    
    def point(x,y):
        if memo[x][y] != -1:
            return memo[x][y]
        else:
            ret = max(a[x]-point(x+1,y),a[y]-point(x,y-1))
            memo[x][y] = ret
            return ret
            
    point(0,N-1)
    print(memo[0][N-1])
   
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))
    dp = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = a[i]
    
    for i in range(N-1,-1,-1):
        for j in range(i,N):
            if dp[i][j] != -1:
                continue
            dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])
            
    print(dp[0][-1])
   
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

N, M, Q = map(int, input().split())

# LRi = []
Xi = np.zeros((N+1,N+1),dtype=np.int32)
for i in range(M):
    L, R = map(int, input().split())
    # LRi.append((L,R))
    Xi[L][R] += 1

pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

# for (L,R) in LRi:
#     Xi[L][R] += 1

# print(Xi)

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for (p, q) in pqi:
    tmp = 0
    for l in range(p,q+1):
        tmp += Ci[l][q] - Ci[l][p-1]

    print(tmp)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# import numpy as np

N, M, Q = map(int, input().split())

# Xi = np.zeros((N+1,N+1),dtype=np.int32)
Xi = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1

# Ci = np.zeros((N+1,N+1),dtype=np.int32)
Ci = [[0]*(N+1) for i in range(N+1)]
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp

# print(Ci)

pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

for (p, q) in pqi:
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    print(tmp)
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for i in range(0, N)])

# DPテーブル
dp = np.zeros((N+1, W+1), dtype=int)


def solve():
    for n in range(N - 1, -1, -1):
        for w in range(0, W + 1):
            if w < wv[n, 0]:
                dp[n, w] = dp[n + 1, w]
            else:
                dp[n, w] = max(dp[n+1, w], dp[n+1, w - wv[n, 0]] + wv[n, 1])

    print(dp[0, W])


def main():
    solve()


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


### FIXED CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))
### BUGGY CODE ###

def solve():
    K = int(input())
    K_one = K % 10
    cnt = 0

    carry = 0
    carry_one = carry % 10

    while True:
        is_ok = False
        for i in range(0,9+1):
            if (i * K_one + carry_one) % 10 == 7:
                is_ok = True
                cnt += 1
                carry = (K * i + carry) // 10
                carry_one = carry % 10
                break
        
        if not is_ok:
            print(-1)
            return
        
        carry_str = str(carry)
        if carry_str.count('7') == len(carry_str):
            print(len(carry_str) + cnt)
            return
    
if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve(K):
    K_one = K % 10
    cnt = 0

    carry = 0
    carry_one = carry % 10

    while True:
        is_ok = False
        for i in range(0,9+1):
            if (i * K_one + carry_one) % 10 == 7:
                is_ok = True
                cnt += 1
                carry = (K * i + carry) // 10
                carry_one = carry % 10
                break
        
        if not is_ok:
            print(-1)
            return
        
        if carry == 0:
            print(cnt)
            return

        carry_str = str(carry)
        if carry_str.count('7') == len(carry_str):
            print(len(carry_str) + cnt)
            return
    
if __name__ == '__main__':
    K = int(input())
    solve(K)
### BUGGY CODE ###

import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])

begin = 0
last = XH[begin][0] + 2*D

# これより手前までを減らす
end = bisect.bisect_right(X, last)

while True:
    need = counting(XH[begin][1])
    ans += need
    

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break







"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

### FIXED CODE ###

import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    if hp < 0:
        return 0
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)









"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""
### BUGGY CODE ###

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

Alist = [int(i) for i in input().split(' ')]
import math

#print(Alist)
my_list = [9,8,7,4,7,1,3]

Alist=sorted(Alist, reverse=True)

def insert_list(list, value):
	start=0
	end=len(list)-1

	if value<list[len(list)-1]:
		list.insert(len(list), value)
		return list
	if value>list[0]:
		list.insert(0, value)
		return list
	while True:
		mid_point=int((start+end)/2)
		if value>list[mid_point]:
			if (end-start)<2:
				list.insert(start, value)
				return list
			else:
				end=mid_point
		else:
			if (end-start)<2:
				list.insert(end, value)
				return list
			else:
				start=mid_point

for i in range(K):
   Alist[0]=Alist[0]/2
   
   if len(Alist)>1:
      value=Alist.pop(0)
      Alist=insert_list(Alist,value)
sum=0
#print(Alist)
for i in Alist:
   sum+=math.floor(i) 
print(int(sum))

### FIXED CODE ###

from heapq import heappush, heappop
import math
 
N,M = [int(i) for i in input().split(' ')]
inputList = [int(i) for i in input().split(' ')]
list = []
 
for i in inputList:
    heappush(list, -i)
 
for _ in range(M):
    heappush(list, math.ceil(heappop(list)/2))
    
print(-sum(list))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    *N, = map(int, open(0).read().split())
    h = N[2:]
    K = N[1]
    N = N[0]

    D = [[] for i in range(0, N)]
    for i in range(0, N):
        for j in range(0, N):
            if not i == j:
                D[i].append(abs(h[i] - h[j]))
        D[i].sort()

    ans = max(h) - min(h)
    for i in range(0, N):
        tmp = sum(D[i][0:K - 1])
        if tmp < ans:
            ans = tmp

    print(ans)


main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    *N, = map(int, open(0).read().split())
    h = N[2:]
    K = N[1]
    N = N[0]

    h.sort(reverse=True)
    ans = max(h) - min(h)
    for i in range(0, N - K + 1):
        d = h[i] - h[i + K -1]
        if d < ans:
            ans = d
    print(ans)


main()
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
grid = [input() for i in range(H)]

dist = [[-1]*W for _ in range(H)]
black_cells = deque()
#黒マスの位置をblack_cellsに保持
#distの黒マスの部分に0でフラッグ
for h in range(H):
  for w in range(W):
    if grid[h][w]=="#":
      black_cells.append((h,w))
      dist[h][w] = 0
def bfs(black_cells, dist):
  count=0
  while black_cells:
    h,w = black_cells.popleft()
    count = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
          continue
        if dist[new_h][new_w] == -1:
          dist[new_h][new_w] = count+1
          black_cells.append((new_h,new_w))
  return count
print(bfs(black_cells,dist))

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
grid = [input() for i in range(H)]

dist = [[-1]*W for _ in range(H)]
black_cells = deque()
#黒マスの位置をblack_cellsに保持
#distの黒マスの部分に0でフラッグ
for h in range(H):
  for w in range(W):
    if grid[h][w]=="#":
      black_cells.append((h,w))
      dist[h][w] = 0
def bfs(black_cells, dist):
  count=0
  while black_cells:
    h,w = black_cells.popleft()
    count = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
          continue
        if dist[new_h][new_w] == -1:
          dist[new_h][new_w] = count+1
          black_cells.append((new_h,new_w))
  return count
print(bfs(black_cells,dist))
### BUGGY CODE ###

N, K = map(int, input().split())
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()

ans = 10 ** 9
for i in range(N-K+1):
    ans = min(ans, max(h[i:i+K])-min(h[i:i+K]))

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()

ans = 10 ** 9
for i in range(N-K+1):
    ans = min(ans, h[i+K-1]-h[i])

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N = int(readline())
    s = 0
    while N:
        s += N%10
        s %= 9
        N //= 10
    if s%9 == 0:
        print('Yes')
    else:
        print('No')
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N = input()
    s = 0
    for i in range(len(N)):
        s += int(N[i])
    if s%9 == 0:
        print('Yes')
    else:
        print('No')
if __name__ == '__main__':
    main()