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

def main():
    from sys import stdin
    input = stdin.readline

    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {a*(10**9)+b-1 for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = [None]*25
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0,3-b),min(5,w-b+3)):
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j] = 1
                else:
                    temp[i*5+j] = 0
        for i in range(3):
            for j in range(3):
                cnt = [temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()


### FIXED CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

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

ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if a < b+c and b < c+a and c < a+b:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        ans += i - bisect.bisect_right(L[:i], L[j]-L[i])
print(ans)
### BUGGY CODE ###

from math import ceil
import sys
input=sys.stdin.readline
n, h = map(int, input().split())
a = []
b = []
for i in range(n):
  p, q = map(int, input().split())
  a.append(p)
  b.append(q)
b.sort(reverse=1)
ans=0
m=max(a)
while(h>0 and len(b) != 0):
  if b[0] < m:
    break
  h-=b[0]
  b.pop(0)
  ans+=1
if h>0:
  ans+=ceil(h/m)
print(ans)


### FIXED CODE ###

def main():
    import sys
    from math import ceil
    input = sys.stdin.readline

    N, H = map(int, input().split())
    A = []
    B = []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    a_max = max(A)
    B.sort(reverse=True)
    ans = 0
    for i in range(N):
        if a_max >= B[i]:
            break
        elif H > 0:
            ans += 1
            H -= B[i]
            continue
    if H > 0:
        ans += ceil(H / a_max)
    print(ans)


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

s = input()
n = len(s)

if n<5: ans = 0
else:
    ans = 0
    for i in range(n):
        for j in range(i+5, n+1):
            num = int(s[i:j])
            if int(num)%2019==0: ans += 1 ; continue

print(ans)


### FIXED CODE ###

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * pow(10, i, 2019)
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

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

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[[False for _ in range(M)] for j in range(W)] for i in range(H)]
dp[0][0][C[0][0]] = True
for i in range(H):
    for j in range(W):
        D = i + j
        d = C[i][j]
        for k in range((i+j+1)*80):
            if i != 0:
                if dp[i-1][j][abs(k-d)]:
                    dp[i][j][k] = True
                elif dp[i-1][j][k+d]:
                    dp[i][j][k] = True
            if j != 0:
                if dp[i][j-1][abs(k-d)]:
                    dp[i][j][k] = True
                elif dp[i][j-1][k+d]:
                    dp[i][j][k] = True

for i, v in enumerate(dp[H-1][W-1]):
    if v:
        print(i)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        if d != 0:
            x = int(bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
            y = int(bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        else:
            x=y=0
        #print(bin(dp[i-1][j]), bin(dp[i-1][j]+(2**10)))
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
        #print(i, j, d, bin(dp[i][j]))

for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(n):
    if i%2!=n%2:
        ans.insert(0,a[i])
    else:
        ans.append(a[i])
for i in ans:
    print(i,end=" ")

### FIXED CODE ###

from collections import deque
n=int(input())
a=list(map(int,input().split()))
ans=deque()
for i in range(n):
    if i%2!=n%2:
        ans.appendleft(a[i])
    else:
        ans.append(a[i])
for i in ans:
    print(i,end=" ")
### BUGGY CODE ###

H, W = map(int, input().split())
S = ['' for h in range(H)]
L = [[[0, 0] for w in range(W + 2)] for h in range(H + 2)]
ans = 0
for i in range(H):
  S[i] = input()
  for j in range(W):
    if S[i][j] == '.':
      if L[i + 1][j][0] == 0:
        k = j
        while k < W and S[i][k] == '.':
          L[i + 1][j + 1][0] += 1
          k += 1
      else:
        L[i + 1][j + 1][0] = L[i + 1][j][0]
for j in range(W):
  for i in range(H):
    if S[i][j] == '.':
      if L[i][j + 1][1] == 0:
        k = i
        while k < H and S[k][j] == '.':
          L[i + 1][j + 1][1] += 1
          k += 1
        ans = max(sum(L[i + 1][j + 1]) - 1, ans)
      else:
        L[i + 1][j + 1][1] = L[i][j + 1][1]
        ans = max(sum(L[i + 1][j + 1]) - 1, ans)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = ['' for h in range(H)]
L = [[0 for w in range(W + 2)] for h in range(H + 2)]
R = [[0 for w in range(W + 2)] for h in range(H + 2)]
D = [[0 for w in range(W + 2)] for h in range(H + 2)]
U = [[0 for w in range(W + 2)] for h in range(H + 2)] 
ans = 0
for i in range(H):
  S[i] = input()
  for j in range(W):
    if S[i][j] == '.':
      L[i + 1][j + 1] = L[i + 1][j] + 1
    if S[i][W - 1 - j] == '.':
      R[i + 1][W - j] = R[i + 1][W - j + 1] + 1
for j in range(W):
  for i in range(H):
    if S[i][j] == '.':
      U[i + 1][j + 1] = U[i][j + 1] + 1
    if S[H - 1 - i][j] == '.':
      D[H - i][j + 1] = D[H + 1 - i][j + 1] + 1
for i in range(1, H + 1):
  for j in range(1, W + 1):
    ans = max(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3, ans)
print(ans)
### BUGGY CODE ###

def main():
    import itertools,copy,sys
    input = sys.stdin.readline
    T = list(input())
    N = [i for i, x in enumerate(T) if x == '?']
    B = list(itertools.product(['P','D'], repeat=len(N)))
    point = [0]*len(B)
    strs = ['']*len(B)
    for b,i in zip(B,range(len(B))):
        TC = copy.deepcopy(T)
        for n,j in zip(N,range(len(N))):
            TC[n] = b[j]
        TC = ''.join(TC)
        strs[i] = TC
        point[i] = TC.count('PD') + TC.count('D')
    maxin = max(point)

    print(strs[point.index(maxin)])
main()

if __name__ == '__main__':
    main()

### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

import sys
a = sys.stdin.read().split('\n')[:-1]
s = a[0]
q = int(a[1])
f = 1
for i in range(2, q + 2):
    if a[i][0] == '1':
        f = 1 - f
    else:
        if a[i][2] == '21'[f]:
            s = a[i][4] + s
        else:
            s += a[i][4]
if f == 1:
    print(s)
else:
    b = ''
    for c in reversed(s):
        b += c
    print(b)

### FIXED CODE ###

import sys
a = sys.stdin.read().split('\n')[:-1]
q = int(a[1])
f = 1
l = [[], []]
for i in range(2, q + 2):
    if a[i][0] == '1':
        f = 1 - f
    else:
        l[0 if a[i][2] == '21'[f] else 1].append(a[i][4])
if f != 1:
    l[1].reverse()
    print(''.join(l[1]) + ''.join(reversed(list(a[0]))) + ''.join(l[0]))
else:
    l[0].reverse()
    print(''.join(l[0]) + a[0] + ''.join(l[1]))
### BUGGY CODE ###

n=int(input())
s=list(input())
q=int(input())

def ctoi(c):
  return ord(c)-97
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [[0]*(n+1) for _ in range(26)]
  def query(self,a,i):
    r = 0
    while i > 0:
      r += self.tree[a][i]
      i -= i & -i
    return r
  def update(self,i,a,x):
    while i<=n:
      self.tree[a][i]+=x
      i+=i&(-i)
bi=Bit(n)
for i in range(n):
  bi.update(i+1,ctoi(s[i]),1)
  
for _ in range(q):
  a,b,c=input().split()
  a,b=int(a),int(b)
  if a==1 and s[b-1]!=c:
    bi.update(b,ctoi(s[b-1]),-1)
    bi.update(b,ctoi(c),1)
    s[b-1]=c
  elif a==2:
    c=int(c)
    right=[bi.query(i,c) for i in range(26)]
    left=[bi.query(i,b-1) for i in range(26)]
    ans=0
    for r,l in zip(right,left):
      if r-l>0:
        ans+=1
    print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())
q=int(input())

def ctoi(c):
  return ord(c)-97
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [[0]*(n+1) for _ in range(26)]
  def query(self,a,i):
    r = 0
    while i > 0:
      r += self.tree[a][i]
      i -= i & -i
    return r
  def update(self,i,a,x):
    while i<=n:
      self.tree[a][i]+=x
      i+=i&(-i)
bi=Bit(n)
for i in range(n):
  bi.update(i+1,ctoi(s[i]),1)
  
for _ in range(q):
  a,b,c=input().split()
  a,b=int(a),int(b)
  if a==1 and s[b-1]!=c:
    bi.update(b,ctoi(s[b-1]),-1)
    bi.update(b,ctoi(c),1)
    s[b-1]=c
  elif a==2:
    c=int(c)
    right=[bi.query(i,c) for i in range(26)]
    left=[bi.query(i,b-1) for i in range(26)]
    ans=0
    for r,l in zip(right,left):
      if r-l>0:
        ans+=1
    print(ans)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
B = [K]*N
for i in range(N):
    B[i] += A.count(i+1)
for i in range(N):
    if(B[i] > Q):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import bisect as bi

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
B = [K]*N
p = 0
for i in range(N+1):
    A.append(i+1)
C = sorted(A)
for i in range(N):
    B[i] += bi.bisect_left(C,i+2) - p - 1
    p = bi.bisect_left(C,i+2)
for i in range(N):
    if(B[i] > Q):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys

(str_n,str_y) = input().split()
n = int(str_n)
y = int(str_y)

for i in range(y//10000,-1,-1):
    left = y - 10000*i
    
    for j in range(left//5000,-1,-1):
        left = y - 10000*i - 5000*j
        
        for k in range(left//1000,-1,-1):
            left = y - 10000*i - 5000*j - 1000*k
            if left == 0:
                if i+j+k == n:
                    print (i,j,k)
                    sys.exit()

print (-1,-1,-1)

### FIXED CODE ###

import sys

(str_n,str_y) = input().split()
n = int(str_n)
y = int(str_y)

if y % 1000 != 0:
    print (-1,-1,-1)
    sys.exit()

i_max = min(n,y//10000)
for i in range(i_max,-1,-1):
    left = y - 10000*i
    
    j_max = min(n-i,left//5000)
    for j in range(j_max,-1,-1):
        left = y - 10000*i - 5000*j
        
        k = left // 1000
        if i+j+k == n:
            print (i,j,k)
            sys.exit()

print (-1,-1,-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(M)]
    F = [[0]*(N+1) for i in range(N+1)]
    for a,b in C:
        if F[a][b] == 0:
            F[a][b] += 1
        if F[b][a] == 0:
            F[b][a] += 1
    G = [1]*(N+1)
    for i in range(N+1):
        G[i] = sum(F[i])
    ans = max(G) + 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return -self.parents[self.find(x)]

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 1
    if M == 0:
        print(ans)
        return

    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

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

n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a

def div2(x):
  ret=0
  while x%2==0:
    ret+=1
    x//=2
  return ret

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]):
    chk=False
  mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))

### FIXED CODE ###

n,m=map(int,input().split())
A=[int(i)//2 for i in input().split()]

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a

def div2(x):
  ret=0
  while x%2==0:
    ret+=1
    x//=2
  return ret

s=div2(A[0])
chk=True

mul=A[0]
for i in range(1,n):
  if s!=div2(A[i]) or mul>m:
    chk=False
  else:
    mul=mul*A[i]//gcd(mul,A[i])
if not chk:
  print(0)
else:
  print(m//mul-m//(mul*2))
### BUGGY CODE ###

A, B, C, D, E, F = map(int,input().split())

water = []
sugar =[]
ans = [-1] * 3
for i in range(F+1):
    for j in range(F+1):
        y = i * C + j * D
        if y <= F:
            sugar.append(y)

for i in range(F + 1):
    for j in range(F + 1):
        x = i * 100 * A + j * 100 * B
        if x <= F:
            water.append(x)

for i in range(len(water)):
    for j in range(len(sugar)):
        a = water[i]
        b = sugar[j]
        if a + b <= F and a / 100 * E >= b:
            if ans[0] * (a + b) < 100 * b:
                ans[0] = 100 * b / (a + b)
                ans[1] = a + b
                ans[2] = b
print("{} {}".format(ans[1], ans[2]))


### FIXED CODE ###

A, B, C, D, E, F = map(int,input().split())

water = []
sugar =[]
ans = [-1] * 3
for i in range(F+1):
    for j in range(F+1):
        y = i * C + j * D
        if y <= F:
            sugar.append(y)

for i in range(F + 1):
    for j in range(F + 1):
        x = i * 100 * A + j * 100 * B
        if x <= F:
            water.append(x)

for i in range(len(water)):
    for j in range(len(sugar)):
        a = water[i]
        b = sugar[j]
        if a + b <= F and a / 100 * E >= b:
            if ans[0] * (a + b) < 100 * b:
                ans[0] = 100 * b / (a + b)
                ans[1] = a + b
                ans[2] = b
print("{} {}".format(ans[1], ans[2]))
### BUGGY CODE ###

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

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

Q, K =(int(i) for i in input().split())

d = BFS(N, graph, K-1)
for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(d[x-1] + d[y-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    dd = [float("inf")] * N
    Q.append(start)
    dd[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

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

Q, K =(int(i) for i in input().split())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    dd = BFS(N, graph, K-1)

for i in range(Q):
    x, y = (int(a) for a in input().split())
    print(dd[x-1] + dd[y-1])
### BUGGY CODE ###

n, w = map(int, input().split())
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 for j in range(w+1)]for i in range(n+1)]
for i in range(n+1):
    for j in range(w+1):
        if j-g[i-1][0] < 0:
            m[i][j] = m[i-1][j]
        else:
            m[i][j] = max(m[i-1][j], m[i-1][j-g[i-1][0]]+g[i-1][1])
print(m[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
g = []
for i in range(n):
    g.append(list(map(int, input().split())))
m = [[0 for j in range(w+1)]for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j-g[i][0] < 0:
            m[i+1][j] = m[i][j]
        else:
            m[i+1][j] = max(m[i][j], m[i][j-g[i][0]]+g[i][1])
print(m[n][w])
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

N, M = map(int, input().split())

list_A = []
list_B = []
for _ in range(M):
    a, b = map(int, input().split())
    list_A.append(a)
    list_B.append(b)


visitlist = []  
for i in range(M):
    if list_B[i] == N:
        visitlist.append(list_A[i])

for j in range(M):
    if list_A[j] == 1 and list_B[j] in visitlist:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int, input().split())

travellist = []
for _ in range(M):
    a, b = map(int, input().split())
    travellist.append([a,b])

travellist = sorted(travellist)


To_list = [0]*N
From_list = []
for i in range(M):

    oneroot = travellist[i]
    From = oneroot[0]
    To   = oneroot[1]

    if From == 1:
        To_list[To] = 1

    if To == N:
        From_list.append(From)


for i in From_list:
    if To_list[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
ans = 0

if N <= K:
  print(ans)
else:
  H.sort(reverse=True)
  for i in range(K):
    H.pop(0)
  ans = sum(H)
  print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
ans = 0

if N <= K:
  print(ans)
else:
  H.sort(reverse=True)
  del H[:K]
  ans = sum(H)
  print(ans)
### BUGGY CODE ###


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

num = 0

if d > n - 1:
    num = 0
elif d == 0:
    num = (n - d)
else:
    num = (n - d) * 2


numPow = num*pow(n,m-2) * (m-1)
ans = numPow/pow(n,m)
print(ans)


# elif d == n - 1:
#     num = m - 1
# elif 2 * d > n - 1:
#     num = (n - d) * (m - 1)


# n, m, s, t = map(int, input().split())
# u = []
# v = []
# a = []
# b = []
#
# for i in range(m):
#     in1, in2, in3, in4 = map(int, input().split())
#
#     u.append(in1)
#     v.append(in2)
#     a.append(in3)
#     b.append(in4)
#
# print(u,v,a,b)




### FIXED CODE ###

import math
n, m, d = map(int, input().split())
num = 0

if d > n - 1:
    num = 0
elif d == 0:
    num = (n - d)
else:
    num = (n - d) * 2


ans = num*  (m-1)/(n*n)
print(ans)


# elif d == n - 1:
#     num = m - 1
# elif 2 * d > n - 1:
#     num = (n - d) * (m - 1)


# n, m, s, t = map(int, input().split())
# u = []
# v = []
# a = []
# b = []
#
# for i in range(m):
#     in1, in2, in3, in4 = map(int, input().split())
#
#     u.append(in1)
#     v.append(in2)
#     a.append(in3)
#     b.append(in4)
#
# print(u,v,a,b)