Harryxun/stf_run huggingface dataset:
pf[len(l)-1] = 3
mod = 1000000007
for i in range(len(l)-2, -1, -1):
    dpf[i] = (3 * dpf[i+1]) % mod
#print(dpf)
def dfs(i):
    if i == len(l):
        return 1
    if l[i] == '0':
        return dfs(i+1)
    return (dpf[i+1] + (dfs(i+1) * 2) % mod) % mod
 
print(dfs(0))

### FIXED CODE ###

l = input()
dpf = [0] * (len(l) + 2)
dpf[len(l)-1] = 3
mod = 1000000007
for i in range(len(l)-2, -1, -1):
    dpf[i] = (3 * dpf[i+1]) % mod
#print(dpf)
# def dfs(i):
#     if i == len(l)-1:
#         if l[i] == '1':
#             return 3
#         else:
#             return 1
#     if l[i] == '0':
#         return dfs(i+1)
#     return (dpf[i+1] + (dfs(i+1) * 2) % mod) % mod
#
# print(dfs(0))

dp = [0] * (len(l))
dp[-1] = 1
if l[-1] == '1':
    dp[-1] = 3
for i in range(len(l)-2, -1, -1):
    if l[i] == '0':
        dp[i] = dp[i+1]
    else:
        dp[i] = (dpf[i+1] + (dp[i+1]*2)%mod)%mod
print(dp[0])
i = input()

if int(i)<0:
 	print("0")
else:
	acc = 0
	for j in range(len(i)//2):
		acc+=9*(10**(2*j))

	if len(i)%2==0:
		print(acc)
	else:
 		addition = int(i[1:])+1
		print(acc+addition)

### FIXED CODE ###

i = input()

acc = 0
for j in range(len(i)//2):
  acc+=9*(10**(2*j))

if len(i)%2==0:
  print(acc)
else:

  addition = (int(i[0])-1)*10**(len(i)-1)+1
  if len(i)>1:
    addition += int(i[1:])
  print(acc+addition)
n = input()
a = (input() for i in range(n))
counter = 0
i = 1
while counter < n:
    i = a[i - 1]
    counter += 1
    if i == 2:
        print(counter)
        break
else:
    print(-1)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
counter = 0
i = 1
while counter <= n:
    i = a[i - 1]
    counter += 1
    if i == 2:
        print(counter)
        break
else:
    print(-1)
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):
  ndp = [0]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi_min = max(0,vf-t)
    vi_max = min(v_max,vf+t)
    def it():
      for vi,d in enumerate(dp[vi_min:vi_max+1], start=vi_min):
        vp = (t+vi+vf)/2
        yield d + 2*vp*vp-vf*vf-vi*vi - 2*(max(0,vp-v_max))**2
    ndp[vf] = max(it())
  
  dp = ndp
 
print(dp[0]/8)

### FIXED CODE ###

from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):

  ndp = [None]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi = min(len(dp)-1,vf+t)
    while vi >= 0 and dp[vi] is None:
      vi -= 1

    if vi < max(0,vf-t):
      ndp[vf] = None
    else:
      vp = (vf+t+vi)/2
      ndp[vf] = dp[vi] + 2*vp*vp-vf*vf-vi*vi - 2*max(0,vp-v_max)**2
  dp = ndp
 
print(dp[0]/8)
r=lambda x:p[x]>=0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=[-1]*-~n
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=x
 if m>0or x==y:s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

### FIXED CODE ###

def root(x):
  while par[x]>=0:x=par[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x!=y:
    if x>y:x,y=y,x
    par[x]+=par[y]
    par[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return-par[root(x)]
n,m,k,*t=map(int,open(0).read().split())
par=[-1]*n
f=[set()for _ in range(n)]
for a,b in zip(*[iter(t[:m*2])]*2):
  a-=1
  b-=1
  unite(a,b)
  f[a].add(b)
  f[b].add(a)
a=[size(i)-len(f[i])-1for i in range(n)]
for c,d in zip(*[iter(t[m*2:])]*2):
  c-=1
  d-=1
  if same(c,d):
    a[c]-=1
    a[d]-=1
print(*a)
a, b, c= map(int, input().split())
if a=b=c:
  print(1)
elif a=b:
  print(2)
elif b=c:
  print(2)
else:
  print(3)

### FIXED CODE ###

a, b, c= map(int, input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)
n=int(input())
w=list(map(int,input().split()))
x=0
for i in range(n):
  s=abs(w[:i+1]-w[i+1:])
  if s.count()==0 or x<s:
    x=s
print(x)

### FIXED CODE ###

from itertools import accumulate
n=int(input())
w=list(map(int,input().split()))
w=list(accumulate(w))
for i in range(n):
  if w[i]*2==w[-1]:
    print(0)
    break
  elif w[i]*2>w[-1]:
    print(min((w[i]*2-w[-1]),(w[-1]-w[i-1]*2)))
    break
x, y = map(int, input().split())
if y%2 == 0 and (x*2 <= y <= x*4):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

x, y = map(int, input().split())
if y%2 == 0 and (x*2 <= y) and (y<= x*4):
  print('Yes')
else:
  print('No')
N, K = map(int, input().split)
h = list(map(int, input().split()))
for hantei in h:
    if K > hantei:
        N -= 1
    else:
        pass
print(str.N)
        

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
for hantei in h:
    if K > hantei:
        N -= 1
    else:
        pass
print(N)
A,B,C=input().split()
A=int(A)
B=int(B)
C=int(C)
D=A/B
D=int(D)
if A%B=0:
  print((D)*C)
else:
  print((D+1)*C)

### FIXED CODE ###

A,B,C=input().split()
A=int(A)
B=int(B)
C=int(C)
D=A/B
D=int(D)
if A%B==0:
  print((D)*C)
else:
  print((D+1)*C)
N, M = open(0).readline().split()
from collections import Counter
cnt = Counter(open(0).read().split())
print('\n'.join(map(str,cnt.values())))

### FIXED CODE ###

N, M, *cnt = open(0).read().split()
from collections import Counter
cnt = Counter(cnt)
for i in range(1,int(N)+1):
    print(cnt[str(i)])
N = input()
K = int(input())
L = len(N)

dp = [[[0 for j in range(L + 1)] for i in range(L + 1)] for _ in range(2)]
dp[0][0][0] = 1

for i in range(L):
    Ni = int(N[i])
    for j in range(L):
        if Ni == 0:
            dp[0][i + 1][j + 0] += dp[0][i][j + 0] * 1
            dp[0][i + 1][j + 1] += dp[0][i][j + 0] * 0
            dp[1][i + 1][j + 0] += dp[0][i][j + 0] * 0 + dp[1][i][j + 0] * 1
            dp[1][i + 1][j + 1] += dp[0][i][j + 0] * 0 + dp[1][i][j + 0] * 9
        else:
            dp[0][i + 1][j + 0] += dp[0][i][j + 0] * 0
            dp[0][i + 1][j + 1] += dp[0][i][j + 0] * 1
            dp[1][i + 1][j + 0] += dp[0][i][j + 0] * 1 + dp[1][i][j + 0] * 1
            dp[1][i + 1][j + 1] += dp[0][i][j + 0] * (Ni - 1) + dp[1][i][j + 0] * 9
#print(dp[0])
#print(dp[1])

print(dp[0][L][K] + dp[1][L][K])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N = int(input())
K = int(input())

LN = len(str(N))

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])
#print(keta1(N))


def keta2(n):
    if n < 10:
        return 0
    cnt2 = [0] * 101
    for i in range(2, 101):
        cnt2[i] = 9 * 9 * (i - 1)
    tmp2 = 0
    for i in range(len(str(n))):
        tmp2 += cnt2[i]
    tmp2 += (int(str(n)[0]) - 1) * keta1((10 ** (len(str(n))  - 1)) - 1) + keta1(int(str(n)[1:]))
    return tmp2

def keta3(n):
    cnt3 = [0] * 101
    for i in range(3, 101):
        cnt3[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    tmp3 = 0
    for i in range(len(str(n))):
        tmp3 += cnt3[i]
    tmp3 += (int(str(N)[0]) - 1) * keta2((10 ** (len(str(n))  - 1)) - 1) + keta2(int(str(n)[1:]))
    
    return tmp3

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))
N=int(input())
A=list(map(int,input().split()))
A.sort()
prit(A[-1]-A[0])


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
print(A[-1]-A[0])
import math

def overlap(p1, p2, d):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 <= d

def intersection(o1,o2):
    a  = 2*(o2[0] - o1[0])
    b  = 2*(o2[1] - o1[1])
    c  = (o1[0] - o2[0])*(o1[0] + o2[0]) + (o1[1] - o2[1])*(o1[1] + o2[1])
    
    a2 = a**2 + b**2
    b2 = a*c + a*b*o1[1] - b**2*o1[0]
    c2 = b**2*(o1[0]**2 + o1[1]**2 - 1) + c**2 + 2*b*c*o1[1]
    x1 = (-b2 + math.sqrt(b2**2 - a2*c2))/a2
    x2 = (-b2 - math.sqrt(b2**2 - a2*c2))/a2
    if b == 0:
        y1 = (o1[1] + o2[1])/2
        y2 = (o1[1] + o2[1])/2
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    if b2**2 - a2*c2 < 10e-6:
        return [x1, y1], [None, None]
    else:
        return [x1, y1], [x2, y2]

while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 4):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2[0] != None and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)


### FIXED CODE ###

import math

def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def intersection(o1,o2):
    if dist(o1,o2) > 2:
        p1, p2 =  [None, None], [None, None]
    elif dist(o1,o2) == 2:
        p1, p2 =  [(o1[0] + o2[0])/2, (o1[1] + o2[1])/2], [None, None]
    else:
        m = [(o1[0] + o2[0])/2, (o1[1] + o2[1])/2]
        v = [m[0] - o1[0], m[1] - o1[1]]
        v_abs = dist(v,[0,0])
        w = [v[1], -v[0]]
        w_abs = dist(w,[0,0])
        n = [w[0]/w_abs, w[1]/w_abs]
        l = math.sqrt(1 - v_abs**2)
        p1 = [m[0] + l*n[0], m[1] + l*n[1]]
        p2 = [m[0] - l*n[0], m[1] - l*n[1]]
    return p1, p2
err = 1.0e-6
while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1[0] and dist(p1, p[k]) <= 1 + err:
                    cnt1 += 1
                if p2[0] and dist(p2, p[k]) <= 1 + err:
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)
A, B, K = map(int, input().split())
lst1 = list(range(A, A+K))
lst2 = list(range(B-K+1, B+1))
ans = set(lst1 + lst2)
ans = list(sorted(ans))
for i in ans:
  print(i)

### FIXED CODE ###

S = list(input())
if 'a' in S and 'b' in S and 'c' in S:
  print('Yes')
else:
  print('No')
import sys
import numpy as np


def solve(sequence):

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[::1])')(solve)
    cc.compile()
    exit()


from my_module import solve


def main():
    sequence = np.array(input().split(), np.int64)
    print(solve(sequence))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# import numpy as np
# from itertools import permutations
# from itertools import combinations
# from itertools import combinations_with_replacement

# import heapq
# from collections import deque

# N, M = map(int, input().split())
# sequence = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    sequence = list(map(int, input().split()))

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


def main():
    print(solve())


if __name__ == "__main__":
    main()
def main():
    s=input()
    x,y=map(int,input().split())

    lf = [0]
    tf = 0
    for i in range(len(s)):
        if s[i] =="F":
            lf[tf] += 1
        else:
            lf.append(0)
            tf += 1

    lx = [lf[i] for i in range(len(lf)) if i % 2 == 0]
    ly = [lf[i] for i in range(len(lf)) if i % 2 == 1]
    dpxcenter = sum(lx)
    dpxedge = dpxcenter*2+20
    dpx = [[False for _ in range(dpxedge)] for _ in range(len(lx)+1)]
    dpx[1][dpxcenter+lx[0]+10] = True
    for i in range(1,len(lx)):
        for j in range(dpxedge):
            if j-lx[i] >= 0:
                dpx[i+1][j] = dpx[i][j-lx[i]]
            if j+lx[i] < dpxedge:
                dpx[i+1][j] = dpx[i+1][j] or dpx[i][j+lx[i]]

    dpycenter = sum(ly)
    dpyedge = dpycenter*2+20
    dpy = [[False for _ in range(dpyedge)] for _ in range(len(ly)+1)]
    dpy[0][dpycenter+10] = True
    for i in range(len(ly)):
        for j in range(dpyedge):
            if j-ly[i] >= 0:
                dpy[i+1][j] = dpy[i][j-ly[i]]
            if j+ly[i] < dpyedge:
                dpy[i+1][j] = dpy[i+1][j] or dpy[i][j+ly[i]]

    if dpx[-1][x+dpxcenter+10] and dpy[-1][y+dpycenter+10]:return "Yes"
    else:return "No"

print(main())

### FIXED CODE ###


def main():
    s=input()
    x,y=map(int,input().split())

    lf = [0]
    tf = 0
    for i in range(len(s)):
        if s[i] =="F":
            lf[tf] += 1
        else:
            lf.append(0)
            tf += 1

    lx = [lf[i] for i in range(len(lf)) if i % 2 == 0]
    ly = [lf[i] for i in range(len(lf)) if i % 2 == 1]
    dpxcenter = sum(lx)
    if abs(x)>dpxcenter: return "No"
    dpxedge = dpxcenter*2+20
    dpx = [[False for _ in range(dpxedge)] for _ in range(len(lx)+1)]
    dpx[1][dpxcenter+lx[0]+10] = True
    for i in range(1,len(lx)):
        for j in range(dpxedge):
            if j-lx[i] >= 0:
                dpx[i+1][j] = dpx[i][j-lx[i]]
            if j+lx[i] < dpxedge:
                dpx[i+1][j] = dpx[i+1][j] or dpx[i][j+lx[i]]

    dpycenter = sum(ly)
    if abs(y)>dpycenter: return "No"
    dpyedge = dpycenter*2+20
    dpy = [[False for _ in range(dpyedge)] for _ in range(len(ly)+1)]
    dpy[0][dpycenter+10] = True
    for i in range(len(ly)):
        for j in range(dpyedge):
            if j-ly[i] >= 0:
                dpy[i+1][j] = dpy[i][j-ly[i]]
            if j+ly[i] < dpyedge:
                dpy[i+1][j] = dpy[i+1][j] or dpy[i][j+ly[i]]

    if dpx[-1][x+dpxcenter+10] and dpy[-1][y+dpycenter+10]:return "Yes"
    else:return "No"

print(main())
X = input()

X1 = 10*int(X[0]) + int(X[1])
X2 = 10*int(X[2]) + int(X[3])

if (1 <= X1 <= 12) and ((X2 > 12) or (X2 == 0)):
    print("MMYY")
elif ((X2 > 12) or (X2 == 0) and (1 <= X1 <= 12):
    print("YYMM")
elif (1 <= X1 <= 12) and (1 <= X2 <= 12):
    print("AMBIGUOUS")
else:
    print("NA")

### FIXED CODE ###

X = input()

X1 = 10*int(X[0]) + int(X[1])
X2 = 10*int(X[2]) + int(X[3])
if (1 <= X1 <= 12) and ((X2 > 12) or (X2 == 0)):
    print("MMYY")
elif ((X1 > 12) or (X1 == 0)) and (1 <= X2 <= 12):
    print("YYMM")
elif (1 <= X1 <= 12) and (1 <= X2 <= 12):
    print("AMBIGUOUS")
else:
    print("NA")
import sys
import string

dic = {}
for c in string.ascii_lowercase:
    dic[c] = 0

for c in sys.stdin.read().lower():
    if c.isalpha():
        dic[c] += 1

for c in dic:
    print(c+" : "+dic[c])

### FIXED CODE ###

import sys
import string

s = sys.stdin.read().lower()
for c in string.ascii_lowercase:
    print(c, ":", s.count(c))
N=int(input())
T=[int(i) for i in raw_input().split()]
M=int(input())
PX=[]
for i in range(M):
    PX.append([int(k) for k in raw_input().split()])
if N>=M:
    for h in range(M):
        time=sum(T)-(T[PX[h][0]-1]-PX[h][1])
        print(time)
else:
    for h in range(N):
        time=sum(T)-(T[PX[h][0]-1]-PX[h][1])
        print(time)

### FIXED CODE ###

N=int(input())
T=list(map(int,input().split()))
M=int(input())
P=[]
X=[]
for k in range(M):
    p,x=map(int,input().split())
    P.append(p)
    X.append(x)

for h in range(M):
    time=sum(T)-T[P[h]-1]+X[h]
    print(time)
import math

s=input()
t=input()
s.sort()
t.sort()
t.reverse()

s<t if print("Yes") else print("No")

### FIXED CODE ###

import math

s=input()
t=input()
s=sorted(s)
t=sorted(t,reverse=True)
if s<t:
    print("Yes")
else :
    print("No")
n, k = map(int, raw_input().split())
print(k * (k-1)**(n-1))


### FIXED CODE ###

a, b, c = map(int, raw_input().split())
print(len(set([a,b,c])))
sx, sy, tx, ty = map(int, input().split())

ans = ""

ans += "U" * (ty - sy) + "R" * (tx - sx)
ans += "D" * (ty - sy) + "L" * (tx - sx)
ans += "L" + "U" * (ty - sy + 1) + "R" * (tx - sx + 1) + "D"
ans += "R" + "D" * (ty - sy + 1) + "L" * (tx - sx + 1) + "U"
print(ans)sx, sy, tx, ty = map(int, input().split())

ans = ""

ans += "U" * (ty - sy) + "R" * (tx - sx)
ans += "D" * (ty - sy) + "L" * (tx - sx)
ans += "L" + "U" * (ty - sy + 1) + "R" * (tx - sx + 1) + "D"
ans += "R" + "D" * (ty - sy + 1) + "L" * (tx - sx + 1) + "U"
print(ans)

### FIXED CODE ###

sx, sy, tx, ty = map(int, input().split())

ans = ""

ans += "U" * (ty - sy) + "R" * (tx - sx)
ans += "D" * (ty - sy) + "L" * (tx - sx)
ans += "L" + "U" * (ty - sy + 1) + "R" * (tx - sx + 1) + "D"
ans += "R" + "D" * (ty - sy + 1) + "L" * (tx - sx + 1) + "U"
print(ans)
nmax = 8
graph = [[0]*nmax for i in range(nmax)]
visited = [0] * nmax

def dfs(v, N, visitied):
  all_visited = True
  for i in range(N):
    if visitied[i] == 0:
      all_visited = False
    if all_visited:
      return 1
  
  ret = 0
  for i in range(N):
    if graph[v][i] == 0:
      continue
    if visited[i] == 0:
      continue
    visited[i] = 1
    ret += dfs(i, N, visited)
    visited[i] = False
  return ret
      

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

visited[0] = 1
print(dfs(0, N, visited))
  


### FIXED CODE ###

nmax = 8
graph = [[0]*nmax for i in range(nmax)]
visited = [0] * nmax


def dfs(v, N, visited):
    all_visited = True
    for i in range(N):
        if visited[i] == 0:
            all_visited = False
    if all_visited:
        return 1
  
    ret = 0
    for i in range(N):
        if graph[v][i] == 0:
            continue
        if visited[i] == 1:
            continue
        visited[i] = 1
        ret += dfs(i, N, visited)
        visited[i] = 0
    return ret
      

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


visited[0] = 1
print(dfs(0, N, visited))
s = int(input())
def func(n):
  if n%2 == 1:
    return 3n+1
  else:
    return n//2
def prog(N):
  if N == 1:
    return s
  else:
    a=s
    for i in range(1,N):
      a = func(a)
    return a

b=[]
for i in range(1,10000):
  tmp = prog(i)
  if tmp in b:
    print(i)
    break
  else:
    b.append(tmp)
  



### FIXED CODE ###

s = int(input())
def func(n):
  if n%2 == 1:
    return 3*n+1
  else:
    return n//2
def prog(N):
  if N == 1:
    return s
  else:
    a=s
    for i in range(1,N):
      a = func(a)
    return a

b=[]
for i in range(1,1000000):
  tmp = prog(i)
  if tmp in b:
    print(i)
    break
  else:
    b.append(tmp)
H,W=map(int,input().split())
A=[tuple(input()) for _ in range(H)]
q=[]
L=[[0]*W for _ in range(H)]
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='#':
            q.append((i,j))
            L[i][j]=-1
print(q)
while len(q)!=0:
    x,y=q.pop(0)
    v=L[x][y]+1 if L[x][y]!=-1 else 1
    if x>0 and L[x-1][y]==0:
        L[x-1][y]=v
        q.append((x-1,y))
    if x<W-1 and L[x+1][y]==0:
        L[x+1][y]=v
        q.append((x+1,y))
    if y>0 and L[x][y-1]==0:
        L[x][y-1]=v
        q.append((x,y-1))
    if y<H-1 and L[x][y+1]==0:
        L[x][y+1]=v
        q.append((x,y+1))
print(max([max(l) for l in L]))

### FIXED CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
L=[[0]*W for _ in range(H)]
next_q=deque()

for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            L[i][j]=1
            next_q.append((i,j))

q=deque()

res = 0
while len(next_q) != 0:
    q=copy.copy(next_q)
    next_q.clear()
    while q:
        y, x = q.popleft()
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q)==0: break
    res += 1
print(res)
def find_max(n, grid):
    def helper(idx, cur_max, down):
        if n > (idx + 1):
            if down:
                return helper(idx + 1, cur_max + grid[1][idx], down)
            else:
                return max(helper(idx + 1, cur_max + grid[1][idx], True), helper(idx + 1, cur_max + grid[0][idx + 1], False))
        else:
            return cur_max + grid[1][idx]

    return helper(0, grid[0][0], False)

n = int(input())
candie_matrix = []
for i in range(2):
    row = list(map(int, input().split()))
    if len(row) != n:
        print("wrong inputs")
        return;

    candie_matrix.append(row)

find_max(n,candie_matrix)

### FIXED CODE ###

def find_max(n, grid):
    def helper(idx, cur_max, down):
        if n > (idx + 1):
            if down:
                return helper(idx + 1, cur_max + grid[1][idx], down)
            else:
                return max(helper(idx + 1, cur_max + grid[1][idx], True), helper(idx + 1, cur_max + grid[0][idx + 1], False))
        else:
            return cur_max + grid[1][idx]

    return helper(0, grid[0][0], False)

n = int(input())
candie_matrix = []
for i in range(2):
    row = list(map(int, input().split()))
    if len(row) != n:
        print("wrong inputs")

    candie_matrix.append(row)

print(find_max(n,candie_matrix))
S = int(input())
W = int(input())
if S > W:
  print("safe")
else:
  print("unsafe")

### FIXED CODE ###

S, W = map(int, input().split())
if S > W:
  print("safe")
else:
  print("unsafe")
S=input()

weather={"Sunny":"Cloudy","Rainy":"Sunny","Cloudy":"Rainy"}

print(wather[S])

### FIXED CODE ###

S=input()

weather={"Sunny":"Cloudy","Rainy":"Sunny","Cloudy":"Rainy"}

print(weather[S])
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: x[0]+x[1], x[0])
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				dp[i][0] = min(dp[i][0], dp[j][0] + men[i-1][1])
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [tuple(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
	for j in range(i+1, 0, -1):
		if dp[j-1] <= men[i][0]:
			dp[j] = min(dp[j], dp[j-1] + men[i][1])

#print(dp)
for i in range(n+1):
	if dp[i] < INF:
		ans = i
print(ans)