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

import sys
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    F = [[0 for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        F[a][b] = 1
        F[b][a] = 1

    G = csgraph_from_dense(F, null_value=0)
    d, predecessors = dijkstra(G, return_predecessors=True)
    # print(d, "\n", predecessors)

    # print(type(G))
    if np.any(d[0] == np.inf):
        print("No")
        sys.exit()
    else:
        print("Yes")
        for i in range(1, N):
            print(predecessors[0][i] + 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import heapq


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]

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

    # print(adj)

    INF = 10 ** 18
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def dijkstra(s):
        color = [WHITE] * N
        d = [INF] * N
        p = [-1] * N
        d[s] = 0
        PQ = []
        heapq.heappush(PQ, (0, s))  # (距離, 頂点の番号)
        color[s] = GRAY

        while PQ:
            distance, u = heapq.heappop(PQ)
            color[u] = BLACK

            if d[u] < distance:
                continue
            # print(u)

            for j in range(len(adj[u])):
                v = adj[u][j]
                if color[v] == BLACK:
                    continue
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    p[v] = u
                    heapq.heappush(PQ, (d[v], v))
                    color[v] = GRAY

        return d, p

    d, p = dijkstra(0)
    # print(d, p)
    if INF in d[1:]:
        print("No")
        sys.exit()
    else:
        print("Yes")
        for i in range(1, N):
            print(p[i] + 1)


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

N=int(input())
 
A=list(map(int,input().split()))
 
B=max(A)
 
answer=10**9
 
for j in range(-B,B+1):
	total=0
	for i in range(len(A)):
		total=total+abs(A[i]-(i+j))
		if total>=answer:
			break;
	answer=min(total,answer)
print(answer)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
import statistics
B=[0]*N
answer=0
for i in range(N):
	B[i]=A[i]-(i+1)
med=int(statistics.median(B))

for i in range(N):
	answer+=(abs(B[i]-med))
print(answer)
### BUGGY CODE ###

n = int(input())
s = input()
res = 0
for i in range(1, n//2 + 1):
    found = False
    for j in range(0, n - i - i+1):
        s1 = s[j:j+i]
        for k in range(j+i, n-i+1):
            if s[k:k+i] == s1:
                res = i
                found = True
                #print(res, s1, s[k:k+i])
            if found:
                break
        if found:
            break
print(res)

### FIXED CODE ###

tmp = input()
my_str = input()
 
start = 0
end = 1
max_len = 0
 
while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1
print(max_len)
### BUGGY CODE ###

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

Aset = set(A)
lst = {}
for i in Aset:
    lst[i] = 0
    
for i in range(N):
    lst[A[i]] += 1

Q = int(input())

ans = []
for i in range(Q):
    B, C = map(int, input().split())
    if B in lst:
        if C in lst:
            lst[C] += lst[B]
            lst.pop(B)
        else:
            lst[C] = lst[B]
            lst.pop(B)
            
    ans_tmp = 0
    for i in lst:
        ans_tmp += i*lst[i]
    
    ans.append(ans_tmp)

for i in ans:
    print(i)


### FIXED CODE ###

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

Aset = set(A)
lst = {}
for i in Aset:
    lst[i] = 0
    
for i in range(N):
    lst[A[i]] += 1

Q = int(input())

# 最初の全てのA_iの和
ans_init = 0
for i in lst:
    ans_init += i*lst[i]

# 初期値からのプラスマイナス分
ans_pm = 0
ans = []
for i in range(Q):
    B, C = map(int, input().split())
    if B in lst:
        # 更新する前に、lst中のkeyがBの個数をBnumに記憶しておく。
        Bnum = lst[B]
        # lstを更新
        if C in lst:
            lst[C] += lst[B]
            lst.pop(B)
        else:
            lst[C] = lst[B]
            lst.pop(B)
    
        # 初期値からの増減分をここで算出。
        ans_pm += Bnum*(C-B)
        ans.append(ans_init + ans_pm)
        
    else:
        ans.append(ans_init + ans_pm)

for i in ans:
    print(i)
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x

def dfs(v,p,val):
    if p != -1:
        val[v] += val[p]
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v,val)

dfs(0,-1,val)
print(*val)


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x
stack = [(0,-1)]
while stack:
    v,p = stack.pop()
    for nv in G[v]:
        if nv == p:
            continue
        val[nv] += val[v]
        stack.append((nv,v))
# def dfs(v,p):
#     if p != -1:
#         val[v] += val[p]
#     for nv in G[v]:
#         if nv == p:
#             continue
#         dfs(nv,v)
#
# dfs(0,-1)
print(*val)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, q = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
dfs(1,0)
for i in range(1,n+1):
    print(tree_value[i])


### FIXED CODE ###

import sys
from queue import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
"""
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
"""
used = [0 for i in range(n+1)]
que = Queue()
que.put(1)
while que.qsize() != 0:
    m = que.get()
    used[m] = 1
    for i in adjacent_list[m]:
        if not used[i]:
            tree_value[i] += tree_value[m]
            que.put(i)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")
### BUGGY CODE ###

n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = [0] * n
for i in range(n-2):
  if s[i] == "A":
    if s[i+1] == "C":
      is_ac[i] = 1
   
for item in lr:
  ans = sum(is_ac[item[0]-1: item[1]])
  if s[item[1]-1] == "A":
    if item[1] != n:
      if s[item[1]] == "C":
        ans -= 1
  print(ans)

### FIXED CODE ###

n, q = [int(item) for item in input().split()]
s = input()
lr = [[int(item) for item in input().split()] for _ in range(q)]

is_ac = [0] * n
count = 0
for i in range(n-1):
  if s[i] == "A":
    if s[i+1] == "C":
      count += 1
  is_ac[i+1] = count
is_ac[-1] = count
for item in lr:
  ans = is_ac[item[1]-1] - is_ac[item[0]-1]
  print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
a,b,n = map(int,input().split())
li = []
append = li.append

#for x in range(n+1):
#    append(int((a*(x))/b) - a * int(x/b))
#print(max(li))
li = [(int((a*(x))/b) - a * int(x/b)) for x in range(n+1)]
print(max(li))

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
 
ans1 = 0
 
if N > B - 1:
    x = B-1
    print(int((A * x) / B) - A * int(x / B))
elif N <= B - 1:
    x = N
    print(int((A * x) / B) - A * int(x / B))
### BUGGY CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      cb[q] -= 1
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      ca[q] -= 1
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    ca[p] -= 1
    cb[q] -= 1
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)


### FIXED CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

def update_cnt(cnt_,r):
  cnt_[r] -= 1
  if cnt_[r]==0:
    del cnt_[r]

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      update_cnt(cb,q)
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      update_cnt(ca,q)
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    update_cnt(ca,p)
    update_cnt(cb,q)
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)
### BUGGY CODE ###

MOD=998244353
N,M,K=map(int,input().split())

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  for i in range(K+1):
    ans_k=M
    term1=powmod(M-1,N-i-1)
    term2=comb_mod(N-1,i)
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    
  print(answer)

### FIXED CODE ###

MOD=998244353
N,M,K=map(int,input().split())

inv_table = [0]+[1]
for i in range(2,K+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
elif K==N-1:
  print(powmod(M,N))
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)
### BUGGY CODE ###

N = int(input())
A = [0]
A += list(map(int, input().split()))
A += [0]
cost = [abs(A[i] - A[i+1]) for i in range(N+1)]
for i in range(1, N+1):
    print(sum(cost) - (cost[i-1] + cost[i]) + abs(A[i+1] - A[i-1]))


### FIXED CODE ###

N = int(input())
A = [0]
A += list(map(int, input().split()))
A += [0]
cost = [abs(A[i] - A[i+1]) for i in range(N+1)]
sumcost = sum(cost)
for i in range(1, N+1):
    print(sumcost - (cost[i-1] + cost[i]) + abs(A[i+1] - A[i-1]))
### BUGGY CODE ###

print(sum(i for i in range(int(input()))))

### FIXED CODE ###

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

while 1:
    n = input()
    if n==0:
        break
    w, h = map(int, raw_input().split())
    p = [map(int, raw_input().split()) for i in xrange(n)]
    s, t = map(int, raw_input().split())
    ans = 0
    for b in xrange(1, h-t+2):
        for a in xrange(w-s+2):
            cnt = 0
            for c, d in p:
                if 0 <= c-a < s and 0 <= d-b < t:
                    cnt += 1
            ans = max(ans, cnt)
    print ans

### FIXED CODE ###

while 1:
    n = input()
    if n==0:
        break
    w, h = map(int, raw_input().split())
    m = [[0]*w for i in range(h)]
    l = [[0]*(w+1) for i in range(h+1)]
    for i in xrange(n):
        x, y = map(int, raw_input().split())
        m[y-1][x-1] = 1
    for i in xrange(h):
        temp = 0
        for j in xrange(w):
            temp += m[i][j]
            l[i+1][j+1] = l[i][j+1] + temp

    s, t = map(int, raw_input().split())
    ans = 0
    for i in xrange(h-t+1):
        for j in xrange(w-s+1):
            ans = max(ans, l[i+t][j+s] - l[i][j+s] - l[i+t][j] + l[i][j])
    print ans
### BUGGY CODE ###

H, W = map(int, input().split())


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

print(ans)








### FIXED CODE ###

H, W = map(int, input().split())


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

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

n = int(input())
s = []
for i in range(n):
    t = input()
    s.append(t)

t = list(set(s))
cnt = [0 for _ in range(len(t))]
for i in range(len(t)):
    for y in s:
        if t[i] == y: cnt[i]+=1
ans = []
for i in range(len(t)):
    if cnt[i] == max(cnt):
        ans.append(t[i])
ans.sort()
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

n = int(input())
cnt = {}
for _ in range(n):
    s = input()
    if not s in cnt:
        cnt[s] = 1
    else:
        cnt[s] = cnt[s] + 1

maxv = max(cnt.values())
ans = []
for x, c in cnt.items():
    if c == maxv: ans.append(x)
ans.sort()
for x in ans:
    print(x)
### BUGGY CODE ###

n = int(input())    

s = [0]*(n+1)
for i in range(1,n+1):
    for j in range(i,n+1,i):
        s[j] += 1
ans = 0

for i in range(1,n+1):
    ans += (i * s[i])

print(ans)


### FIXED CODE ###

from numba import njit
import numpy as np


@njit("i8(i8)")
def solve(n):
    ans = 1
    res = np.ones(n + 1, dtype=np.int64)
    for i in range(2, n + 1):
        for j in range(i, n + 1, i):
            res[j] += 1
        ans += i * res[i]
    return ans


N = int(input())
print(solve(N))
### BUGGY CODE ###

import numpy as np
import sys 

readline = sys.stdin.readline 

N = int(input())
A = np.array(readline().split(), np.int64) 

for i in range(N):
    xor = 0
    for i_2 in range(N):
        if i_2 != i:
            xor = xor^A[i_2]

    print(xor, end = ' ')

### FIXED CODE ###

import numpy as np
import sys 

readline = sys.stdin.readline 

N = int(input())
A = np.array(readline().split(), np.int64)
all_xor = 0
for a in A:
    all_xor = all_xor^a

for a in A:
    xor = all_xor^a
    print(xor, end = ' ')
### BUGGY CODE ###

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

N = int(input())
A = [int(a) for a in input().split()]

# 正の数p, 負の数nに対して、p+n=N
# 全探索は2^Nで爆発

while True:
    ch = False
    for i in range(0, N-1):
        if i < N-2 and 2*A[i]+3*A[i+1]+2*A[i+2] < 0:
            A[i] *= -1
            A[i+2] *= -1
            ch = True
        if A[i] + A[i+1] < 0:
            A[i] *= -1
            A[i+1] *= -1
            ch = True
    if ch is False:
        break

print(sum(A))



### FIXED CODE ###

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

N = int(input())
A = [int(a) for a in input().split()]

# かっこいい解法版
# Ai, Ai+1を反転して-Ai,-Ai+1であるが、これを繰り返すことで、
# -Ai, Ai+1, Ai+2,....,Aj-1, -Aj というように、
# i < jとなるi,jのみを反転させ、間はそのままという操作が可能。
# ここから、負の数が偶数個であれば、全てを正にすることができる
# 負の数が奇数個であれば、絶対値が一番小さい数を残して残りを正にすればよい

ng = [a for a in A if a < 0]    # 負の数の抽出
ab = [abs(a) for a in A]    # 絶対値の和

if len(ng) % 2 == 0:
    print(sum(ab))
else:
    mn = min(ab)
    print(sum(ab)-2*mn)
### BUGGY CODE ###


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

c = [1000000000]*(N-K+10)
for i in range(N - K + 1):
    if (len(x[i:i+K]) != K):
        c[i] = 1000000000
        continue
    p = x[i:i+K]
    if min(p) < 0 and max(p) > 0:
        if p[-1] + p[-1] - p[0] < abs(p[0]) + p[-1] -p[0]:
            c[i] = (p[-1] + (p[-1] - p[0]))
        else:
            c[i] = (abs(p[0]) + p[-1] - p[0])
    elif min(p) >= 0:
        c[i] = (p[-1])
    elif max(p) <= 0:
        c[i] = (abs(p[0]))

print(min(c))


### FIXED CODE ###

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

ans = 10**18
for i in range(N - K + 1):
    p1 = x[i]
    p2 = x[i+K-1]
    lr = abs(p1) + abs(p2 - p1)
    rl = abs(p2) + abs(p1 - p2)
    if lr < rl:
        ans = min(ans,lr)
    else:
        ans = min(ans,rl)
print(ans)
### BUGGY CODE ###

import math

n = int(input())
ans = []
for x in range(1, math.ceil(n**(1/2))+1):
    for y in range(1, math.ceil(n**(1/2))+1):
        for z in range(1, math.ceil(n**(1/2))+1):
            ans.append(x**2 + y**2 + z**2 + x*y + y*z + z*x)
ans.sort()
for i in range(1, n+1):
    tmp = 0
    for x in ans:
        if x == i:
            tmp += 1
        elif x > i:
            print(tmp)
            break

### FIXED CODE ###

import math

n = int(input())
ans = []
for x in range(1, math.ceil(n**(1/2))+1):
    for y in range(1, math.ceil(n**(1/2))+1):
        for z in range(1, math.ceil(n**(1/2))+1):
            ans.append(x**2 + y**2 + z**2 + x*y + y*z + z*x)
ans.sort()
for i in range(1, n+1):
    tmp = 0
    for x in ans:
        if x == i:
            tmp += 1
        elif x > i:
            print(tmp)
            break
### BUGGY CODE ###

n = int(input())
sum = 0 
for i in range(1,2000001):
    sum += n%(10**i)
if sum%9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = input()
sum = 0 
for i in n:
    sum += int(i)
if sum%9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# coding: utf-8
import itertools
num = int(input())
lines = list(int(i) for i in input().split())
lines.sort(reverse=True)
counter = 0

comb = itertools.combinations(lines, 3)

for c in comb:
  cl = list(c)
  if cl[0] < cl[1] + cl[2]:
    counter += 1
    
print(counter)

### FIXED CODE ###

import bisect
n = int(input())
lines = list(int(i) for i in input().split())
lines.sort()
counter = 0

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

import sys
sys.setrecursionlimit(1000000)
import numpy as np

H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]

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


for y in range(H):
    for x in range(W):
        if S[y][x]=='#':
            m_horizontal[y][x]=0
        elif x==0 or m_horizontal[y][x-1]==0:
            cnt=0
            i=x
            while S[y][i]=='.':
                cnt+=1
                i+=1
                if i==W:
                    break
            m_horizontal[y][x]=cnt
        else:
            m_horizontal[y][x]=m_horizontal[y][x-1]


        if S[y][x]=='#':
            m_vertical[y][x]=0
        elif y==0 or m_vertical[y-1][x]==0:
            cnt=0
            i=y
            while S[i][x]=='.':
                cnt+=1
                i+=1
                if i==H:
                    break
            m_vertical[y][x]=cnt
        else:
            m_vertical[y][x]=m_vertical[y-1][x]

ho=np.array(m_horizontal)
ve=np.array(m_vertical)
hv=ho+ve
print(np.amax(hv)-1)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == "."

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)

for i in range(H):
    U[i] = (U[i-1]+1)*S[i]
    D[-i - 1] = (D[-i] + 1) * S[-i - 1]

for i in range(W):
    L[:, i] = (L[:, i - 1] + 1) * S[:, i]
    R[:, -i - 1] = (R[:, -i] + 1) * S[:, -i - 1]

print(np.max(D + U + R + L) - 3)