Harryxun/stf_run huggingface dataset:
H, W = map(int, input().split())
maze = np.array([[c == '#' for c in input()] for _ in range(H)], dtype=bool)

n_walls = np.sum(maze)
n_aisle = W * H - n_walls

d = dict(enumerate(map(dict, map(enumerate, maze))))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
adj = {(i, j): {(i + k, j + l): 1 for k, l in directions if not d.get(i + k, {}).get(j + l, True)}
       for i in range(H) for j in range(W) if not d[i][j]}
start = (0, 0)
end = (H-1, W-1)
for i in adj.keys():
    for j in adj.keys():
        for k in adj.keys():
            distance = adj.get(i, {}).get(k, np.inf) + adj.get(k, {}).get(j, np.inf)
            if adj.get(i, {}).get(j, np.inf) > distance:
                adj[i][j] = distance
print(n_aisle - adj[start][end] - 1)

### FIXED CODE ###

H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

visited = [(0, 0)]
queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop(0)
    for dy, dx in directions:
        y2, x2 = y + dy, x + dx
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        if (y2, x2) in visited:
            continue
        if maze[y2][x2] == '.':
            distances[y2][x2] = distances[y][x] + 1
            visited.append((y2, x2))
            queue.append((y2, x2))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)
import sys
  
for s in sys.stdin:
    g,r=m,n = map(int,s.split())
    while r!=0:
      g,r = r,g%r
    print(g,m//g*n)

### FIXED CODE ###

import sys
  
for s in sys.stdin:
    m,n = map(int,s.split())
    g,r = m,n
    while r!=0:
      g,r = r,g%r
    print(g,m//g*n)
s,w=map(int,input())
if s<=w:
    print('unsafe')
else:
    print('safe')


### FIXED CODE ###

s,w=map(int,input().split())
if s<=w:
    print('unsafe')
else:
    print('safe')
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
l = [0,0]
c = 0
for j in range(len(a)-1):
    if(c => 2):
        print(l[0] * l[1])
    if(a[j] == a[j+1]):
        del l[0]
        l.append(a[j])
        j += 1
        c += 1

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
l = [0,0]
c = 0
i = 0
while(i < len(a)-1):
    if(a[i] == a[i+1]):
        del l[0]
        l.append(a[i])
        i += 1
        c += 1
    if(c >= 2 or i == len(a)-2):
        i = len(a)-1
        print(l[0] * l[1])
    i += 1
print(x ** 3)

### FIXED CODE ###

x = int(input())

print(x ** 3)
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if (sqrt(a) + sqrt(b) + 1e-11 < sqrt(c)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


### FIXED CODE ###

a, b, c = map(int, input().split())
print('Yes' if 4 * a * b < (c - a - b) * (c - a - b)
      and c - a - b > 0 else 'No')
import math

n,k=map(int,input().split())

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

low=0
high=max(A)

while low!=high:
    mid=(low+high)//2
    s=0
    for i in range(n):
        s+=math.ceil(A[i]/mid)-1
    if s>k:
        low=mid+1
    else:
        high=mid


print(low)

### FIXED CODE ###

import math

n,k=map(int,input().split())

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

low=1
high=max(A)

while low!=high:
    mid=(low+high)//2
    s=0
    for i in range(n):
        s+=math.ceil(A[i]/mid)-1
    if s>k:
        low=mid+1
    else:
        high=mid


print(low)
K,X = map(int, input().split())
for _ in range(max(X-K+1,-1000000),min(1000001,b+1)):
  print(_,end=' ')

### FIXED CODE ###

K,X = map(int, input().split())
a, b = 0,0
A = []
if X - K+1 < -1000000:
  a = -1000000
else:
  a = X - K+1

if X + K-1 > 1000000:
  b = 1000000
else:
  b = X + K-1

for _ in range(a,b+1):
  print(_,end=' ')
A,B = int(input().split())
if(B%A==0):
  print(A+B)
else:
  print(B-A)

### FIXED CODE ###

A,B = map(int, input().split())
if(B%A == 0):
    print(A+B)
else:
    print(B-A)
# coding: utf-8
 
n, m, l = map(int, raw_input().split())
mat_A = [] # (n, m)
mat_B = [] # (m, l)
for i in range(n):
    mat_A.append(map(int, raw_input().split()))
 
for j in range(m):
    mat_B.append(map(int, raw_input().split()))
 
for i in range(n):
    c = [0 for g in range(n)]
    for j in range(l):
        for k in range(m):
            c[j] += mat_A[i][k] * mat_B[k][j]
    print " ".join(map(str, c))

### FIXED CODE ###

# coding: utf-8
def main():
    n, m, l = map(int, raw_input().split())
    mat_A = [] # (n, m)
    mat_B = [] # (m, l)
    for i in range(n):
        mat_A.append(map(int, raw_input().split()))

    for j in range(m):
        mat_B.append(map(int, raw_input().split()))

    for i in range(n):
        c = [0 for g in range(l)]
        for j in range(l):
            for k in range(m):
              #  print "n:{}, m:{}, l:{}".format(i,k,j)
                try:
                    c[j] += mat_A[i][k] * mat_B[k][j]
                except:
                    print "n: {}, m: {}, l: {}".format(i,k,j)
        print " ".join(map(str, c))
if __name__ == "__main__":
    main()
N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
BC = [list(map(int, list(input().split(' ')))) for i in range(Q)]

count = [0] * 10**5
for i in range(N):
    count[A[i]] += 1

s = sum(A)
for i in range(Q):
    s = s - BC[i][0] * count[BC[i][0]] + BC[i][1] * count[BC[i][0]]
    count[BC[i][1]] += count[BC[i][0]]
    count[BC[i][0]] = 0
    print(s)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
BC = [list(map(int, list(input().split(' ')))) for i in range(Q)]

count = [0] * (10**5 + 5)
for i in range(N):
    count[A[i]] += 1

s = sum(A)
for i in range(Q):
    s = s - BC[i][0] * count[BC[i][0]] + BC[i][1] * count[BC[i][0]]
    count[BC[i][1]] += count[BC[i][0]]
    count[BC[i][0]] = 0
    print(s)
a,m=map(int,input().split())
print(2*m-a)

### FIXED CODE ###

a=int(input())
m=int(input())
print(2*m-a)
n=int(input())
l=input()
cnt=0
for i in range(n-3):
  if l[i:i+3]=="ABC":
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
l=input()
cnt=0
if n<=2:
  print(0)
  exit()
for i in range(n-2):
  if l[i:i+3]=="ABC":
    cnt+=1
print(cnt)
T = input("T")
T = int(T)
X = input("X")
X = int(X)
t = T / X

### FIXED CODE ###

t,x = map(int,input().split())
print(t/x)
O = list(input())
E = list(input())
llist = list(range(1, len(E)+3, 2))
for i in range(len(E)):
    O.insert(llist[i],E[i] )
print(''.join(O))

### FIXED CODE ###

O = list(input())
E = list(input())
llist = list(range(1, len(E)*2, 2))
for num in range(len(E)):
    O.insert(llist[num], E[num])

print(''.join(O))
def anagram(list1, list2):

    anagramFlg = 1

    for i in range(len(str)):
        if list1[i] != list2[i]:
            anagramFlg = 0
            break

    return anagramFlg


n = int(input())

inputList=[]
for i in range(n):
    line = input()
    inputList.append(line)

# print(inputList)

sortedList = []
for i in range(n):
    tmpList = list(inputList[i])
    tmpList.sort()
    sortedList[i] = tmpList

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        if anagram(sortedList[i], sortedList[j]) == 1:
            cnt += 1

print(cnt)













### FIXED CODE ###


def combinatnion(num, cmb):
    nmrtr = 1
    dnmntr = 1

    for i in range(cmb):
        nmrtr = nmrtr * (num - i)
        dnmntr = dnmntr * (i + 1)

    ans = int(nmrtr/dnmntr)
    return ans

n = int(input())

inputList=[]
for i in range(n):
    line = input()
    inputList.append(line)

# print(inputList)

sortedList = []
dic = {}
for i in range(n):
    tmpList = list(inputList[i])
    tmpList.sort()
    tmpword = "".join(tmpList)

    if tmpword in dic:
        dic[tmpword] = dic[tmpword] + 1
    else:
        dic[tmpword] = 1

    # print(dic)

# print(tmpword)

cnt = 0
for val in dic.values():
    if val != 1:
        cnt += combinatnion(val, 2)

print(cnt)
n = int(input())
s = [input for _ in range(n)]
c = [i in range(1, n)]

### FIXED CODE ###

n = int(input())
b = {}
ans = 0
for _ in range(n):
  x = list(input())
  x.sort()
  x = "".join(x)
  if not x in b:
    b[x] = 0
  else:
    b[x] += 1
    ans += b[x]
print(ans)
myinput = input()
myinput_H = input()
mylist = list(map(int, myinput.split(" ")))
N = int(mylist[0])
K = int(mylist[1])
list_H = list(map(int, myinput_H.split(" ")))
for i in range(K):
    list_H.remove(max(list_H))
sum = sum(list_H)
print(sum)

### FIXED CODE ###

myinput = input()
myinput_H = input()
mylist = list(map(int, myinput.split(" ")))
N = mylist[0]
K = mylist[1]
list_H = list(map(int, myinput_H.split(" ")))
if N - K <= 0:
    print(0)
else:
    x = N - K
    list_H.sort()
    l = list_H[0:x]
    sum = sum(l)
    print(sum)
import sys

while 1:
  a , b = map(int, sys.stdin.readline().split())
  #if a == b == 0:
    break
  #elif a > b :
  #  print(b,a)
  #else :
#	print(a,b)

### FIXED CODE ###

import sys

while 1:
  a , b = sys.stdin.readline().split()
  if a == b == "0":
    break
  elif int(a) > int(b) :
    print(b,a)
  else :
    print(a,b)
N,M = map( int,input().split())
A = list(map(int,input().split())
print(max(-1,N - sum(A)))

### FIXED CODE ###

N,M = map( int, input().split() )
A = list( map(int, input().split() ))
print(max(-1, N - sum(A)))
n, m = int(input().split())
a = map(int,input().split())
for k in range(m):
  a.sort()
  s, t = int(input().split())
  for i in range(s)
  	if a[i] < t:
      a[i] = t
    else:
      break
ans = 0
for v in range(n):
  ans = a[v]
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [list(map(int,input().split())) for p in [0]*m]
b.sort(key=lambda q: -q[1])
#print(a)
#print(b)

c = 0
for s in b:
	for t in [0]*s[0]:
		#print(s)
		if c + 1 > n:
			break
		if s[1] <= a[c]:
			break
		a[c] = s[1]
		c += 1
		#print(a)
	else:
		continue
	break
print(sum(a))
s = input()
option1 = ['1' if i % 2 == 0 else '0' for i in range(len(s))]
option2 = ['0' if i % 2 == 0 else '1' for i in range(len(s))]
ans_1 = 0
ans_2 = 0
for i, c in enumerate(s):
  if option_1[i] != c:
    ans_1 += 1
  if option_2[i] != c:
    ans_2 = 0
print(min(ans_1, ans_2))

### FIXED CODE ###

s = input()
option_1 = ['1' if i % 2 == 0 else '0' for i in range(len(s))]
option_2 = ['0' if i % 2 == 0 else '1' for i in range(len(s))]
ans_1 = 0
ans_2 = 0
for i, c in enumerate(s):
  if option_1[i] != c:
    ans_1 += 1
  if option_2[i] != c:
    ans_2 += 1
print(min(ans_1, ans_2))
L, R = map(int, input().split())

if R - L >= 2019:
  print(0)
else:
  ans = 2018
  for i in range(L, R):
    for j in range(i + 1, R + 1):
      ans = min(ans, (i * j) % 2019)
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

if R - L >= 2019:
  print(0)
else:
  ans = 2018
  for i in range(L, R):
    for j in range(i + 1, R + 1):
      ans = min(ans, (i * j) % 2019)
  print(ans)
### FIXED CODE ###

#A
a, b = map(int,input().split())
print(a*b)
N=int(input())
A=map(int, input().split())
ans = 0
for i in range(N):
  ans = ans + 1/A[i]
print(1/ans)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
ans = 0
for i in range(N):
  ans = ans + 1/A[i]
print(1/ans)
N = int(input())
T = [int(input()) for _ in range(N)]
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

def lcm(a,b):
    g = gcd(a,b)
    return a*b//g

l = lcm(T[0],T[1])
for i in range(2,N):
    l = lcm(l,T[i])
print(l)

### FIXED CODE ###

"""
すべての秒数の最小公倍数を求める
Gを最大公約数として持つX,Yの最小公倍数はG*X/G*Y/G
"""
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
N = int(input())
T = [int(input()) for _ in range(N)]
tmp = T[0]
for i in range(1,N):
    t = T[i]
    g = gcd(tmp,t)
    tmp = g*(tmp//g)*(t//g)
print(tmp)
total,okasi=map(int,input().split())
sunuke=[]
for i in range(okasi):
  d=int(input())
  A=list(map(int,input().split()))
  for a in A:
    sunuke.append(input())
    
    
ans=total-len(set(sunuke))
 
print(ans)

### FIXED CODE ###

total,okasi=map(int,input().split())
sunuke=[]
for i in range(okasi):
  d=int(input())
  A=list(map(int,input().split()))
  for a in A:
    sunuke.append(a)
    
    
ans=total-len(set(sunuke))
 
print(ans)
def main():
    _, m, ab = map(int, open(0).read().split())
    ab = zip(ab[0::2], ab[1::2])
    pay = 0
    day = 0
    for t in reversed(sorted(ab, key=lambda x: (x[1], x[0]))):
        a, b = t

        # 目標日以降
        if day > m:
            break
        # 報酬が受け取れない
        if a > m or day+a > m:
            continue

        pay += b
        day += 1

    print(pay)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    # == zip(ab[0::2], ab[1::2])
    for a, b in zip(*[iter(ab)]*2):
        # 最大値が欲しいが、heappopは最小値を取り出すので-1倍しておく
        works[a].append(-b)

    candidates, pay = [], []
    for day in range(1, m+1):
        for x in works[day]:
            heappush(candidates, x)
        if candidates:
            pay.append(heappop(candidates))
    print(-sum(pay))


if __name__ == "__main__":
    main()
int(N) = input()
int(A) = input()
if N % 500 > A:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
A = int(input())
if (N % 500) > A:
    print("No")
else:
    print("Yes")
N = int(input())
A = map(int, input().split())

T = 1
xyz = [0]*3
for Ai in A:
  T = (T * sum([i==Ai for i in xyz]))%1000000007
  xyz[xyz.index(Ai)] += 1
print(T)


### FIXED CODE ###

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

T = 1
xyz = [0]*3
for Ai in A:
  if xyz.count(Ai)>0:
    T = (T * xyz.count(Ai))%1000000007
    xyz[xyz.index(Ai)] += 1
  else:
    T = 0
    break
print(T)
def main():

    N,M = map(int,input().split())
    A = [i for i in map(int,input().split())]
    A.sort()
    tmpC = 0
    targetList = []

    for i in range(M):

        element = list(map(int,input().split()))
        targetList.append(element)

    targetList.sort(key=lambda x:x[1],reverse=True)
    
    flag = False
    ans = 0
    for b,c in targetList:
        for j in range(b):
            if A[tmpC] < c and N > tmpC:
                ans += c
                tmpC +=1
            else:
                flag = True
                break
        if flag:
            break
    
    if flag < N:

        ans += sum(A[tmpC:])


    print(ans)






if __name__== "__main__":
    main() 


### FIXED CODE ###


def main():

    N,M = map(int,input().split())
    A = [i for i in map(int,input().split())]
    A.sort()
    tmpC = 0
    targetList = []

    for i in range(M):

        element = list(map(int,input().split()))
        targetList.append(element)

    targetList.sort(key=lambda x:x[1],reverse=True)
    
    flag = False
    ans = 0
    for b,c in targetList:
        for j in range(b):
            if N > tmpC and A[tmpC] < c:
                ans += c
                tmpC +=1
            else:
                flag = True
                break
        if flag:
            break
    
    if tmpC < N:

        ans += sum(A[tmpC:])


    print(ans)






if __name__== "__main__":
    main()
inp=list(map(int,input().split()))
S=inp[0]
B=inp[1]
R=inp[2]
x=S//(B+R)#brグループが何回
y=S//(B+R)
print(B*x+y)

### FIXED CODE ###

inp=input()
if inp=='AAA'or inp=='BBB':
  print('No')
else:
  print('Yes')
n=int(input())
result=100000000000000000000000000
for i in range(n):
  nn=n/(i+1)
  if (nn.is_integer() and result>nn+i-1):
    result=nn+i-1
    print(nn)
    print(i+1)
print(result)

### FIXED CODE ###

a,b=map(int,input().split())
if a>9 or b>9:
  print(-1)
else:
  print(a*b)
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
hole = [0] * (N+1)
for i in range(M):
    hole[int(input())] = 1
flg_one = False
flg_two = False
if hole[1] == 1:
    first = 0
    second = 1
    flg_one = True
elif hole[2] == 1:
    first = 1
    second = 0
    flg_two = True
else:
    first = 1
    second = 2

if flg_one and flg_two:
    print(0)
    exit()
flg = False

for i in range(3,N):
    if hole[i] == 1:
        if flg:
            print(0)
            exit()
        flg = True
        first = second
        second = 0
        flg = False
        continue
    tmp = first + second
    tmp %= 1000000007
    first = second
    second = tmp
    flg = False
tmp = first + second
tmp %= 1000000007
print(tmp)

### FIXED CODE ###

import sys
N, M = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1
if ans[0] == -1 and ans[1] == -1:
    print(0)
    sys.exit()
elif ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

if N != 2:
    for i in range(2,N):
        if ans[i] == -1:
            ans[i] = 0
        else:
            ans[i] = (ans[i-1]  + ans[i-2]) % mod
print(ans[N-1])
colatz=[1,2,4]
colatz.append(int(input()))
b=3
while colatz[b]!=colatz[b-3]:
    if colatz[b]%2==0:
        colatz.append(colatz[b]/2)
    else: colatz.append(3*colatz[b]+1)
    b=b+1
print(b+1)

### FIXED CODE ###

a=list(map(int,input().split()))
print('{:.0f}'.format(a[0]*a[1]/2))
import math
n, m = input().split()
m = int(m)
n = int(n)
if n == 1:
	nNum = 0
else:
	nNum = math.factorial(n) / (math.factorial(n-2) * math.factorial(2))
if m == 1:
	mNum = 0
else:
	mNum = math.factorial(m) / (math.factorial(m-2) * math.factorial(2))
print(int(mNum + nNum))

### FIXED CODE ###

import math
n, m = input().split()
m = int(m)
n = int(n)
if n == 1 or n == 0:
	nNum = 0
else:
	nNum = math.factorial(n) / (math.factorial(n-2) * math.factorial(2))
if m == 1 or m == 0:
	mNum = 0
else:
	mNum = math.factorial(m) / (math.factorial(m-2) * math.factorial(2))
print(int(mNum + nNum))
n = int(input())
import math
from functools import reduce

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

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

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)


num = []
for i in range(n):
    num.append(int(input()))
print(lcm(num))


### FIXED CODE ###

n = int(input())
def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a
# 最小公倍数
def lcm(a,b):
    return a // gcd(a,b) * b

ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(ans,t)
print(ans)
N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

res = [] # solution for each key in A
res_list = {} # solution for each value in A

# counter ver
A_c = Counter(A)
l = len(A_c)

def ncr(j):
  return math.factorial(j) // math.factorial(2) // math.factorial(j - 2) if j >= 2 else 0

# store ncr for each value 
combs = {k: ncr(v) for k, v in A_c.items()}

s = sum(combs.values())
  
for m in A_c.keys():
  cnt = combs[m]

  n = s
  n -= cnt # the only inaccurate entry
  n += ncr(A_c[m] - 1)
  res_list[m] = n

for k in range(N):
  print(res_list[A[k]])
# print('\n'.join([str(s) for s in res]))

### FIXED CODE ###

M, N = [int(k) for k in input().split(' ')]
import math 
res = 0

if N >= 2:
  res += (math.factorial(N) // math.factorial(2) // math.factorial(N - 2))

if M >= 2:
  res += (math.factorial(M) // math.factorial(2) // math.factorial(M - 2))

print(res)
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
C={0:1}
ans = 3
for i in range(1,N):
    a = A[i]
    if a not in C:
        C[a]=0
    C[a] += 1
    if C[a]==1:
        ans = (ans*C[a-1])%p
    elif a==0 and C[a]==2:
        ans = ans*2
    elif a>0 and C[a]==2:
        ans = (ans*(C[a-1]-1))%p
print(ans)

### FIXED CODE ###

p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
cnt = 1
cnt0 =0
C = {i:0 for i in range(N)}
B = []
for i in range(N):
    a = A[i]
    if a==0:
        cnt = (cnt*(3-cnt0))%p
        cnt0 += 1
    else:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
    C[a] += 1
print(cnt)
import fractions

def prime_divisor(n):
  prime_divisor_set = {1}
  end = int(n ** 0.5) + 1
  for i in range(2, 10 ** 5 + 1):
    if not (n % i):
      prime_divisor_set.add(i)
      while (n % i) == 0:
        n //= i
  return prime_divisor_set


a, b = map(int, input().split())
s1, s2 = prime_divisor(a), prime_divisor(b)
ans = len(s1 & s2)
print(len(prime_divisor(fractions.gcd(a, b))))


### FIXED CODE ###

n = int(input())
if n % 2:
  print((n+1) / (n * 2))
else:
  print(0.5)
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))

if __name__ == "__main__":
    total_fee = int(input('total_fee:'))

    while (total_fee != 0):
        coins = input('total_coins:')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)

### FIXED CODE ###

import math
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)
 
    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])
 
    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
 
if __name__ == "__main__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500?????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
import math
a, b, c, d = (int(x) for x in input().split())
def func(div):
    if (a/div).is_integer(): c_1 = int(a/div)
    else: c_1 = a // div + 1
    c_2 = b // div
    return int(c_2 - c_1 + 1)
print(int((b - a + 1) - func(c) - func(d) + func(c*d//math.gcd(c, d))))

### FIXED CODE ###

import fractions
def lcm(a,b):
  return a*b //fractions.gcd(a, b)

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

b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
print((B-(A-1))-(b_num-a_num))