Harryxun/stf_run huggingface dataset:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i,j])
  b.append(list(s))
count=0
while len(d)!=0:
  for i in range(len(d)):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]])
    if 0<x[0]
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]])
    if x[1]<w-1
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1])
    if 0<x[1]
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1])
  count+=1
print(count-1) 


### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  t=[]
  s=input()
  for j in range(w):
    if s[j]=="#":d.append((i,j));dc+=1;t.append(1)
    else:t.append(0)
  b.append(t)
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==0:b[x[0]+1][x[1]]=1;d.append((x[0]+1,x[1]));dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==0:b[x[0]-1][x[1]]=1;d.append((x[0]-1,x[1]));dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==0:b[x[0]][x[1]+1]=1;d.append((x[0],x[1]+1));dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==0:b[x[0]][x[1]-1]=1;d.append((x[0],x[1]-1));dc+=1
  count+=1
print(count-1)
N,K=map(int,input().split())
S=input()
po=[0]
ans,q,left,right=0,0,0,0
for i in range(1,N):
	p=S[i-1]+S[i]
	if (p=='10')|(p=='01'):
		po.append(i)
po.append(len(S))
for i in range(len(po)):
	if K*2>=len(po):
		ans=po[-1]
		break
	elif (S[0]=='0')&(right<1):
		q=po[2*K]
		left=2
		right=2*K+left
	elif (S[0]=='1')&(right<1):
		q=po[2*K+1]
		left=1
		right=2*K+left
	elif right<=len(po):
		q=po[right]-po[left]+1
		left+=2
		right+=2
	elif S[-1]=='0':
		right=len(po)-1
		left=right-2*K
		q=po[right]-po[left]
		ans=max(q,ans)
		break
	else:
		right=len(po)-1
		left=right-2*K-1
		q=po[right]-po[left]
		ans=max(q,ans)
		break
	ans=max(q,ans)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
S=input()
po=[0]
X=[]
i=0
for i in range(N-1):
	if not S[i] == S[i+1]:
		po.append(i+1)
po.append(len(S))
for i in range(len(po)):
	if 2*K+1>=len(po):
		X.append(po[-1])
		break
	elif 2*K+i+1>=len(po):
		X.append(po[2*K+i]-po[i])
		break
	elif S[po[i]]=='0':
		X.append(po[2*K+i]-po[i])
	else:
		X.append(po[2*K+1+i]-po[i])
print(max(X))
def main():
    n, k = [int(i) for i in input().split()]
    num = [int(i) for  i in input().split()]
    if k >= n:
        return 0
    else:
        l = sorted(num)
        return sum(l[:-k])
print(main())


### FIXED CODE ###

def main():
    num = [int(i) for i in input().split()]
    h = num[0]
    a = num[1]
    return attack(h, a)

def attack(h,a):
    if h % a == 0:
        return h // a
    elif h % a >= 1:
        return (h//a) + 1

print(main())
a,b = map(int, input().split())
if (a<10 && b<10):
      print(a*b)
else:
      print(-1)

### FIXED CODE ###

a,b = map(int, input().split())
if (a<10 and b<10):
      print(a*b)
else:
      print(-1)
cond=input().split(" ")
n=int(cond[0])
m=int(cond[1])
q=int(cond[2])
train=[[0 for i in range(2)] for j in range(m)]
sect=[[0 for i in range(2)] for j in range(q)]

def judge(arr_m,arr_q):
    a=0
    if arr_q[0]<=arr_m[0] and arr_m[1]<=arr_q[1]:
        a=1
    return a

for i in range(m):
    train[i]=input().split(" ")
    train[i]=list(map(int,train[i]))
for i in range(q):
    sect[i]=input().split(" ")
    sect[i]=list(map(int,sect[i]))
for i in range(q):
    ans=0
    for j in range(m):
        ans+=judge(train[j],sect[i])
    print(ans)

### FIXED CODE ###

nums=input().split(" ")
print((int(nums[0])-1)*(int(nums[1])-1))
n=int(input())
L=list(map(int,input().split()))
ans=[0 for i in range(n)]

L=[i for i in L]


m=n//2
a=L[m]

for i in range(1,(n+1)/2):
  a=L[m-i]+L[m+1]-a

ans[0]=a/2

for i in range(1,n):
  ans[i]=L[i]-ans[i-1]
  
print(ans)

### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
ans=[0 for i in range(n)]

L=[i*2 for i in L]

m=n//2
a=L[m]

for i in range(1,(n+1)//2):
  a=L[m-i]+L[m+i]-a

ans[0]=a//2

for i in range(1,n):
  ans[i]=L[i-1]-ans[i-1]

print(*ans)
import itertools

N = int(input())
params = []
for i in range(N):
    xyh = [int(n) for n in input().split()]
    params.append(xyh)

#if len(params) == 1:
#    print(*params[0])

#else:

#Cx, Cy, H = 0, 0, 0
for cxi, cyi in itertools.product(range(101), range(101)):
    hight_ = params[0][2] + abs(params[0][0] - cxi) + abs(params[0][1] - cyi)

    for k in range(N):
        if params[k][2] > 0:
            hight = params[k][2] + abs(params[k][0] - cxi) + abs(params[k][1] - cyi)

            if hight < 1:
                break
            else:
                if hight != hight_:
                    break
                else:
                    hight_ = hight

        #elif params[k][2] == 0:
        #    if 1 > (abs(params[k][0] - cxi) + abs(params[k][1] - cyi)):
        #        break
    
    else:
        Cx = cxi
        Cy = cyi
        H = hight
    continue

print(Cx, Cy, H)

### FIXED CODE ###

N = int(input())
params = []
for i in range(N):
    xyh = [int(n) for n in input().split()]
    params.append(xyh)

for cxi in range(101):
    for cyi in range(101):
        for k in range(N):
            if params[k][2] > 0:
                hight = params[k][2] + abs(params[k][0] - cxi) + abs(params[k][1] - cyi)

        for k in range(N):
            if params[k][2] != max((hight - abs(params[k][0] - cxi) - abs(params[k][1] - cyi)), 0):
                break
        
        else:
            print(cxi, cyi, hight)
n, a, b = map(int, input().split())
res = ''

if a == 0:
  print(0)
elif b == 0:
  print(n)
else:
  while len(res) < n:
      res += 'b'*a
      res += 'r'*b

  res = res[:n]
  print(res)
  print(res.count('b'))

### FIXED CODE ###

n, a, b = map(int, input().split())
period = a+b
times = n//period
k = n%period
n =  a if k >a else k
print(times*a + n)
import itertools as it
dic={}
bing=[[0 for i in range(3)] for j in range(3)]
for i in range(3):
    f=list(map(int,input().split()))
    for each in f:
        dic.update({each:(i,f.index(each))})
n=int(input())
for i in range(n):
    m=int(input())
    place=dic[m]
    bing[place[0]][place[1]]=1
flag=False
code="000102101112202122"
code=code+code[::-1]
code=code+"001122021120"

for i in range(8):
    code_sep=code[6*i:6*i+6]
    p=1
    for j in range(3):
        cords=code_sep[2*j:2*j+2]
        p*=bing[int(cords[0])][int(cords[1])]
    if p==1:
        flag=True
        break
    
print("Yes")if flag else print("No")

### FIXED CODE ###

import itertools as it
dic={}
bing=[[0 for i in range(3)] for j in range(3)]
for i in range(3):
    f=list(map(int,input().split()))
    for each in f:
        dic.update({each:(i,f.index(each))})
n=int(input())
for i in range(n):
    m=int(input())
    if m in dic.keys():
        place=dic[m]
        bing[place[0]][place[1]]=1
flag=False
code="000102101112202122"
code=code+code[::-1]
code=code+"001122021120"

for i in range(8):
    code_sep=code[6*i:6*i+6]
    p=1
    for j in range(3):
        cords=code_sep[2*j:2*j+2]
        p*=bing[int(cords[0])][int(cords[1])]
    if p==1:
        flag=True
        break
    
print("Yes")if flag else print("No")
import math


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // math.gcd(c, d)
    num_b = b - b // c - b // d + b // lcm
    num_a = a - 1 - (a - 1) // c - (a - 1) // d + (a - 1) // lcm
    return num_b - num_a


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

import fractions


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // fractions.gcd(c, d)
    div_c = b // c - (a - 1) // c
    div_d = b // d - (a - 1) // d
    div_cd = b // lcm - (a - 1) // lcm
    return (b - a + 1) - div_c - div_d + div_cd


if __name__ == "__main__":
    print(solve())
a, b = map(int(input()))

if abs(a-b) < 2:
    print("Yay!")
else:
    printa, b = map(int, input().split())

if abs(a-b) < 2:
    print("Yay!")
else:
    print(":(")

### FIXED CODE ###

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

if abs(a-b) < 2:
    print("Yay!")
else:
    print(":(")
n = int(input())
a = list(map(int, input().split())).sort(reverse=True)

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

ans = 1
if n == 2:
    print(max(a))
else:
    for i in range(n // 10):
        b = a[:i] + a[i + 1:]
        element = gcd(b[0], b[1])
        if n == 3:
            ans = max(ans, element)
        else:
            for j in range(2, n - 1):
                element = gcd(element, b[j])
            ans = max(ans, element)
    print(ans)


### FIXED CODE ###

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


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

ans = 1
if n == 2:
    print(max(a))
else:
    l = [0] * (n + 1)
    r = [0] * (n + 1)
    for i in range(1, n):
        l[i] = gcd(l[i - 1], a[i - 1])
        r[n - i] = gcd(r[n - i + 1], a[-i])
    for i in range(n):
        m = gcd(l[i], r[i + 1])
        ans = max(ans, m)
    print(ans)
import sys


def dep(u, p):
    D[u] = p
    if tree[u][2] != NIL:
        dep(tree[u][2], p)
    if tree[u][1] != NIL:
        dep(tree[u][1], p+1)


def print_ans():
    for i in range(n):
        if tree[i][0] == NIL:
            typea = "root"
        elif tree[i][1] == NIL:
            typea = "leaf"
        else:
            typea = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i], typea, tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
    for i in range(n):
        if tree[i][0] == NIL:
            r = i
            break
    dep(r, 0)
    print_ans()

### FIXED CODE ###

import sys


def dep(u, p):
    D[u] = p
    for i in tree[u][3]:
        dep(i, p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    # ???????????????
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] # ????????????
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] # ??????????????????
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()
x = input('number?')
y = int(x)
print(x**3+ "\n")



### FIXED CODE ###

a = int(input())
print(a**3)
n, k = [int(x) for x in input().strip().split()]
s = input().strip()
s[k-1] = s[k-1].lower()
print(s)

### FIXED CODE ###

n, k = [int(x) for x in input().strip().split()]
s = input().strip()
print(s[:k-1]+s[k-1].lower()+s[k:])
n = int(input())
 
if n%2 == 0:
    print(0.5)   
else:
    s = (n-1)/2   
    s /= n　　　
    print(1-s)    

### FIXED CODE ###

n = int(input())

if n%2 == 0:
    print(0.5)
else:
    print(1-(n-1)/2/n)
n, q = map(int, input().split())
s = input()
lst = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    lst[i] = (l, r)

cum = [0] * (n + 1)
for i in range(n):
    cum[i + 1] = cum[i]
    if s[i] == 'A' and s[i + 1] == 'C':
        cum[i + 1] += 1

for x in lst:
    print(cum[x[1]-1] - cum[x[0]-1])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lst = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    lst[i] = (l, r)

cum = [0] * (n + 1)
for i in range(n):
    cum[i + 1] = cum[i]
    if i < n - 1 and s[i] == 'A' and s[i + 1] == 'C':
        cum[i + 1] += 1

for x in lst:
    print(cum[x[1]-1] - cum[x[0]-1])
n,x=map(int,input().split())
xlist= list(map(int,input().split()))
xlist.append(x)
xsort = sorted(xlist, reverse=True)
ylist = []
for i in range(n-1):
  ylist.append(xsort[i]-xsort[i+1])
from functools import reduce
from math import gcd
print(reduce(gcd,ylist))

### FIXED CODE ###

n,x=map(int,input().split())
xlist= list(map(int,input().split()))
if n == 1:
  print(abs(xlist[0]-x))
  exit()
ylist = []
for i in range(n):
  ylist.append(abs(xlist[i]-x))
from functools import reduce
from math import gcd
print(reduce(gcd,ylist))
h,w=map(int,input().split())
a=[[0 if s=="." else "#" for s in list(input())] for i in range(h)]
for _ in range(h):
  for s in range(w):
    if a[_][s]=="#":
      try:
        a[_-1][s]+=1
      except:
        continue
      try:
        a[_+1][s]+=1
      except:
        continue
      try:
        a[_][s-1]+=1
      except:
        continue
      try:
        a[_][s+1]+=1
      except:
        continue
      try:
        a[_+1][s+1]+=1
      except:
        continue
      try:
        a[_+1][s-1]+=1
      except:
        continue
      try:
        a[_-1][s+1]+=1
      except:
        continue
      try:
        a[_-1][s-1]+=1
      except:
        continue
    print(a)
for s in range(h):
  print(a[s])

### FIXED CODE ###

n=int(input())
ans=0
for s in range(n):
  a,b=map(int,input().split())
  ans+=b-a+1
print(ans)
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

A.sort()
ans = 0
i = 0
j = N-1

c = Counter(A)
A = [i[0] for i in c.items() if i[1] == 1]

while A:
  if A[j] % A[i] == 0:
    A.pop(j)
  j -= 1
  if j == i:
    ans += 1
    j = int(len(A)-1)
    i += 1
  if j == i:
    ans += 1
    break;

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
l = max(A)+1
li = [0]*(l)
A.sort()

for a in A:
  if li[a] == 0:
    li[a] = 1
    for i in range(a*2, l, a):
      li[i] = 2
  elif li[a] == 1:
    li[a] = 2
print(li.count(1))
from enum import Enum

N = int(input())
H = [int(h) for h in input().split()]

# 状態
class State(Enum):
    INCREASING = 1
    DECREASED_BY_1 = 2
    FAIL = -1

state = State.INCREASING

for i in range(1, N): # i = 1, 2, ..., N - 1
    if state == State.INCREASING:
        if H[i] == H[i - 1] - 1: # 1減少
            state = State.DECREASED_BY_1
        elif H[i] <= H[i - 1] - 2: # 2以上減少
            state = State.FAIL
    elif state == State.DECREASED_BY_1:
        if H[i] > H[i - 1]: # 増加
            state = State.INCREASING
        elif H[i] < H[i - 1]: # 減少
            state = State.FAIL
    else:
        break

ans = "Yes" if state is not State.FAIL else "No"
print(ans)


### FIXED CODE ###

N = int(input())
H = [int(h) for h in input().split()]

# 状態
INCREASING = 1
DECREASED_BY_1 = 2
FAIL = -1

state = INCREASING

for i in range(1, N): # i = 1, 2, ..., N - 1
    if state == INCREASING:
        if H[i] == H[i - 1] - 1: # 1減少
            state = DECREASED_BY_1
        elif H[i] <= H[i - 1] - 2: # 2以上減少
            state = FAIL
    elif state == DECREASED_BY_1:
        if H[i] > H[i - 1]: # 増加
            state = INCREASING
        elif H[i] < H[i - 1]: # 減少
            state = FAIL
    else:
        break

ans = "Yes" if state is not FAIL else "No"
print(ans)
N = int(input())
S = input()
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
ans = r * g * b

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        x = j + j - i
        if S[i] != S[j] and x <= N - 1:
            if S[i] != S[x] and S[x] != S[j]:
                ans -= 1

print(ans)


### FIXED CODE ###

N = input()
ans = "No"
for i in N:
    if i == "7":
        ans = "Yes"

print(ans)
menu = [int(input()) for _ in range(5)]

cnt = 0
l = []
for m in menu:
  cnt += m
  mod = cnt % 10
  if mod != 0:
    cnt += 10 - mod
    l.append(mod)

cnt -= 10 - min(l)
print(cnt)

### FIXED CODE ###

menu = [int(input()) for _ in range(5)]

cnt = 0
l = [10]
for m in menu:
  cnt += m
  mod = cnt % 10
  if mod != 0:
    cnt += 10 - mod
    l.append(mod)

cnt -= 10 - min(l)
print(cnt)
#!/usr/bin/env python

n, m = input().split(" ")
n = int(n)
m = int(m)
s_len = []
c_len = []
dig = 10**(n-1)

for i in range(m):
    tmp = input().split(" ")
    s_len.append(int(tmp[0]))
    c_len.append(int(tmp[1]))

c_t = 0
for i in c_len:
    c_t += int(i)

for i in range(dig-1, dig*10):
    flag = False
    for j,s in enumerate(s_len):
        if str(i)[s-1] != str(c_len[j]) and flag == False:
            flag = True
            break
    if flag==False:
        print(i)
        exit()

print("-1")

### FIXED CODE ###

#!/usr/bin/env python

n, m = input().split(" ")
n = int(n)
m = int(m)
s_len = []
c_len = []
dig = 10**(n-1)

for i in range(m):
    tmp = input().split(" ")
    s_len.append(int(tmp[0]))
    c_len.append(int(tmp[1]))

for i in range(0, dig*10):
    flag = False
    if len(str(i)) < n:
        continue
    for j,s in enumerate(s_len):
        if str(i)[s-1] != str(c_len[j]) and flag == False:
            flag = True
            break
    if flag==False:
        print(i)
        exit()

print("-1")
x=int(input())
if x=0:
  print("1")
else:
  print("0")

### FIXED CODE ###

x=int(input())
if x==0:
  print(1)
else:
  print(0)
n,m=map(int,input().split())
a=sorted(map(int,input().split()))
b=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])[::-1]
i=0
for num,v in b:
	for j in range(num):
		if a[i]<v and i<n:
			a[i]=v
			i+=1
		else:
			print(sum(a))
			exit()
else:
	print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=sorted(map(int,input().split()))
b=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])[::-1]
i=0
for num,v in b:
	for j in range(num):
		if i<n and a[i]<v:
			a[i]=v
			i+=1
		else:
			print(sum(a))
			exit()
else:
	print(sum(a))
import math
H=input()
W=input()
N=input()
m=max(H,W)
print(math.ceil(N/m))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N=len(v)
    size=len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列


    import math
    H=int(input())
    W=int(input())
    N=int(input())
    m=max(H,W)
    print(math.ceil(N/m))



if __name__ == "__main__":
    main()
# encoding: "utf-8"

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def first_count_and_pop(xs):
    cnt = 0
    fst = xs[0]
    cnt = xs.count(fst)
    # for x in xs:
    #     if x != fst:
    #         break
    #     cnt += 1
    return (cnt, xs[cnt:])    
    

def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    ys = dict()
    while xs:
        key = xs[0]
        cnt, xs = first_count_and_pop(xs)
        ys[key] = cnt
    zs = sorted(list(ys.items()), key=(lambda x: x[1]), reverse=True)
    m = 0
    for i in range(1, 10000):
        temp = ys.get(i-1, 0) + x + ys.get(i+1, 0)
        if m < temp:
            m = temp
    print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
lst = list(map(int, input().split()))
s = set(lst)

if len(s) == 1:
  print (`Yes`)
else:
  print (`No`)

### FIXED CODE ###

lst = list(map(int, input().split()))
s = set(lst)

if len(s) == 1:
  print ('Yes')
else:
  print ('No')
def cmb(n, r, mod):
    if (r<0 or r>n):
        return(0)
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2,N+1):
    g1.append(( g1[-1] * i ) % mod)
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
n,k=map(int,input().split())
for i in range(1,K+1):
    ans = cmb(n-k+1,i,mod)*cmb(k-1,i-1,mod)
    print(ans%mod)

### FIXED CODE ###

def cmb(n, r, mod):
    if (r<0 or r>n):
        return(0)
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
N = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2,N+1):
    g1.append(( g1[-1] * i ) % mod)
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
n,k=map(int,input().split())
for i in range(1,k+1):
    ans = cmb(n-k+1,i,mod)*cmb(k-1,i-1,mod)
    print(ans%mod)
H,W = map(int, input().split())
fields = [list(input()) for i in range(H)]

for f in fields:
    cnt += f.count("#")
if cnt == H + W - 1: 
    print("Possible")
else:
    print("Impossible")

### FIXED CODE ###

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

mvs = [(0,1),(1,0)]

from collections import deque
q = deque()
q.append((0,0))

cnt = 0
for f in fields:
    cnt += f.count("#")
if cnt != H + W - 1: 
    print("Impossible")
    exit()
# ゴールまで連結しているか
while len(q) > 0:
    h,w = q.popleft()
    if h == H-1 and w == W-1:
        print("Possible")
        exit()
    for dh, dw in mvs:
        h_nx = h + dh
        w_nx = w + dw
        if h_nx >= H or w_nx >= W:continue
        if fields[h_nx][w_nx] == ".":continue
        q.append((h_nx,w_nx))
print("Impossible")
n = list(int(input()))
for i in range(n):
    if n[i]==1:
        n[i]=9
    elif n[i]==9:
        n[i]=1
print("".join(n))

### FIXED CODE ###

n = list(input())
for i in range(len(n)):
    if n[i]=="1":
        n[i]="9"
    elif n[i]=="9":
        n[i]="1"
print("".join(n))