Harryxun/stf_run huggingface dataset:
import collections

def get_lim(n):
    # for i in range(n):
    #     if i * i > n:
    #         return i + 1
    return pow(10, int((len(str(n)) / 2)))

def prime_factor(n, length):
    ass = collections.defaultdict(int)
    # break_num = pow()
    # for i in range(2,int(n**0.5)+1):
    lim = get_lim(n)
    for i in range(2, lim + 1):
        # print(pow(i, length),  n)
        # if pow(i, length) > n:
        #     break
        if i > n or n == 1:
            break
        # i = pow(i, num)
        while n % i==0:
            ass[i] += 1
            n = n//i

    if n != 1:
        ass[n] += 1
    return ass

if __name__ == '__main__':
    length, num = list(map(int, input().split()))

    if length == 1:
        print(num)
    else:

        soinnsuu = prime_factor(num, length)
        ans = 1
        # print(soinnsuu)
        for data in soinnsuu.keys():
            if soinnsuu[data] >= length:
               ans *= data
        print(ans)

### FIXED CODE ###

import math


def main():
    a = int(input())
    b = int(input())
    print(a ** 2 - b)





if __name__ == '__main__':
    main()
a,b,t=map(int,input().split())
print(int(((t+0.5)//a*b))

### FIXED CODE ###

a,b,t=map(int,input().split())
x=((t+0.5)//a)
print(int(x*b))
n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = []

for i in range(0,n):
	kari = 0
	for j in range(i,n-1):
		if h[j] < h[j+1]:
			break
		kari += 1
	ans.appened(kari)

print(max(ans))

### FIXED CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split(" ")))

ans = 0

kari = 0
i = 0
for m in range(0,n-1):
	if h[m] >= h[m+1]:
		kari += 1
	else:
		kari = 0
	if ans < kari:
		ans = kari



print(ans)
import sys

argv = sys.argv
a = int(argv[1])
b = int(argv[2])
t = int(argv[3]) + 0.5 - a

r = 0

while t > 0:
    r += b
    t -= a

print(r)


### FIXED CODE ###

args = input()
args = args.split(' ')

a = int(args[0])
b = int(args[1])
t = int(args[2]) + 0.5 - a

r = 0

while t > 0:
    r += b
    t -= a

print(r)
# dict形式で既出分をもたせる
N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
test_dict = {}
result = ''
for temp in a:
    if test_dict.get(string[temp[0]-1:temp[1]]):
        result += '\n' + str(test_dict.get(string[temp[0]-1:temp[1]]))
        continue
    test_dict[string[temp[0]-1:temp[1]]] = string[temp[0]-1:temp[1]].count('AC')
    result += '\n' + str(test_dict[string[temp[0]-1:temp[1]]])

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
a, b, c = map(int, input().split())
num = a*100 + b*10 + c
if num % 4 == 0:
  print("YES)
else:
  @rint("NO")

### FIXED CODE ###

# スペース区切りの整数の入力
a, b, c = map(int, input().split())
num = a*100 + b*10 + c
if num % 4 == 0:
  print("YES")
else:
  print("NO")
import sys
input = sys.stdin.readline
from operator import itemgetter

tmp = []
tree = []

def dfs(node, depth, fr):
    global tmp, tree
    tree[node] = (fr, depth)
    for i, c in tmp[node]:
        if i != fr:
            dfs(i, depth+c, node)

def main():
    global tmp, tree
    n = int(input().strip())
    tmp = [[] for _ in range(n)]
    tree = [0] * n
    for _ in range(n-1):
        a, b, c = map(int, input().strip().split())
        a -= 1
        b -= 1

        if b > a:
            a, b = b, a
        tmp[a].append((b, c))
        tmp[b].append((a, c))

    q, k = map(int, input().strip().split())
    k -= 1
    dfs(k, 0, -1)
    # print(tmp)
    # print(tree)
    for _ in range(q):
        x, y = map(lambda x: x-1, map(int, input().strip().split()))
        print(tree[x][1] + tree[y][1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

tmp = []
tree = []

def dfs(node, depth, fr):
    global tmp, tree
    tree[node] = (fr, depth)
    for i, c in tmp[node]:
        if i != fr:
            dfs(i, depth+c, node)

def main():
    global tmp, tree
    n = int(input().strip())
    tmp = [[] for _ in range(n)]
    tree = [0] * n
    for _ in range(n-1):
        a, b, c = map(int, input().strip().split())
        a -= 1
        b -= 1

        if b > a:
            a, b = b, a
        tmp[a].append((b, c))
        tmp[b].append((a, c))

    q, k = map(int, input().strip().split())
    k -= 1
    dfs(k, 0, -1)
    # print(tmp)
    # print(tree)
    for _ in range(q):
        x, y = map(lambda x: x-1, map(int, input().strip().split()))
        print(tree[x][1] + tree[y][1])


if __name__ == '__main__':
    main()
a,n=map(int,input().split())
if a%2==0:
    print(" ".join(str(a//2)+str(a)*(n-1)))
else:
    d=[(a+1)//2]*n
    r=n-1
    for i in range((n-1)//2+1):
        if d[r]==1:
            d[r]=0
            r-=1
        else:
            d=d[:r]+[d[r]-1]+[a]*(n-r-1)
            r=n-1
    while d[-1]==0:
        d.pop()
    print(" ".join(str(i)for i in d))

### FIXED CODE ###

a,n=map(int,input().split())
if a%2==0:
    print(*[a//2]+[a]*(n-1))
else:
    d=[(a+1)//2]*n
    for i in range(n//2):
        if d[-1]==1:
            d.pop()
        else:
            d[-1]-=1
            d.extend([a]*(n-len(d)))
    print(" ".join(str(i)for i in d))
s = int(input())
w = int(input())
if(w >= s):
    print("unsafe")
else:
    print("safe")


### FIXED CODE ###

s,w = map(int,input().split())
if(w >= s):
    print("unsafe")
else:
    print("safe")
while True :
	x,y = map(int,raw_input.split())
	if x==0 and y==0 :
		break
	else :
		if a<b :
			print '%d %d' %(a,b)
		else :
			print '%d %d' %(b,a)

### FIXED CODE ###

while True :
	x,y = map(int,raw_input().split())
	if x==0 and y==0 :
		break
	else :
		if x<y :
			print'%d %d' %(x,y)
		else :
			print'%d %d' %(y,x)
L, R, d = [int(x) for x in input().split()]
compteur = 0

for i in range(L, R+1):
  if i%d == 0:
    k += 1
   

### FIXED CODE ###

L, R, d = [int(x) for x in input().split()]
compteur = 0

for i in range(L, R+1):
  if i%d == 0:
    compteur += 1
   
print(compteur)
n = int(input())
tenants = {}
for i in range(n):
  tenant = list(map(int,input().split()))
  key = f'{b} {f} {r}'
  if key in d:
    d[key] += v
  else:
    d[key] = v
    
  b = tenant[0]
  f = tenant[1]
  r = tenant[2]
  v = tenant[3]
    
for b in range(1,5):
  for f in range(1,4):
    for r in range(1,11):
      key = f'{b} {f} {r}'
      if key in d:
        print(" "+str(d[key]),end="")
      else:
        print(" "+str(0),end="")
      if r == 10:
        print()
      if r == 10 and f == 3 and b != 4:
        print('####################')


### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
  [b, f, r, v] = list(map(int,input().split()))
  key = f'{b} {f} {r}'
  if key in d:
    d[key] += v
  else:
    d[key] = v
    
for b in range(1,5):
  for f in range(1,4):
    for r in range(1,11):
      key = f'{b} {f} {r}'
      if key in d:
        print(" "+str(d[key]),end="")
      else:
        print(" "+str(0),end="")
      if r == 10:
        print()
      if r == 10 and f == 3 and b != 4:
        print('####################')
N = input()
if N%2 == 1:
    print(2*N)
else:
    print(N)

### FIXED CODE ###

N = int(input())
if N%2 == 1:
    print(2*N)
else:
    print(N)
a,b,h,m = map(int,input().split())
import math
mi = 360*(((60*h + m) % 60) / 60)
hour = 360*(((60*h + m) % 720) / 720)
cos = 0
ans = 0
if hour > mi:
	cos = math.cos(math.radians(hour - mi))
	ans = (a**2 + b**2 - 2*a*b*cos)**0.5
elif hour == mi:
	ans = 0
elif hour +180 > mi:
	cos = math.cos(math.radians(mi - hour))
	ans = (a**2 + b**2 - 2*a*b*cos)**0.5
elif hour + 180 == mi:
	ans = a + b
elif hour + 180 < mi:
	cos.hour = math.cos(math.radians(hour - mi + 360))
	ans = (a**2 + b**2 - 2*a*b*cos)**0.5
print(cos)
print(ans)


### FIXED CODE ###

import math
a,b,h,m = map(int,input().split())

ans = 0
cos = 0
mi = m/60 * 360 #分針の角度
hour = (60*h + m)/720 * 360 #時針の角度

cos = math.cos(math.radians(hour - mi))
ans = a*a + b*b -2*a*b*cos
#余弦定理
ans = ans ** (1/2)
print(ans)
N, X = map(int, input().split())
L = list(input().split())
D = 1
l = [0]
while max(l) < X:
  if int(l[-1]) + int(L[D - 1]) <= X:
    l.append(int(l[-1]) + int(L[D - 1]))
    D += 1
  else:
    break
print(len(l))

### FIXED CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))
l = [0]
if L[0] <= X:
  l.append(L[0])
  for x in range(N - 1):
    a = l[-1] + L[x + 1]
    if a <= X:
      l.append(a)
    elif a > X:
      break

print(len(l))
import math
a,b,c,d = map(int,input().split())
#c_d = math.floor(((c*d)//(math.gcd(c,d))))
c_d = (c*d)//(math.gcd(c,d))
#print((math.gcd(c,d)))
a_c = (a-1) // c
a_d = (a-1) // d
a_c_d = (a-1) // c_d
a_ans = (a-1) - a_c - a_d + a_c_d
#ans1 = (a_c + a_d - a_c_d)
#print(c_d)
b_c = b // c
b_d = b // d
b_c_d = b // c_d
b_ans = b - b_c - b_d + b_c_d
#ans2 = (b_c + b_d -b_c_d)
#print(ans2)
#print(math.floor((b-a+1)-(ans2-ans1)))
print(math.floor(b_ans-a_ans))

### FIXED CODE ###

import math
import fractions
a,b,c,d = map(int,input().split())
#c_d = math.floor(((c*d)//(math.gcd(c,d))))
c_d = (c*d)//(fractions.gcd(c,d))
#print((math.gcd(c,d)))
a_c = (a-1) // c
a_d = (a-1) // d
a_c_d = (a-1) // c_d
a_ans = (a-1) - a_c - a_d + a_c_d
#ans1 = (a_c + a_d - a_c_d)
#print(c_d)
b_c = b // c
b_d = b // d
b_c_d = b // c_d
b_ans = b - b_c - b_d + b_c_d
#ans2 = (b_c + b_d -b_c_d)
#print(ans2)
#print(math.floor((b-a+1)-(ans2-ans1)))
print(math.floor(b_ans-a_ans))
import sys
sys.setrecursionlimit(1000000)

n, k = map(int, input().split())
alist = list(sorted(map(int, input().split())))

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

if n == 1:
  if k == a[0]:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
else:
  r = gcd(alist[1], alist[0])
  for _a in alist[2:]:
    r = gcd(_a, r)
  if k <= alist[-1] and k % r == 0:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')


### FIXED CODE ###

n, k = map(int, input().split())
alist = list(sorted(map(int, input().split())))

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

if n == 1:
  if k == alist[0]:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
else:
  r = gcd(alist[1], alist[0])
  for _a in alist[2:]:
    r = gcd(_a, r)
  if k <= alist[-1] and k % r == 0:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
a=input()
b = input()
c = input()
d = input()
e = input()
k = input()
if e - a > k:
  print("Yay!")
else:
  print(":(")
  


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if e - a > k:
  print(":(")
else:
  print("Yay!")
times=0
while True:
    times+=1
    W=int(input())
    n=int(input())
    if W==0:
        break
    w=[0]*n
    v=[0]*n
    for i in range(n):
        v[i],w[i]=map(int,input().split(","))
    dp=[[0]*(W+1) for i in range(n+1)]
    for i in range(n):
        for j in range(W+1):
            if j<w[i]:
                dp[i+1][j]=dp[i][j]
            else:
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
    MIN=0
    for i in range(W+1):
        if dp[n][i]==dp[n][W]:
            MIN=i
            break
    print("Case %d:"%times)
    print(dp[n][W])
    print(MIN)

### FIXED CODE ###

cnt=0
while True:
    cnt+=1
    W=int(input())
    if W==0:
        break
    n=int(input())
    dp=[0]*(W+1)
    for i in range(n):
        v,w=map(int,input().split(','))
        for j in range(W,w-1,-1):
            dp[j]=max(dp[j],dp[j-w]+v)
    wgt=0
    md=max(dp)
    for i in range(W+1):
        if md==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(md)
    print(wgt)
from itertools import accumulate
from bisect import bisect_left, bisect_right

n = int(input())
xs = [int(x) for x in input().split()]

ys = [0] + list(accumulate(xs))

rs = range(2, n-2)
v = []
for i in rs:
    j = bisect_left(ys, ys[i]//2)
    minmax1 = sorted([ys[j], ys[i] - ys[j]])
    minmax2 = sorted([ys[j-1], ys[i] - ys[j-1]])
    minmax3 = sorted([ys[j+1], ys[i] - ys[j+1]])
    _, max1, min1 = min((x-n, x, n) for n, x in (minmax1, minmax2, minmax3))

    k = bisect_left(ys, (ys[-1] - ys[i])//2 + ys[i])
    minmax1 = sorted([ys[k] - ys[i], ys[-1] - ys[k]])
    minmax2 = sorted([ys[k-1] - ys[i], ys[-1] - ys[k-1]])
    minmax3 = sorted([ys[k+1] - ys[i], ys[-1] - ys[k+1]])
    _, max2, min2 = min((x-n, x, n) for n, x in (minmax1, minmax2, minmax3))

    minn, _, _, maxx = sorted([max1, min1, max2, min2])
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

### FIXED CODE ###

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))
N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

Q, K = list(map(int, input().split()))

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, -1, 0)

ans = []
for q in range(Q):
    x, y = list(map(int, input().split()))
    ans.append(cost[x] + cost[y])

for a in ans:
    print(a)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

# for n in tree.keys():
#     tree[n] = list(set(tree[n]))  # 重複を削除
# こいつが原因ではない

Q, K = list(map(int, input().split()))

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, -1, 0)

# print(cost)
ans = []
for q in range(Q):
    x, y = list(map(int, input().split()))
    ans.append(cost[x] + cost[y])

for a in ans:
    print(a)
n,a,b,c,d=map(int,input().split())
s=input()
a-=1
b-=1
c-=1
d-=1
x=[]
cnt=1
y=s[0]
g=[0,0,0,0]
for i in range(1,n):
    if s[i]==y:
        cnt+=1
    else:
        x.append([cnt,y])
        cnt=1
        y=s[i]
    if i==a:
        g[0]=len(x)
    if i==b:
        g[1]=len(x)
    if i==c:
        g[2]=len(x)
    if i==d:
        g[3]=len(x)
x.append([cnt,y])
for i in x:
    if i[0]>=2 and i[1]=='#':
        print("No")
        exit()
if a<b and c<d:
    print("Yes")
    exit()
for i in range(g[1],min(g[2]-1):
    if x[i][1]=="." and x[i][0]>=3:
        print("Yes")
        exit()
print("No")


### FIXED CODE ###

n,a,b,c,d=map(int,input().split())
s=input()
a-=1
b-=1
c-=1
d-=1
x=[]
for i in range(a,max(c,d)):
    if s[i]==s[i+1]=="#":
        print("No")
        exit()
if a<b and c<d:
    print("Yes")
    exit()
ans=0
for i in range(b-1,d+2):
    if s[i]==".":
        ans+=1
    else:
        if ans>=3:
            print("Yes")
            exit()
        ans=0
if ans>=3:
    print("Yes")
    exit()
"""
if s[b+1]=="." and s[b-1]==".":
    print("Yes")
    exit()
if s[d-1]=="." and s[d+1]==".":
    print("Yes")
    exit()
"""
print("No")
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    while True:
        plus+=1
    h,l=-1,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    if ap: h,l=ap[-1]**2,ap[0]**2-1
    if am: h,l=max(h,am[-1]**2),min(l,am[0]**2-1)
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

### FIXED CODE ###

import sys

def f1(m):
    j=0
    num=0
    for x in ap[::-1]:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,10**18
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=10**20,0
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)
A, B, C, D = map(int, input().split())

x = C / B
y = C % B
p = A / D
q = A % D

if (x < p):
  print("Yes")
elif (x > p):
  print("No")
else
  if (y == 0 and q <> 0):
    print("Yes")
  elif (y <> 0 and q == 0):
    print("No")
  else :
    print("Yes")


### FIXED CODE ###

A, B, C, D = map(int, input().split())
 
flg = True
t = False
while(flg):
  C -= B
  if (C <= 0):
    t = True
    break
  A -= D
  if (A <= 0) :
    t = False
    break

if (t):
  print("Yes")
else:
  print("No")
x=input()
y=input()
if 2*x <= y <= 4*x and y%2 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = input( ).split( )
x = int(S[0])
y = int(S[1])
if 2*x <= y <= 4*x and y%2 == 0:
  print("Yes")
else: print("No")
c11,c12,c13=map(int,input().split())
c21,c22,c23=map(int,input().split())
if c11==c23:
    print('YES')
elif c12==c22:
    print('YES')
elif c13==c31:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

a=input()
b=input()
if a[0]==b[2] and a[1]==b[1] and a[2]==b[0]:
    print('YES')
else:
    print('NO')
import math

A,B,C,D = map(int,input().split(" "))
min_C = B//C-(A-1)//C
min_D = B//D-(A-1)//D
lcm = C*D//math.gcd(C,D)
min_lcm = B//lcm-(A-1)//lcm
print(B-A-min_C-min_D+min_lcm+1)



### FIXED CODE ###

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

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

A,B,C,D = map(int,input().split(" "))
min_C = B//C-(A-1)//C
min_D = B//D-(A-1)//D
lcm = lcm(C,D)
min_lcm = B//lcm-(A-1)//lcm
print(B-A-min_C-min_D+min_lcm+1)
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N,K = map(int,input().split())
dp=[[0 for i in range(N)] for j in range(N)]

for i in range(N):
    dp[i][0] = 1
    for j in range(1,N):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

for i in range(1,K+1):
    tmp=dp[N-K+1][i]*dp[K-1][i-1]
    if tmp > MOD:
        print(tmp%MOD)
    else:
        print(tmp)


### FIXED CODE ###

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

import math

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

def combination_fuc(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#dp=[[0 for i in range(N)] for j in range(N)]
#for i in range(N):
#    dp[i][0] = 1
#    dp[i][i] = 1
#for i in range(2,N):
#    for j in range(1,i):
#        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
#for i in range(1,K+1):
#    tmp=dp[N-K+1][i]*dp[K-1][i-1]
#    if tmp > MOD:
#        print(tmp%MOD)
#    else:
#        print(tmp)

for i in range(1,K+1):
    if N-K+1 >= i:
        print((combination_fuc(N-K+1,i)*combination_fuc(K-1,i-1))%MOD)
    else:
        print(0)
import math

N, K = map(int,input().split())
devisor = 10 ** 9 + 7

def C(n,r):
    if n == 0 or n==r:
        return 1
    elif r == 1:
        return n
    else:
        return math.factorial(n)//math.factorial(r)//math.factorial(n-r)

for i in range(K):
    print(C(N-K+1, i+1)*C(K-1, i) % devisor)

### FIXED CODE ###

N, B = map(int,input().split())
R = N-B
T = 1000000007

def generating_combination(n):
	T = 1000000007
	C = C = [[0 for i in range(n+1)] for j in range(n+1)]
	C[0][0] = 1
	C[1][0] = 1
	C[1][1] = 1
	for i in range(2,n+1):
		C[i][0] = 1
		C[i][i] = 1
		for j in range(1,i):
			C[i][j] = (C[i-1][j-1] + C[i-1][j])%T
	return(C)

D = generating_combination(2000)
for i in range(1,B+1):
	print((D[B-1][i-1]*D[R+1][i])%T)
n = int(input())

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

sigma = 0
after = sum(a[0:])
for i in range(len(a)-1):
  start = a[i]
  after = after - [i]
  if after >= (10**9 + 7):
    after = after % (10**9+7)
  sigma = sigma + start * after
  if sigma >= (10**9 + 7):
    sigma = sigma % (10**9+7)

print(sigma)


### FIXED CODE ###

n = int(input())

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

sigma = 0
after = sum(a[0:])
for i in range(len(a)-1):
  start = a[i]
  after = after - a[i]
  sigma = sigma + start * after
  if sigma >= (10**9 + 7):
    sigma = sigma % (10**9+7)

print(sigma)
import math
from functools import reduce

n = int(input())
a = list(map(int, input().split()))

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

gcds = [gcd_list(a[:i]+a[i+1:]) for i in range(n)]

print(max(gcds))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

def gcd(x_,y_):
	x = max(x_, y_)
	y = min(x_, y_)
	if y==0:
		return x
	if x%y == 0:
		return y
	return gcd(y, x%y)

L = [0]*n
R = [0]*n
L[0] = a[0]
R[-1] = a[-1]

for i in range(1,n):
	L[i] = gcd(L[i-1], a[i])
	j = n-1-i
	R[j] = gcd(R[j+1], a[j])

L = [0]+L
R = R + [0]
M = [0]*n
for i in range(n):
	M[i] = gcd(L[i],R[i+1])
print(max(M))
import math

def Lcm(a,b):
    return a*b//math.gcd(a,b)
def Kosu(min,max,k):
    return max//k-(min-1)//k

min,max,a,b=map(int,input().split())
c=Lcm(a,b)
print(max+1-min-Kosu(min,max,a)-Kosu(min,max,b)+Kosu(min,max,c))



### FIXED CODE ###

import fractions

def Lcm(a,b):
    return a*b//fractions.gcd(a,b)
def Kosu(min,max,k):
    if(min%k==0):
        tyousei=1
    return max//k-(min-1)//k

min,max,a,b=map(int,input().split())
c=Lcm(a,b)
print(max+1-min-Kosu(min,max,a)-Kosu(min,max,b)+Kosu(min,max,c))