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

def solve(n,k,ar):
    MAXX = 10**9
    dp = [MAXX] * (n+1)
    dp[0] = 0
    dp[1] = 0

    for i in range(1,n+1):
        for j in range(i+1,i+k+1):
            if j <= n:
                dp[j] = min(dp[j],dp[i]+abs(ar[i]-ar[j]))
            else:
                break
    print(dp[n])





if __name__ == '__main__':
    n,k = map(int, input().split())
    ar = list(map(int, input().split()))
    ar.insert(0,0)

    solve(n,k,ar)

### FIXED CODE ###

import sys

def solve(n,k,ar):

    dp = [sys.maxsize]*n
    dp[0] = 0

    for i in range(n):
        for k in range(1,k+1):
            if i+k <= n-1:
                dp[i+k] = min(dp[i+k], dp[i] + abs(ar[i]-ar[i+k]))

    print(dp[n-1])



if __name__ == '__main__':
    n,k = map(int,input().split())
    ar = list(map(int,input().split()))

    solve(n,k,ar)
### BUGGY CODE ###

s=int(input())

li = list(map(int,input().split()))
cnt = 0
for a in range(len(li)):
    for b in range(a + 1, len(li)):
        for c in range(b + 1, len(li)):
            if ((li[a] < li[b] + li[c]) and (li[b] < li[c] + li[a]) and (li[c] < li[a] + li[b])):
                cnt += 1

print(cnt)

### FIXED CODE ###

s=int(input())

li = list(map(int,input().split()))
li.sort()
cnt = 0
import bisect
for a in range(len(li)):
    for b in range(a + 1, len(li)):
       i = bisect.bisect_left(li, li[a]+li[b])
       cnt += i - b - 1

print(cnt)
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
ks = list(map(int, input().split()))

def solve(N, S, k):
    k -= 1
    
    # i-th of these counts the thing in [ max(0, i-k), i ).
    D_counts  = [0]
    M_counts  = [0]
    DM_counts = [0]

    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == 'D':
            D += 1
        elif S[i] == 'M':
            DM += D
            M += 1
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)
    for i in range(k, N):
        if S[i-k] == 'D':
            D -= 1
            DM -= M
        elif S[i-k] == 'M':
            M -= 1

        if S[i] == 'D':
            D += 1
        elif S[i] == 'M':
            DM += D
            M += 1
            
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)

    ans = 0
    for i, c in enumerate(S):
        if c == 'C':
            ans += DM_counts[i]
    return ans

for k in ks:
    print(solve(N, S, k))
    

### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
S = input()
Q = int(input())
ks = list(map(int, input().split()))

def func(ch):
    if ch == 'D':
        return 1
    if ch == 'M':
        return 2
    if ch == 'C':
        return 3
    return 0
    
S_arr = np.array([func(ch) for ch in S], dtype = np.int32)

@njit("i8(i8, i4[:], i8)", cache = True)
def solve(N, S_arr, k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM
    for i in range(k, N):
        if S_arr[i-k] == 1:
            D -= 1
            DM -= M
        elif S_arr[i-k] == 2:
            M -= 1

        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM

    return ans

for k in ks:
    print(solve(N, S_arr, k))
### BUGGY CODE ###

N, M = tuple(map(int, input().split()))
mod = 10**9+7
broken = []
dp = []

for i in range(M):
    broken.append(int(input()))

for i in range(N+1):
    dp.append(0)

dp[0] = 1

for i in range(1, N+1):
    if (i in broken):
        continue
    if (i == 1):
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))
mod = 10 ** 9 + 7

dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    if i in A:
        continue
    if i == 1:
        dp[i] = 1
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)
### BUGGY CODE ###

N, A, B, C, D = [int(i) - 1 for i in input().strip().split(' ')]
N += 1
S = [c for c in input().strip()]


def get(a, b):
  s = S[:]
  s[a] = 'A'
  s[b] = 'B'

  return s


def is_reachable(s, a, b):
  i = a
  while i < C:
    if i + 1 <= C and s[i + 1] == '.':
      i = i + 1
    elif i + 2 <= C and s[i + 2] == '.':
      i = i + 2
    else:
      break
  is_a = i == C

  i = b
  while i < D:
    if i + 1 <= D and s[i + 1] == '.':
      i = i + 1
    elif i + 2 <= D and s[i + 2] == '.':
      i = i + 2
    else:
      break
  is_b = i == D

  return is_a, is_b


def move(s, i):
  if i + 1 < N and s[i + 1] == '.':
    return i + 1
  if i + 2 < N and s[i + 2] == '.':
    return i + 2

  return -1


def main():
  a = A
  b = B

  for _ in range(1000):
    s = get(a, b)
    is_a, is_b = is_reachable(s, a, b)
    #print(_, (is_a, is_b), s)
    if is_a and is_b:
      return True
    elif not is_a:
      b = move(s, b)
      if b < 0:
        return False
    elif not is_b:
      a = move(s, a)
      if a < 0:
        return False
    else:
      return False


print('Yes' if main() else 'No')

### FIXED CODE ###

N, A, B, C, D = [int(i) - 1 for i in input().strip().split(' ')]
N += 1
S = [c for c in input().strip()]
S += '#'


def check(current, dest):
  i = current + 1
  while True:
    if i >= dest:
      return True
    elif S[i] == '.':
      i = i + 1
    elif S[i + 1] == '.':
      i = i + 2
    else:
      return False


def passable():
  i = B
  while True:
    if i > D:
      return False
    elif S[i - 1] == '.' and S[i] == '.' and S[i + 1] == '.':
      return True
    else:
      i = i + 1


def main():
  if D > C:
    return check(B, D) and check(A, C)
  else:
    return passable() and check(A, C)


print('Yes' if main() else 'No')
### BUGGY CODE ###

import math
n, m = input().split()
N = int(n)
M = int(m)

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

for i in range(M):
    k = A.index(max(A))
    A[k] = math.floor(A[k] / 2)

print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

print(sum(range(1, int(input()))))

### FIXED CODE ###

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

def main(input_str):
    nums = list(map(int, input_str.split()))

    count = 0
    for num_1 in range(nums[0]+1):
        for num_2 in range(nums[0]+1):
            for num_3 in range(nums[0]+1):
                result = num_1 + num_2 + num_3
                if result == nums[1]:
                    count += 1

    return count


if __name__ == "__main__":
    input_str = input()
    print(main(input_str))


### FIXED CODE ###

def main(input_str):
    nums = list(map(int, input_str.split()))

    count = 0
    for num_1 in range(nums[0]+1):
        for num_2 in range(nums[0]+1):
            if 0 <= nums[1]-(num_1+num_2) <= nums[0]:
                count += 1

    return count


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

N, *L,  = [list(map(int, s.split())) for s in open(0)]
L = L[0]
i = 0
l = N[0]
cnt = 0
while l > 0 and l - 1 >= i:
    if L[i] != i + 1:
        L.pop(i)
        cnt += 1
        i = 0
    else:
        i += 1
    l = len(L)
if cnt == N[0]:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

N, *L,  = [list(map(int, s.split())) for s in open(0)]
L = L[0]
minj = 0
for l in L:
    if l == minj + 1:
        minj = l
if minj == 0:
    print(-1)
else:
    print(len(L) - minj)
### BUGGY CODE ###

a=int(input())
moji=input()
r=[]
g=[]
b=[]
for i in range(a):
    if moji[i]=="R":
        r.append(i)
    elif moji[i]=="G":
        g.append(i)
    elif moji[i]=="B":
        b.append(i)
res=len(r)*len(g)*len(b)
if len(r)==0 or len(g)==0 or len(b)==0:
    print(0)
else:
    min_len={0:r,1:g,2:b}
    if len(min_len[0])>len(min_len[1]):
        tmp=min_len[0]
        min_len[0]=min_len[1]
        min_len[1]=tmp
    if len(min_len[1])>len(min_len[2]):
        tmp=min_len[1]
        min_len[1]=min_len[2]
        min_len[2]=tmp
    if len(min_len[0])>len(min_len[1]):
        tmp=min_len[0]
        min_len[0]=min_len[1]
        min_len[1]=tmp
    a1=[]
    for i in range(3):
        a1.append(min_len[i])
    
    for i in a1[0]:
        for j in a1[1]:
            if -abs(i-j)+min(i,j) in a1[2]:
                res-=1
            if abs(i-j)+max(i,j) in a1[2]:
                res-=1
            if abs(i-j)%2==0 and  int(abs(i-j)/2)+min(i,j) in a1[2]:
                res-=1
    print(res)

### FIXED CODE ###

a=int(input())
moji=input()
r=[]
g=[]
b=[]
for i in range(a):
    if moji[i]=="R":
        r.append(i)
    elif moji[i]=="G":
        g.append(i)
    else:
        b.append(i)
res=len(r)*len(g)*len(b)
if len(r)==0 or len(g)==0 or len(b)==0:
    print(0)
else:
    for i in range(0,a-2):
      for j in range(i+1,a-1):
        if 2*j-i<a and moji[i]!=moji[j] and moji[j]!=moji[2*j-i] and moji[2*j-i]!=moji[i]:
          res-=1
    print(res)
### BUGGY CODE ###

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


### FIXED CODE ###

k,s = list(map(int,input().split()))
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <=k:
            count += 1
print(count)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())
l=list(map(int,input().split()))

dp=[float('inf')]*(N)

dp[0]=0
for i in range(1,N):
    
    for j in range(1,min(i,K)+1):

        dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))

print(dp[N-1])
    


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

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

dp=[float('inf')]*(N)

dp[0]=0
for i in range(1,N):
    
    for j in range(1,min(i,K)+1):

        dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))

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


N, M = map(int, input().split())
cities = []
prefectures = [[] for _ in range(N+1)]

for i in range(M):
  p, y = map(int, input().split())
  cities.append((y, p))

for (y, p) in sorted(cities):
  prefectures[p].append(y)

for (y, p) in cities:
  x = prefectures[p].index(y) + 1
  pid = "00000" + str(p)
  xid = "00000" + str(x)
  print(pid[::-1][:6][::-1] + xid[::-1][:6][::-1])

### FIXED CODE ###


import bisect

N, M = map(int, input().split())
cities = []
prefectures = [[] for _ in range(N+1)]

for i in range(M):
  p, y = map(int, input().split())
  cities.append((y, p))

for (y, p) in sorted(cities, key=lambda x: x[0]):
  prefectures[p].append(y)

for (y, p) in cities:
  x = bisect.bisect_right(prefectures[p], y) 
  pid = "00000" + str(p)
  xid = "00000" + str(x)
  print(pid[::-1][:6][::-1] + xid[::-1][:6][::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = input().split()

sum = 0
for i in range(N):
    for j in range(i+1, N):
        sum += int(A[i]) * int(A[j])

print(sum % (10**9 +7))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = input().split()

B = [0]
for i in range(N):
    B.append(B[i] + int(A[i]))

sum = 0
for i in range(N):
    sum += int(A[i]) * (B[N] - B[i+1])

print(sum % (10**9 + 7))
### BUGGY CODE ###

s = input()
q = int(input())
back = 1
for i in range(q):
    query = input().split()
    if query[0] == '1':
        back *= -1
    else:
        if query[1] == '1':
            if back == 1:
                s = ('').join(query[2]) + s
            else:
                s = s + ('').join(query[2])
        else:
            if back == 1:
                s = s + ('').join(query[2])
            else:
                s = ('').join(query[2]) + s
if back == -1:
    s = s[-1::-1]
print(s)

### FIXED CODE ###

import collections
s = input()
q = int(input())
back = 1
t = collections.deque()
for ss in s:
    t.append(ss)
for i in range(q):
    query = input().split()
    if query[0] == '1':
        back *= -1
    else:
        if query[1] == '1':
            if back == 1:
                t.appendleft(query[2])
            else:
                t.append(query[2])
        else:
            if back == 1:
                t.append(query[2])
            else:
                t.appendleft(query[2])
ans = ''
if back == -1:
    for i in range(len(t)):
        ans += t.pop()
else:
    for i in range(len(t)):
        ans += t.popleft()
print(ans)
### BUGGY CODE ###

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

tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

op = {i: 0 for i in range(1, n+1)}
for i in range(q):
    p, x = map(int, input().split())
    op[p] = op[p] + x

res = []
for node in op.keys():
    cnt = op[node]
    res.append(cnt)
    if node in tree:
        for i in tree[node]:
            op[i] += cnt

print(*res)

### FIXED CODE ###

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

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

op = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    op[p] += x

for root, reaf in enumerate(tree):
    for i in reaf:
        op[i] += op[root]

print(*op[1:])
### BUGGY CODE ###

from sys import stdin
n = int(input())
s = stdin.readline()
rind = []
gind = []
bind = []
ans = 0
for i in range(n):
    if s[i] == "R":
        rind.append(i+1)
    elif s[i] == "G":
        gind.append(i+1)
    else:
        bind.append(i+1)
for i in range(len(rind)):
    for j in range(len(gind)):
        for k in range(len(bind)):
            if (rind[i]+gind[j]!=2*bind[k])and(gind[j]+bind[k]!=2*rind[i])and(bind[k]+rind[i]!=2*gind[j]):
                ans += 1
print(ans)


### FIXED CODE ###

from sys import stdin
n = int(input())
s = stdin.readline()
r = 0
g = 0 
b = 0
for i in range(n):
    if s[i] == "R":
        r += 1
    elif s[i] == "G":
        g += 1
    else:
        b += 1
count1 = r*g*b
count2 = 0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if 2*j-i<=n-1:
            if (s[i] != s[j])and(s[i] != s[2*j-i])and(s[j] != s[2*j-i]):
               count2 += 1
print(count1-count2)
### BUGGY CODE ###

import math
K = int(input())
a = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for h in range(1,K+1):
      l = math.gcd(j,h)
      m = math.gcd(i,l)
      a += m
print(a)

### FIXED CODE ###

import math
K = int(input())
a = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    m = math.gcd(i,j)
    for h in range(1,K+1):
      l = math.gcd(h,m)
      a += l
print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
N, K = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 10 ** 9 + 7

def dfs(u, par):
    color_num = K - 1 if par == -1 else K - 2

    if len(graph[u]) > K:
        return 0
    
    cnt = 1
    for v in graph[u]:
        if v == par:
            continue

        cnt *= color_num
        cnt %= MOD
        color_num -= 1

    for v in graph[u]:
        if v == par:
            continue

        cnt *= dfs(v, u)
        cnt %= MOD
        
    return cnt

graph = [[] for _ in range(N)]
for u, v in edges:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

print(dfs(0, -1) * K % MOD)



### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 10 ** 9 + 7

def dfs(u, par):
    q = deque()
    q.append((u, par))
    ret = 1

    while q:
        u, par = q.pop()
        color_num = K - 1 if par == -1 else K - 2
        
        if len(graph[u]) > K:
            return 0
            
        for v in graph[u]:
            if v == par:
                continue
                
            ret *= color_num
            ret %= MOD
            color_num -= 1
            
            q.append((v, u))

    return ret

graph = [[] for _ in range(N)]
for u, v in edges:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

print(dfs(0, -1) * K % MOD)
### BUGGY CODE ###

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

m = -1
index = -1
for i in range(n-k+1):
    tmp = sum(p[i:i+k])
    if tmp > m:
        m = tmp
        index = i


def calc_exp(p):
    e = 0
    for i in range(1,p+1):
        e += i/p
    return e
        
exp = 0
for i in range(index,index+k):
    exp += calc_exp(p[i])

print(exp)


### FIXED CODE ###

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

m = sum(p[:k])
index = 0
tmp = sum(p[:k])
for i in range(n-k):
    tmp -= p[i]
    tmp += p[i+k]
    if tmp > m:
        m = tmp
        index = i+1

def calc_exp(p):
    return ((p * (p+1)) / 2) / p
        
exp = 0
for i in range(index,index+k):
    exp += calc_exp(p[i])

print(exp)
### BUGGY CODE ###

n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)

### FIXED CODE ###

n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    acc[i] %= mod
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
numlist = list(map(int, input().split()))
dic = {}
for num in numlist:
  if num not in dic:
    dic[num] = 1
  else:
    dic[num] += 1
    
ansdick = {}
for key in dic.keys():
  n = dic[key]
  ansdick[key] = [int(n*(n-1)/2),int((n-1)*(n-2)/2)]
      
for num in numlist:
  sum = 0
  for key in dic.keys():
    if num == key:
      sum += ansdick[key][1]
    else:
      sum += ansdick[key][0]
  print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
numlist = list(map(int, input().split()))
dic = {}
for num in numlist:
  if num not in dic:
    dic[num] = 1
  else:
    dic[num] += 1
    
tmpsum = 0
for value in dic.values():
  tmpsum += int(value*(value-1)/2)
ansdic = {}
for key in dic.keys():
  n = dic[key]
  ansdic[key] = tmpsum - n + 1      
    
for num in numlist:
  print(ansdic[num])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
	a,b=map(int,input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

nim = [-1 for i in range(N)]

def dfs(cur,par):
	val = 0
	for dst in g[cur]:
		if dst == par:
			continue
		val ^= dfs(dst,cur) + 1
	nim[cur] = val
	return val

dfs(0 , -1)
#print(nim)
if nim[0] == 0:
	print('Bob')
else:
	print('Alice')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
	a,b=map(int,input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

nim = [-1 for i in range(N)]

def dfs(cur,par):
	val = 0
	for dst in g[cur]:
		if dst == par:
			continue
		val ^= dfs(dst,cur) + 1
	nim[cur] = val
	return val

dfs(0 , -1)
#print(nim)
if nim[0] == 0:
	print('Bob')
else:
	print('Alice')
### BUGGY CODE ###

#a,b=map(int,input().split())
#p_3,p_4=map(int,input().split())
n=int(input())
#g=input()
#recipe=[list(input().split())for _ in range(n)]
#m=int(input())
#have=[list(input().split())for _ in range(m)]
#a=[int(input()) for _ in range(k)]
h=list(map(int,input().split()))
#b=list(map(int,input().split()))
#c=list(map(float,input().split()))
#n=int(input())
#m=[list(map(int,input().split()))for _ in range(n)]
#p=[list(input().split())for _ in range(h)]
#a=[input()for _ in range(n)]
for i in range(1,n):
    left=max(h[:i])-1
    if h[i]<left:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

#a,b=map(int,input().split())
#p_3,p_4=map(int,input().split())
n=int(input())
#g=input()
#recipe=[list(input().split())for _ in range(n)]
#m=int(input())
#have=[list(input().split())for _ in range(m)]
#a=[int(input()) for _ in range(k)]
h=list(map(int,input().split()))
#b=list(map(int,input().split()))
#c=list(map(float,input().split()))
#n=int(input())
#m=[list(map(int,input().split()))for _ in range(n)]
#p=[list(input().split())for _ in range(h)]
#a=[input()for _ in range(n)]
tmp=h[0]
for i in range(1,n):
    if tmp<h[i]:
        tmp=h[i]
        tmp-=1
    if h[i]<tmp:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

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

light_w=[[0]*w for _ in range(h)]
light_h=[[0]*w for _ in range(h)]

for i in range(w):
  cnt_up = 0
  cnt_down = 0
  for j in range(h):
    if maze[j][i] == "#":
      cnt_up=0
    else:
      light_w[j][i] += cnt_up
      cnt_up+=1

    if maze[h-j-1][i] == "#":
      cnt_down=0
    else:
      light_w[h-j-1][i] += cnt_down
      cnt_down+=1

for i in range(h):
  cnt_right = 0
  cnt_left = 0
  for j in range(w):
    if maze[i][j] == "#":
      cnt_left=0
    else:
      light_h[i][j] += cnt_left
      cnt_left+=1

    if maze[i][w-j-1] == "#":
      cnt_right=0
    else:
      light_h[i][w-j-1] += cnt_right
      cnt_right+=1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,light_h[i][j]+light_w[i][j])
print(ans+1)

### FIXED CODE ###

import re
h,w = map(int, input().split())
m=[]
d = [[0]*w for _ in range(h)]
u = [[0]*w for _ in range(h)]
for _ in range(h):
  t=[]
  for i in re.split("(#)", input()):
    if not i == "#":
      t.extend([len(i)]*len(i))
    else:
      t.append(0)
  m.append(t)

for i in range(w):
  for j in range(h):
    if m[j][i] == 0:
      d[j][i] = 0
    else:
      if j != 0:
        d[j][i] = d[j-1][i] + 1
      else:
        d[j][i] = 1

    if m[h-1-j][i] == 0:
      u[h-1-j][i] = 0
    else:
      if h-1-j == h-1:
        u[h-1-j][i] = 1
      else:
        u[h-1-j][i] = u[h-j][i] + 1
ans=0
for i in range(w):
  for j in range(h):
    ans = max(ans, u[j][i]+d[j][i]+m[j][i])
print(ans - 2)
### BUGGY CODE ###

n = int(input())
lst = []
sum = 0

while n>0:
  sum += n%10
  n //= 10

if sum%9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = int(input())

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