Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# 答案
N,Q = map(int,input().split())
S = input()
l,r = 0,0
csum = [0]*(N+1)

# 累積和
for ctr in range(N):
    if S[ctr]=='A' and S[ctr+1]=='C':
        csum[ctr+1] = csum[ctr] + 1
    else:
        csum[ctr+1] = csum[ctr]

# 出力
for ctr in range(Q):
    l,r=map(int,input().split())
    print(csum[r-1] - csum[l-1])

Fixed submission:
# 答案
N,Q = map(int,input().split())
S = input()
l,r = 0,0
csum = [0]*(N+1)

# 累積和
for ctr in range(N):
    if ctr == (N-1):
        csum[ctr+1] = csum[ctr]
    elif S[ctr]=='A' and S[ctr+1]=='C':
        csum[ctr+1] = csum[ctr] + 1
    else:
        csum[ctr+1] = csum[ctr]

# 出力
for ctr in range(Q):
    l,r=map(int,input().split())
    print(csum[r-1] - csum[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S = input()
tmp = ''
kesu = ''
ans = 0
for i in range(Q):
    LR = list(map(int, input().strip().split(' ')))
    ans = 0
    tmp = S[LR[0]-1:LR[1]]
    kesu = tmp.replace('AC', '')
    ans = (LR[1]-LR[0]+1-len(kesu))/2
    print(int(ans))

Fixed submission:
# 答案
N,Q = map(int,input().split())
S = input()
l,r = 0,0
csum = [0]*(N+1)

# 累積和
for ctr in range(N):
    if ctr == (N-1):
        csum[ctr+1] = csum[ctr]
    elif S[ctr]=='A' and S[ctr+1]=='C':
        csum[ctr+1] = csum[ctr] + 1
    else:
        csum[ctr+1] = csum[ctr]

# 出力
for ctr in range(Q):
    l,r=map(int,input().split())
    print(csum[r-1] - csum[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S = input()
tmp = ''
kesu = ''
ans = 0
LR = []
for i in range(Q):
    array = list(map(int, input().strip().split(' ')))
    LR.append(array)
    
for i in range(Q): # 問iを解く
    ans = 0
    tmp = S[LR[i][0]-1:LR[i][1]]
    kesu = tmp.replace('AC', '')
    ans = (LR[i][1]-LR[i][0]+1-len(kesu))/2
    print(int(ans))

Fixed submission:
# 答案
N,Q = map(int,input().split())
S = input()
l,r = 0,0
csum = [0]*(N+1)

# 累積和
for ctr in range(N):
    if ctr == (N-1):
        csum[ctr+1] = csum[ctr]
    elif S[ctr]=='A' and S[ctr+1]=='C':
        csum[ctr+1] = csum[ctr] + 1
    else:
        csum[ctr+1] = csum[ctr]

# 出力
for ctr in range(Q):
    l,r=map(int,input().split())
    print(csum[r-1] - csum[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
A,B = map(int,input().split())
sum = 0
for cnt in range(A,B+1):
    sum = sum ^ cnt
print(sum)

Fixed submission:
def xorsum(x):
    if x % 4 == 0:
        return(x)
    if x % 4 == 1:
        return(1)
    if x % 4 == 2:
        return(x+1)
    if x % 4 == 3:
        return(0)
    
A, B = map(int,input().split())

if A == 0:
    print(xorsum(B))
else:
    print(xorsum(B)^xorsum(A-1))
Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())

num_moto = int(len(s))

for ctr in range(5000):
    if int(len(s)) == 0:
        break
    s = s.replace('10','')
    s = s.replace('01','')
    
num_kekka = int(len(s))
print(num_moto - num_kekka)

Fixed submission:
s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))

Buggy python submission (verdict: Runtime Error):
s = str(input())

num_moto = int(len(s))

for ctr in range(500)
    if int(len(s)) == 0:
        break
    s = s.replace('10','')
    s = s.replace('01','')
    
num_kekka = int(len(s))
print(num_moto - num_kekka)

Fixed submission:
s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))

Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())

num_moto = int(len(s))

while True:
    if s.find('10') == -1 and s.find('01') == -1:
        break
    if int(len(s)) == 0:
        break
    s = s.replace('10','')
    s = s.replace('01','')
    
num_kekka = int(len(s))
print(num_moto - num_kekka)

Fixed submission:
s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))

Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())

num_moto = int(len(s))
flag = True

for ctr in range(50000):
    if s.find('10') == -1 or s.find('01') == -1 or int(len(s)) == 0:
        flag == False
    if flag == True:
        s = s.replace('10','')
        s = s.replace('01','')
        
num_kekka = int(len(s))
print(num_moto - num_kekka)

Fixed submission:
s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(min(A),0,-1):
    if all( A[c] % i == 0 for c in range(N)):
        ans = i
        break   
print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A) # とりあえず並び替えておく
tmp = 0
for i in range(N-1):
    while A[i]>0:
        tmp = A[i]
        A[i] = A[i+1] % A[i]
        A[i+1] = tmp
print(A[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
H = list(map(int,input().split()))

inf = float('inf')

dp = [inf]*(10**5+10)
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i+j >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i] + abs(H[i+j] - H[i]))

print(dp[N-1])


Fixed submission:
N, K = map(int,input().split())
H = list(map(int,input().split()))

inf = float('inf')

dp = [inf]*(10**5+10)
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i+j >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i] + abs(H[i+j] - H[i]))

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
K = int(input())
N = len(S)
subst = set()
for i in range(1,N+1):
    for j in range(N-i+1):
        subst.add(S[j:j+i])
L = sorted(list(subst))
print(L[K-1])


Fixed submission:
S = input()
K = int(input())
N = len(S)
subst = set()
for i in range(1,K+1):
    for j in range(N-i+1):
        subst.add(S[j:j+i])
L = sorted(list(subst))
print(L[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
L = []
for i in range(n):
    if i % 2 == 0:
        L = [a[i]] + L
    else:
        L = L + [a[i]]
if n % 2 == 0:
    L.reverse()
print(" ".join(map(str,L)))


Fixed submission:
from collections import deque
n = int(input())
a = list(map(int,input().split()))
q = deque()
for i in range(n):
    if i % 2 == 0:
        q.appendleft(a[i])
    else:
        q.append(a[i])
if n % 2 == 0:
    q.reverse()
print(*q)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
first_dest_list = list()
pair_list = list()

for _ in range(M):
    a, b = list(map(int, input().split()))

    if a == 1:
        first_dest_list.append(b)
    elif b == 1:
        first_dest_list.append(a)

    pair_list.append((a, b))


len_first_dest = len(first_dest_list)
result = 'IMPOSSIBLE'
for first_dest in first_dest_list:
    for i in range(M):
        if first_dest in pair_list[i] and N in pair_list[i]:
            result = 'POSSIBLE'
            break
    if result == 'POSSIBLE':
        break

print(result)


Fixed submission:
N, M = list(map(int, input().split()))
dest_list_1 = list()
dest_list_2 = list()

for _ in range(M):
    a, b = list(map(int, input().split()))

    if a == 1:
        dest_list_1.append(b)
    elif b == 1:
        dest_list_1.append(a)
    elif a == N:
        dest_list_2.append(b)
    elif b == N:
        dest_list_2.append(a)

len_dest_1 = len(dest_list_1)
len_dest_2 = len(dest_list_2)

if len(set(dest_list_1 + dest_list_2)) == len_dest_1 + len_dest_2:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a_list = list(map(int, input().split()))

min_diff = abs(sum(a_list[:1]) - sum(a_list[1:]))
for i in range(2, N):
    diff = abs(sum(a_list[:i]) - sum(a_list[i:]))
    min_diff = min(min_diff, diff)
print(min_diff)


Fixed submission:
N = int(input())
a_list = list(map(int, input().split()))

a_sum = sum(a_list)
l_a_sum = a_list[0]
min_diff = abs(a_sum - 2 * l_a_sum)
for i in range(1, N-1):
    l_a_sum += a_list[i]
    min_diff = min(min_diff, abs(a_sum - 2 * l_a_sum))
print(min_diff)
Buggy python submission (verdict: Runtime Error):
group_list = [0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2]

x, y = list(map(int, input().split()))

if group_list[x] == group_list[y]:
    print('Yes')
else:
    print('No')



Fixed submission:
a_group = [1, 3, 5, 7, 8, 10, 12]
b_group = [4, 6, 9, 11]
c_group = [2]

x, y = list(map(int, input().split()))

if x in a_group and y in a_group:
    print('Yes')
elif x in b_group and y in b_group:
    print('Yes')
elif x in c_group and y in c_group:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
big_array = list()

for _ in range(N):
    a, b = list(map(int, input().split()))
    big_array += [a]*b

big_array.sort()

print(big_array[K-1])


Fixed submission:
N, K = list(map(int, input().split()))
val_dict = dict()

for _ in range(N):
    a, b = list(map(int, input().split()))
    val_dict[a] = val_dict.get(a, 0) + b

val_keys = sorted(val_dict.keys())

K_rest = K
for key in val_keys:
    K_rest -= val_dict[key]
    if K_rest <= 0:
        print(key)
        break
Buggy python submission (verdict: Runtime Error):
N, W = list(map(int, input().split()))
w_list = list()
v_list = list()

for _ in range(N):
    w, v = list(map(int, input().split()))
    w_list.append(w)
    v_list.append(v)

cases = [[0]*(W+1)]

for i_item in range(1, N+1):
    case = [0]
    w = w_list[i_item-1]
    v = v_list[i_item-1]
    for i_w in range(1, W+1):
        if w > i_w:
            val = cases[i_item-1][i_w]
        else:
            val = max(cases[i_item-1][i_w], cases[i_item-1][i_w-w] + v)
        case.append(val)
    cases.append(case)

print(cases[N][W])



Fixed submission:
N, W = list(map(int, input().split()))
w0, v0 = list(map(int, input().split()))
w_dict = dict()
w_dict[w0] = [v0]
w_dict[w0+1] = list()
w_dict[w0+2] = list()
w_dict[w0+3] = list()

for _ in range(N-1):
    w, v = list(map(int, input().split()))
    w_dict[w].append(v)

w_dict[w0]   = sorted(w_dict[w0],   reverse=True)
w_dict[w0+1] = sorted(w_dict[w0+1], reverse=True)
w_dict[w0+2] = sorted(w_dict[w0+2], reverse=True)
w_dict[w0+3] = sorted(w_dict[w0+3], reverse=True)

max_sum_v = 0
for i_0 in range(len(w_dict[w0])+1):
    for i_1 in range(len(w_dict[w0+1])+1):
        for i_2 in range(len(w_dict[w0+2])+1):
            for i_3 in range(len(w_dict[w0+3])+1):
                sum_w = w0 * i_0 + (w0 + 1) * i_1 + (w0 + 2) * i_2 + (w0 + 3) * i_3
                if sum_w > W:
                    continue
                sum_v = sum(w_dict[w0][:i_0])   + \
                        sum(w_dict[w0+1][:i_1]) + \
                        sum(w_dict[w0+2][:i_2]) + \
                        sum(w_dict[w0+3][:i_3])
                max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    N = int(input())
    a_list = get_a_list()

    a_list.sort(reverse=True)

    sum_second_a = 0
    
    while len(a_list) > 0:
        a_list.pop(0)
        sum_second_a += a_list.pop(0)
        a_list.pop(-1)

    print(sum_second_a)

def get_a_list():
    a_list = []
    strs = input().split()

    for a in strs:
        a_list.append(int(a))

    return a_list


if __name__ == '__main__':
    main()


Fixed submission:

def main():
    N = int(input())
    a_list = get_a_list()

    a_list.sort(reverse=True)

    sum_second_a = 0
    
    a_list = a_list[:2*N]
    for i in range(1, 2*N, 2):
        sum_second_a += a_list[i]

    print(sum_second_a)

def get_a_list():
    a_list = []
    strs = input().split()

    for a in strs:
        a_list.append(int(a))

    return a_list


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):

def main():
    N = int(input())
    a_list = get_a_list()

    a_list.sort(reverse=True)

    sum_second_a = 0
    
    import pdb; pdb.set_trace()
    while len(a_list) > 0:
        a_list.pop(0)
        sum_second_a += a_list.pop(0)
        a_list.pop(-1)

    print(sum_second_a)

def get_a_list():
    a_list = []
    strs = input().split()

    for a in strs:
        a_list.append(int(a))

    return a_list


if __name__ == '__main__':
    main()


Fixed submission:

def main():
    N = int(input())
    a_list = get_a_list()

    a_list.sort(reverse=True)

    sum_second_a = 0
    
    a_list = a_list[:2*N]
    for i in range(1, 2*N, 2):
        sum_second_a += a_list[i]

    print(sum_second_a)

def get_a_list():
    a_list = []
    strs = input().split()

    for a in strs:
        a_list.append(int(a))

    return a_list


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# def gcd(a_gcd, b_gcd):
#     while b_gcd != 0:
#         a_gcd, b_gcd = b_gcd, a_gcd % b_gcd
#     return a_gcd
#
#
# def lcm(a_lcm, b_lcm):
#     return a_lcm * b // gcd(a_lcm, b_lcm)
#
#
# def max_sum(N_max_sum, a_max_sum):
#     dp = [0] * (N_max_sum + 1)
#     for i in range(N_max_sum):
#         dp[i + 1] = max(dp[i], dp[i] + a_max_sum[i])
#     return dp[N]
#
#
# def knapsack(N_knapsack, W, weight, value):
#     inf = float("inf")
#     dp = [[-inf for _ in range(W+1)] for j in range(N_knapsack + 1)]
#     for i in range(W+1):
#         dp[0][i] = 0
#
#     for i in range(N_knapsack):
#         for w in range(W+1):
#             if weight[i] <= w:
#                 dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
#             else:
#                 dp[i+1][w] = dp[i][w]
#     return dp[N_knapsack][W]
#
#
# class UnionFind:
#     def __init__(self, n):
#         self.par = [i for i in range(n+1)]
#         self.rank = [0] * (n+1)
#
#     # 検索
#     def find(self, x):
#         if self.par[x] == x:
#             return x
#         else:
#             self.par[x] = self.find(self.par[x])
#             return self.par[x]
#
#     # 併合
#     def union(self, x, y):
#         x = self.find(x)
#         y = self.find(y)
#         if self.rank[x] < self.rank[y]:
#             self.par[x] = y
#         else:
#             self.par[y] = x
#             if self.rank[x] == self.rank[y]:
#                 self.rank[x] += 1
#
#     # 同じ集合に属するか判定
#     def same_check(self, x, y):
#         return self.find(x) == self.find(y)
#
# S = input()
# N = int(input())
# A = list(map(int, input().split()))

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []

for i in range(M):
    l, r = map(int, input().split())
    B.append(l)
    C.append(r)



for i in range(M):
    A.extend([C[i]]*B[i])

A.sort()
A.reverse()

print(sum(A[:N]))







Fixed submission:

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

BC = []

for i in range(M):
    l, r = map(int, input().split())
    BC.append((r, l))


for a in A:
    BC.append((a, 1))

BC.sort()
BC.reverse()

count = 0
ans = 0


for bc in BC:
    if (bc[1] + count) <= N:
        count += bc[1]
        ans += bc[0] * bc[1]
    else:
        ans += max(0, bc[0] * (N - count))
        break

print(ans)
Buggy python submission (verdict: Runtime Error):
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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


gcdNM = math.gcd(N, M)
lcmNM = lcm(N, M)

isGood = True
for i in range(gcdNM):
    if S[i * N // (gcdNM)] != T[i * M // (gcdNM)]:
        isGood = False
        break

if isGood and T[0] == S[0]:
    print(lcmNM)
else:
    print(-1)


Fixed submission:

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

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

gcdNM = gcd(N, M)
lcmNM = lcm(N, M)

isGood = True
for i in range(gcdNM):
    if S[i * N // (gcdNM)] != T[i * M // (gcdNM)]:
        isGood = False
        break

if isGood and T[0] == S[0]:
    print(lcmNM)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
import functools
import math

N, X = map(int, input().split())
x = list(map(int, input().split()))
subX = []

for x_i in x:
    subX.append(abs(x_i - X))

print(functools.reduce(math.gcd, subX))

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

N, X = map(int, input().split())
x = list(map(int, input().split()))
ans = abs(x[0] - X)

for i in range(len(x)):
    ans = gcd(ans, abs(x[i] - X))

print(ans)

Buggy python submission (verdict: Runtime Error):
import functools
import math

N, X = map(int, input().split())
x = list(map(int, input().split()))
subX = []

for x_i in x:
    subX.append(abs(x_i - X))

print(functools.reduce(math.gcd, subX))

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

N, X = map(int, input().split())
x = list(map(int, input().split()))
ans = abs(x[0] - X)

for i in range(len(x)):
    ans = gcd(ans, abs(x[i] - X))

print(ans)

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(function.gcd, numbers)

def gcd_list(numbers):
    return reduce(function.gcd, numbers)

N, X = map(int, input().split())
x = list(map(int, input().split()))
subX = []

for x_i in x:
    subX.append(abs(x_i - X))

print(gcd_list(subX))

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

N, X = map(int, input().split())
x = list(map(int, input().split()))
ans = abs(x[0] - X)

for i in range(len(x)):
    ans = gcd(ans, abs(x[i] - X))

print(ans)

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N, X = map(int, input().split())
x = list(map(int, input().split()))
subX = []

for x_i in x:
    subX.append(abs(x_i - X))

print(gcd_list(subX))

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

N, X = map(int, input().split())
x = list(map(int, input().split()))
ans = abs(x[0] - X)

for i in range(len(x)):
    ans = gcd(ans, abs(x[i] - X))

print(ans)
Buggy python submission (verdict: Runtime Error):
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

N = int(input())
A = list(map(int, input().split()))
print(A)
ans = []

if N == 1:
    ans.append(A[0])
else:
    kuri = max(N//2, 10)
    for i in range(1, N+1):
        ans += Medi(A, i)
        so = ans
        so.sort()
        print(so)


print(statistics.median_high(ans))

Fixed submission:
# S = input()
# N = int(input())
N, K = map(int, input().split())
X = list(map(int, input().split()))
# LR = [list(map(int, input().split())) for _ in range(M)]

ans = 10000000000

if K == 1:
    for i in range(N):
        if ans > abs(X[i]):
            ans = abs(X[i])
else:
    for i in range(N - K+1):
        left = X[i]
        right = X[i + K - 1]
        sum = 0

        if abs(left) <= abs(right):
            sum += abs(left)
        else:
            sum += abs(right)

        sum += abs(left - right)

        if ans > sum:
            ans = sum

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
n, m, d = map(int, input().split())
pownum = pow(n,m-2)
num = 0

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


numPow = num*pownum * (m-1)
ans = numPow/(pownum*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)




Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):

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 submission:
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)
Buggy python submission (verdict: Runtime Error):

K = int(input())
aaa = 1
ans_array = []

def sunuke(n):
    re = 0
    tmp = n
    while n:
        re += n % 10
        n = n//10
    re = tmp/re
    print(re)

def print_sunuke():
    global aaa
    num = aaa % 10
    if num == 0:
        aaa += 1
        print_sunuke()
        return
    nine = aaa // 10
    ans = str(num) + "9" * nine
    aaa += 1
    ans_array.append(int(ans))




for i in range(10000):

    print_sunuke()

ans_array.append(1899)
ans_array.append(2899)
ans_array.append(3899)
ans_array.append(4899)
ans_array.append(5899)
ans_array.append(6899)
ans_array.append(7899)
ans_array.append(8899)
ans_array.append(9899)
ans_array.append(18999)
ans_array.append(28999)
ans_array.append(38999)
ans_array.append(48999)
ans_array.append(58999)
ans_array.append(68999)
ans_array.append(78999)
ans_array.append(88999)
ans_array.append(98999)
ans_array.append(189999)
ans_array.append(289999)
ans_array.append(389999)
ans_array.append(489999)
ans_array.append(589999)
ans_array.append(689999)
ans_array.append(789999)
ans_array.append(889999)
ans_array.append(989999)
ans_array.append(1899999)
ans_array.append(2899999)
ans_array.append(3899999)
ans_array.append(4899999)
ans_array.append(5899999)
ans_array.append(6899999)
ans_array.append(7899999)
ans_array.append(8899999)
ans_array.append(9899999)

ans_array.append(18999999)
ans_array.append(28999999)
ans_array.append(38999999)
ans_array.append(48999999)
ans_array.append(58999999)
ans_array.append(68999999)
ans_array.append(78999999)
ans_array.append(88999999)
ans_array.append(98999999)

ans_array.append(189999999)
ans_array.append(289999999)
ans_array.append(389999999)
ans_array.append(489999999)
ans_array.append(589999999)
ans_array.append(689999999)
ans_array.append(789999999)
ans_array.append(889999999)
ans_array.append(989999999)
ans_array.append(1899999999)
ans_array.append(2899999999)
ans_array.append(3899999999)
ans_array.append(4899999999)
ans_array.append(5899999999)
ans_array.append(6899999999)
ans_array.append(7899999999)
ans_array.append(8899999999)
ans_array.append(9899999999)

ans_array.append(18999999999)
ans_array.append(28999999999)
ans_array.append(38999999999)
ans_array.append(48999999999)
ans_array.append(58999999999)
ans_array.append(68999999999)
ans_array.append(78999999999)
ans_array.append(88999999999)
ans_array.append(98999999999)


ans_array.sort()

for i in range(K):
    print(ans_array[i])





Fixed submission:
# n = int(input())
N, K = map(int, input().split())
A = list(map(int, input().split()))
# d = [list(map(int, input().split())) for _ in range(n)]
# s = input()

if (N-1)%(K-1):
    ans =(N-1)//(K-1)+1
else:
    ans = (N-1) // (K - 1)


print(ans)


# K = int(input())