Harryxun/stf_run huggingface dataset:
x1,y1,x2,y2=map(float,raw_input().split(" "))
if y1==y2 or x1==x2:
    if y1==y2:
        t0=0
    if x1==x2:
        t1=0
else:
    t0=(y2-y1)/(x2-x1)
    b0=y1-t0*x1
    t1=-(x2-x1)/(y2-y1)

for i in xrange(int(raw_input())):
    px,py=map(float,raw_input().split(" "))
    if t0==0 or t1==0:
        if t0==0:
            t1=-1
            a=1.0
            b=-t0
            c=y1
            d=0.0
            e=-t1
            f=px
        if t1==0:
            t0=-1
            a=0.0
            b=-t0
            c=x1
            d=1.0
            e=-t0
            f=py
    else:
        b1=py-t1*px
        a,b,c,d,e,f=1.0,-t0,b0,1.0,-t1,b1
    kouten_y=(c*e-f*b)/(a*e-b*d)
    kouten_x=(a*f-c*d)/(a*e-b*d)
    print "{0:.10f} {1:.10f}".format(kouten_x,kouten_y)

### FIXED CODE ###

x1,y1,x2,y2=map(float,raw_input().split(" "))
if y1==y2 or x1==x2:
    if y1==y2:
        t0=0
        t1=-1
    if x1==x2:
        t1=0
        t0=-1
else:
    t0=(y2-y1)/(x2-x1)
    b0=y1-t0*x1
    t1=-(x2-x1)/(y2-y1)

for i in xrange(int(raw_input())):
    px,py=map(float,raw_input().split(" "))
    if t0==0 or t1==0:
        if t0==0:
            a=1.0
            b=-t0
            c=y1
            d=0.0
            e=-t1
            f=px
        if t1==0:
            a=0.0
            b=-t0
            c=x1
            d=1.0
            e=-t0
            f=py
    else:
        b1=py-t1*px
        a,b,c,d,e,f=1.0,-t0,b0,1.0,-t1,b1
    kouten_y=(c*e-f*b)/(a*e-b*d)
    kouten_x=(a*f-c*d)/(a*e-b*d)
    print "{0:.10f} {1:.10f}".format(kouten_x,kouten_y)
#C - Stones
n = int(input())
s = list(input())
isFound = False
cnt = 0
right = 0
#一番右の白を見つける
for i in range(n):
    if s[i] == '.':
        right = max(right, i)
#rightまでの黒を数える
for i in range(right+1):
    if s[i] == '#':
        cnt += 1
print(min(s.count('.'), s.count('#'), cnt))

### FIXED CODE ###

#A - On the Way
a, b, c = map(int, input().split())
if (a<c and c<b) or (a>c and c>b):
    print('Yes')
else:
    print('No')
n,d = map(int,input().split())
from math import sqrt
count = 0
for _ in range(n):
  x,y = map(int,input().split())
  m = sqrt(x**2 + y**2)
  if m <= d:
    count += 1
print(ccount)

### FIXED CODE ###

n,d = map(int,input().split())
from math import sqrt
count = 0
for i in range(n):
    x,y = map(int,input().split())
    m = sqrt(x**2 + y**2)
    if m <= d:
        count += 1
print(count)
def resolve():
    def route(a, b):
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        if dx < 0 or dy < 0:
            return 0
        return cmb.nCr(dx+dy, dx)


    MOD = 10 ** 9 + 7
    H, W, N = map(int, input().split())
    wall = []
    for _ in range(N):
        r, c = map(lambda x:int(x)-1, input().split())
        wall.append((r, c))
    # スタート位置
    wall.append((0, 0))
    wall.sort()

    cmb = Combination((H + W) + 1)
    dp = [[0] * 2 for _ in range(N + 1)]
    dp[0][0] = 1

    for i in range(1, N+1):
        for j in range(0, i):
            dp[i][0] += dp[j][1] * route(wall[j], wall[i]) % MOD
            dp[i][0] %= MOD
            dp[i][1] += dp[j][0] * route(wall[j], wall[i]) % MOD
            dp[i][1] %= MOD

    goal = (H-1, W-1)
    ng = 0
    for i in range(1, N+1):
        ng -= dp[i][0] * route(wall[i], goal) % MOD
        ng += dp[i][1] * route(wall[i], goal) % MOD
        ng %= MOD

    # 全体 - ng
    all = cmb.nCr(H+W-2, H-1)
    ans = (all - ng + MOD) % MOD
    print(ans)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max + 1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod - 2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def nCr(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod


def resolve():
    MOD = 10 ** 9 + 7
    H, W, N = map(int, input().split())
    wall = []
    for _ in range(N):
        r, c = map(lambda x: int(x) - 1, input().split())
        wall.append((r, c))
    # 番兵
    wall.append((H - 1, W - 1))
    wall.sort()

    cmb = Combination((H + W) + 1)
    dp = [0] * (N + 1)

    # 壁がない時(0,0)から(x,y)まで移動する場合の数: x+yCx
    # dp[i] =f(r[i]+c[i],c[i])−(i−1番目までの壁に1回以上ぶつかって壁iの位置にたどり着く場合の数)
    for i in range(N + 1):
        r1, c1 = wall[i]
        dp[i] = cmb.nCr(r1 + c1, c1)
        for j in range(0, i):
            dx = r1 - wall[j][0]
            dy = c1 - wall[j][1]
            # dp[j]: 1～j-1 番目の壁を避けてj番目の壁の位置にたどり着く場合の数
            # nCr :  j 番目の壁の位置からi番目の壁の位置まで壁を無視して移動する場合の数
            tmp = dp[j] * cmb.nCr(dx + dy, dy)
            dp[i] = (dp[i] - tmp % MOD + MOD) % MOD

    print(dp[N])


if __name__ == "__main__":
    resolve()
a,b,c =input().split()

if a=<b:
  ans=c
else:
  ans=c-(a-b)
  if ans<0:
    ans=0
    
  
print(ans)

### FIXED CODE ###

a,b,c = map(int,input().split())
ans = 0

if a <= b:
    ans = c
else:
	ans = c-(a-b)
	if ans < 0:
		ans = 0
    
print(ans)
N, M = map(int, input().split())

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100033
inv = [1] * 100033
for k in range(1, 100033):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2))

def combine(n, k):
    return fact[n] * inv[k] % mod * inv[n-k] % mod

ans = 1
for e in f:
    ans *= combine(e+N-1, e) # N_H_e (重複組合せ)
    ans %= mod

print(ans)


### FIXED CODE ###

from collections import Counter

mod = 1000000007

# nの素因数分解

def prime(n):
    d = Counter()
    i = 2
    while i*i <= n:
        while n%i == 0:
            n //= i
            d[i] += 1
        i += 1
    if n > 1:
        d[n] += 1
    return d

# xのn乗を計算する
def mod_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half_x = mod_pow(x, n // 2)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n-1) % mod

fact = [1] * 100100
inv = [1] * 100100
for k in range(1, 100100):
    fact[k] = fact[k-1] * k % mod
    inv[k] = mod_pow(fact[k], mod-2)

def nCr(n, r):
    return fact[n] * inv[r] % mod * inv[n-r] % mod

def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p.values():
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)

solve()
G = None
ans = None

def dfs(v, parent_c=-1, parent_id=-1):
    global G, ans
    k = 1
    for i in range(len(G[v])):
        edge_id, to = G[v][i]['edge_id'], G[v][i]['to']
        if to == parent_id: continue
        if k == parent_c: k+=1
        ans[edge_id] = k
        k += 1
        dfs(to, parent_c=ans[edge_id], parent_id=v)

def main():
    global G, ans
    N = int(input())
    G = [[] for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    for edge_id in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append({'to': b, 'edge_id': edge_id})
        G[b].append({'to': a, 'edge_id': edge_id})
    
    dfs(0)
    print(max(ans))
    for a in ans:
        print(a)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
G = None
ans = None

def dfs(v, parent_c=-1, parent_id=-1):
    global G, ans
    k = 1
    for i in range(len(G[v])):
        edge_id, to = G[v][i]['edge_id'], G[v][i]['to']
        if to == parent_id: continue
        if k == parent_c: k+=1
        ans[edge_id] = k
        k += 1
        dfs(to, parent_c=ans[edge_id], parent_id=v)

def main():
    global G, ans
    N = int(input())
    G = [[] for _ in range(N)]
    ans = [0 for _ in range(N-1)]
    for edge_id in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append({'to': b, 'edge_id': edge_id})
        G[b].append({'to': a, 'edge_id': edge_id})
    
    dfs(0)
    print(max(ans))
    for a in ans:
        print(a)

main()
n = int(raw_input())
l = set()
max = -10^9
x=0
for i in range(n-1)
    l.add(int(raw_input())

for s in range(n-1)
 for t in range(s-1)
  x= l[n-s]-l[n-t]
  if max<x:
   max=x
printf('%d')%(max)

### FIXED CODE ###

n = int(raw_input())
max = -10**9
x1 = input() 
min = x1

for i in range(n-1):
 x = int(raw_input())

 if max < x-min:
  max = x- min
 if x< min:
  min = x
  
print max
int N = input()
str S = input()

res = count("ABC")
print(res)


### FIXED CODE ###

N = input()
S = input()
print(S.count("ABC"))
N = int(input())
S = input()
N_original = N

ans = 0
isleft = True

def f(n):
    for i in range(N_original - n+1):
        temp = S[i:i+n]
        if temp in S[i+n:]:
            return True
    return False

left = 0
right = N
N = N//4
while True:
    if f(N):
        if left == N:
            ans = left
            break
        left = N
    else:
        if right == N:
            ans = right
            break
        right = N
    N = (left + right)//2
print(ans)


### FIXED CODE ###

S = input()
if S == "Sunny":
    print("Cloudy")
elif S == "Cloudy":
    print("Rainy")
elif S == "Rainy":
    print("Sunny")
import sys
    input = sys.stdin.readline
    s = list(input())
    x, y = map(int, input().split())
    y = abs(y)
    s.append('T')
    x1 = []
    y1 = []

    count = 0
    u = 0
    for i in range(len(s)):
        if s[i] == 'F':
            count += 1
        else:
            if u % 2 == 0:
                x1.append(count)
                u += 1
                count = 0
            else:
                y1.append(count)
                u += 1
                count = 0

    v = sum(x1)
    w = sum(y1)
    if v < x or w < y:
        print('No')
        exit()

    dpx = [[0 for i in range(v + 1)] for j in range(len(x1) + 1)]
    dpx[0][-1] = 1
    x -= x1[0]
    x1[0] = 0
    v-=x1[0]
    x=abs(x)

    for i in range(len(x1)):
        for j in range(v + 1):
            if dpx[i][j] == 1:
                if j - 2 * x1[i] >= 0:
                    dpx[i + 1][j - 2 * x1[i]] = 1
                dpx[i + 1][j] = 1

    if len(y1) == 0:
        y1.append(0)
    dpy = [[0 for i in range(w + 1)] for j in range(len(y1) + 1)]
    dpy[0][-1] = 1

    for i in range(len(y1)):
        for j in range(w + 1):
            if dpy[i][j] == 1:
                if j - 2 * y1[i] >= 0:
                    dpy[i + 1][j - 2 * y1[i]] = 1
                dpy[i + 1][j] = 1

    if dpy[-1][y] == 1 and dpx[-1][x] == 1:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import sys
input = sys.stdin.readline
s=list(input())
x,y = map(int, input().split())
y=abs(y)
s.append('T')
x1=[]
y1=[]

count=0
u=0
for i in range(len(s)):
    if s[i]=='F':
        count+=1
    else:
        if u%2==0:
            x1.append(count)
            u+=1
            count=0
        else:
            y1.append(count)
            u+=1
            count=0
v=sum(x1)
w=sum(y1)
v-=x1[0]
x-=x1[0]
x1.pop(0)
x=abs(x)
if v<x or w<y:
    print('No')
    exit()

dpx=[[0 for i in range(v+1)] for j in range(len(x1)+1)]
dpx[0][-1]=1

for i in range(len(x1)):
    for j in range(v+1):
        if dpx[i][j]==1:
            if j-2*x1[i]>=0:
                dpx[i+1][j-2*x1[i]]=1
            dpx[i+1][j]=1

if len(y1)==0:
    y1.append(0)
dpy=[[0 for i in range(w+1)] for j in range(len(y1)+1)]
dpy[0][-1]=1

for i in range(len(y1)):
    for j in range(w+1):
        if dpy[i][j]==1:
            if j-2*y1[i]>=0:
                dpy[i+1][j-2*y1[i]]=1
            dpy[i+1][j]=1

if dpy[-1][y]==1 and dpx[-1][x]==1:
    print('Yes')
else:
    print('No')
x, y = input().split()
if x!=1 and y!=1:
  print(1)
if x!=2 and y!=2:
  print(2)
if x!=3 and y!=3:
  print(3)

### FIXED CODE ###

x = int(input())
y = int(input())
if x==1 and y==2:
    print(3)
elif x==1 and y==3:
    print(2)
elif x==2 and y==3:
    print(1)
elif x==2 and y==1:
    print(3)
elif x==3 and y==1:
    print(2)
elif x==3 and y==2:
    print(1)
while(1):
    n = map(int, raw_input().split())
    if(len(n) == 0):
        break
    a = n[0]
    b = n[1]
    count = 1
    n = 10
    while(1):
        if((a+b)/n > 0):
            count += 1
            n = n*10
        else:
            break
    print count

### FIXED CODE ###

while True:
    try:
        a, b = map(int, raw_input().split())
        print len(str(a+b))
    except EOFError:
        break
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for _ in range(max_digit_num):
        for a in A:
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] <= min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    for i in range(N+1):
        for a in A:
            if i < MATCH_NUM[a]:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    res = ''
    for _ in range(max_digit_num):
        m = -1
        for a in A:
            if N < MATCH_NUM[a]:
                continue
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if a > m:
                    m = a
        res += str(m)
        N -= MATCH_NUM[m]
    print(res)
main()
import bisect

n = int(input())
d = sorted(list(map(int,input().split())))
m = int(input())
t = list(map(int,input().split()))

flg = True
for i in range(m):
  index = bisect.bisect_left(d,t[i])
  if t[i] == d[index]:
    del d[index]
  else:
    flg = False
    break

print('YES' if flg else 'NO')

### FIXED CODE ###

import collections
 
n = int(input())
d = sorted(list(map(int,input().split())))
m = int(input())
t = list(map(int,input().split()))

cd = collections.Counter(d)
ct = collections.Counter(t)

flg = True
for k in ct.items():
  if k[1] > cd[k[0]]:
    flg = False

print('YES' if flg else 'NO')
a,b = map(int,input().split())

#print(a+b)
print(a*b)

### FIXED CODE ###

from collections import defaultdict

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

x = readInt()
l = [0]*(x+1)
l[1]=1

for i in range(2,len(l)):
  if l[i]==0:
    j = i*i
    while 1:
      if j>len(l)-1:
        break
      else:
        l[j]=1
        j*=i


for i in range(len(l)-1,-1,-1):
  if l[i]==1:
    print(i)
    break
N, M, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

max_num = 0


def dfs(curr_a, curr_b, choice, time_required, count):
    global max_num
    if choice == 0:
        if curr_a >= N - 1:
            if max_num < count:
                max_num = count
            return
        else:
            curr_a += 1
            time_required += a[curr_a]
    else:
        if curr_b >= M - 1:
            if max_num < count:
                max_num = count
            return
        else:
            curr_b += 1
            time_required += b[curr_b]
    if time_required > K:
        return
    count += 1
    if max_num < count:
        max_num = count
    print(max_num)
    dfs(curr_a, curr_b, 0, time_required, count)
    dfs(curr_a, curr_b, 1, time_required, count)

curr_a = -1
curr_b = -1
time_required = 0
count = 0
dfs(curr_a, curr_b, 0, time_required, count)
curr_a = -1
curr_b = -1
time_required = 0
count = 0
dfs(curr_a, curr_b, 1, time_required, count)

print(max_num)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
import math 
import bisect
import heapq
from operator import mul
from collections import deque

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]



def dfs(start):
    if start == 1:
        return [True] * n
    task = deque([])
    seen = [False] * n

    task.appendleft(start)
    seen[start-1] = True

    while task:
        task.popleft()
        for i in range(len(ab)):
            if ab[i][0] == start and seen[ab[i][1]-1] == False:
                next = ab[i][1]
                seen[next-1] = True
                task.appendleft(next)


    return seen


ans = [0]*n

for i in range(q):
    for j in range(n):
        ans[j] += px[i][1] if dfs(px[i][0])[j] else 0
for i in range(len(ans))
print(ans[i])



### FIXED CODE ###

import math 
import bisect
import heapq
from operator import mul
from collections import deque

n, q = map(int, input().split())
g=[[] for _ in range(n)]

for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b - 1].append(a - 1)
c = [0] * n

for j in range(q):
    p, x = map(int, input().split())
    c[p - 1] += x

seen = [0] * n
seen[0] = 1
next = deque([0])


while next:
    v = next.popleft()
    cost = c[v]

    for nv in g[v]:

        if seen[nv]:
            continue
        seen[nv] = 1
        next.append(nv)
        c[nv] += cost

print(*c)
c=0
n=int(input())
s=int(input().split())
nqint(input())
t=int(input().split())
for i in t:
	for j in s:
		if i==j:
			c +=1
print(c)


### FIXED CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
for i in t:
	for j in s:
		if int(i)==int(j):
			c +=1
			break
print(c)
a = list(input().split())
b = list(input().split())
c = list(input().split())

print(a[0]+b[1]+c[2])

### FIXED CODE ###

a = input()
b = input()
c = input()

print(a[0]+b[1]+c[2])
s = input()
k = int(input())

for i in range(len(s)):
    if s[i] == "1":
        continue
    else:
        ans = s[i]
        break
    ans = "1"

print(ans)


### FIXED CODE ###

s = input()
k = int(input())

len1s = 0
for i in range(len(s)):
    if s[i] == "1":
        len1s += 1
        continue
    else:
        res = s[i]
        break
else:
    res = "1"

if k <= len1s:
    ans = "1"
else:
    ans = res

print(ans)
import sys
input = sys.stdin.readline

N = int(input())
D = list(map(int, input().split()))
mod = 998244353

if D[0] > 0:
    print(0)
else:
    num = [0]*max(D)
    for i in range(1, N):
        if D[i] > 0:
            num[D[i]-1] += 1

ans = 1
for i in range(1, len(num)):
    ans *= (num[i-1]**num[i]) % mod

print(ans % mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
D = list(map(int, input().split()))
mod = 998244353

if 0 in D[1:] or D[0] != 0:
    print(0)
    exit(0)
else:
    num = [0]*max(D)
    for i in range(1, N):
        if D[i] > 0:
            num[D[i]-1] += 1

    ans = 1
    for i in range(1, len(num)):
        ans *= (num[i-1]**num[i]) % mod

    print(ans % mod)
def makeCahnge(c):
    money = c
    ret = []
    for i in [500, 100, 50, 10]:
        ret.append(money // i)
        money %= i
    return ret[::-1]

ansOut = []
while True:
    price = int(input())
    if price == 0: break
    c10, c50, c100, c500 = map(int, input().split())
    ans = 20*4+1
    anspay = [0, 0, 0, 0]
    for i10 in range(c10+1):
        for i50 in range(c50+1):
            for i100 in range(c100+1):
                for i500 in range(c500+1):
                    payment = sum(i*c for i, c in zip([i10, i50, i100, i500], [10, 50, 100, 500]))
                    
                    if payment >= price:
                        if sum(i-c+p for i, c, p in zip([i10, i50, i100, i500], [c10, c50, c100, c500], makeCahnge(payment - price))) < ans:
                            ans = sum(i-c+p for i, c, p in zip([i10, i50, i100, i500], [c10, c50, c100, c500], makeCahnge(payment - price))) 
                            anspay = [i10, i50, i100, i500]

    out = []
    for i, c in zip(anspay, [10, 50, 100, 500]):
        if i > 0:
            out.append('{} {}'.format(c, i))
    ansOut.append('\n'.join(out))
print('\n\n'.join(ansOut))

### FIXED CODE ###

ansOut = []
coin = [10, 50, 100, 500]
while True:
    price = int(input())
    if price == 0:
        break
    cash = list(map(int, input().split()))
    sumCash = sum(c * n for c, n in zip(coin, cash))
    change = sumCash - price
    changeCoins = [(change % 50) // 10, (change % 100) // 50, (change % 500) // 100, change // 500]

    out = []
    for i in range(4):
        if cash[i] > changeCoins[i]:
            out.append('{} {}'.format(coin[i], cash[i] - changeCoins[i]))
    ansOut.append('\n'.join(out))
print('\n\n'.join(ansOut))
from collections import deque

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


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial) 
    while len(frontier):
        locations = []
        current_node = frontier.popleft()
        current_state = current_node[0]
        x, y = current_state
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < H:
                if maze[new_x][new_y] == '.' and maze[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == '#':
            continue
        solution = bfs((x, y))
        if ans < solution:
            ans = solution

print(ans)


### FIXED CODE ###

from collections import deque

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


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x, y = current_node
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < W:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        solution = bfs((i, j))
        if ans < solution:
            ans = solution

print(ans)