Harryxun/stf_run huggingface dataset:
def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

N, M = map(int, input().split())
E = [[] for i in range(N)]
edges = []
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    edges.append((a-1, b-1))

dag = False
for v in range(N):
    s, prev = BFS(v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

### FIXED CODE ###

def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

N, M = map(int, input().split())
V = list(range(N))
E = [[] for _ in range(N)]
edges = []
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    edges.append((a-1, b-1))

dag = False
for v in range(N):
    s, prev = cycle_detection(V, E, v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')
n, q = map(int,input().split())
top_list = [list(map(int,input().split())) for i in range(n - 1)]
ope_list = [list(map(int,input().split())) for i in range(q)]
ans = [0] * n

"""
for i in ope_list:
    ans[i[0] - 1] += i[1]

for j in range(n):
    for k in top_list:
        if j + 1 == k[1]:
            ans[j] += ans[k[0] - 1]
"""

print(*ans)

### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
    print(s)
else:
    print('red')
n=int(input())
c=list(map(int,input().split()))
s=0
for i in range(n):
    for j in range(i):
        d=0
        if c[i]>=c[j]
            d+=0
        else: 
            d+=1
    if d==0:
        s+=1
    else:
        s+=0
print(s)

### FIXED CODE ###

n=int(input())
c=list(map(int,input().split()))
s=0
for i in range(n):
    d=0
    for j in range(i):
        if c[i]>=c[j]:
            d+=0
        else: 
            d+=1
    if d==0:
        s+=1
    else:
        s+=0
print(s)
def to_bin(n):
  s = ''
  while n > 0:
    s += str(n%2)
    n //= 2
  return s[::-1]

def xor(s1, s2):
  s1 = '0'*(len(s2)-len(s1)) + s1
  result = ''
  for i in range(len(s1)):
    if s1[i] == s2[i]:
      result += '0'
    else:
      result += '1'
  return result

def to_den(s):
  s = s[::-1]
  total = 0
  for i in range(0, len(s)):
    total += 2**i*int(s[i])
  return total

def main():
  A, B = map(int, input().split())
  if A == B:
    print(A)
    exit(1)

  cur = xor(to_bin(A), to_bin(A+1))

  for i in range(A+2, B+1):
    s = to_bin(i)
    cur = xor(cur, s)

  print(to_den(cur))

main()


### FIXED CODE ###

H, W = map(int, input().split())
h,w = map(int, input().split())

print(abs(H-h)*abs(W-w))
n,m=map(int,input().split())
num=[0]*n
for i in range(n):
  a,b=map(int,input().split())
  a-=1;b-=1
  num[a]+=1;num[b]+=1
flag=0
for i in num:
  if i%2==1:
    flag=1
    break
if bool(flag):print("NO")
else:print("YES")

### FIXED CODE ###

n,m=map(int,input().split())
num=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  a-=1;b-=1
  num[a]+=1;num[b]+=1
flag=0
for i in num:
  if i%2==1:
    flag=1
    break
if bool(flag):print("NO")
else:print("YES")
x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
c=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))
  c.append(int(x[0])/int(x[1]))
s=0  
while H>0:
  maxim=0
  for k in range(n):
    m=H//a[k]
    d=a[k]*(H//a[k]+1)
    if (d+1)*b[k]>maxim:
      maxim=(d+1)*b[k]
  s+=maxim
print(s)  

### FIXED CODE ###

x=input().split()
H=int(x[0])
A=int(x[1])
if H%A==0:
  print(H//A)
else:
  print(H//A+1)
def main():
    a,b,n = map(int,input().split())
    if b>n:
        print(int(a*(n/b-n//b)))
    else:
        print(int(a*((b-1)/b))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    a,b,n = map(int,input().split())
    if b>n:
        print(int(a*(n/b-n//b)))
    else:
        print(int(a*((b-1)/b)))


if __name__ == "__main__":
    main()
def main():
    N = input()
    D_list = list(map(int, input().split()))

    maxD = max(D_list)
    count_nowD = D_list.count(0)
    lenD = len(count_nowD)

    if D_list.count(0) == 0:
        ans = 0
    elif count_nowD == lenD:
        ans = 1
    else:
        counter = 1
        ans = 1

        while counter <= maxD:
            count_beforeD = count_nowD
            count_nowD = D_list.count(counter)

            if(count_nowD == 0):
                ans = 0
                break

            ans = (ans * (count_beforeD ** count_nowD) % 998244353) % 998244353
            counter = counter + 1

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

    if D_list[0] != 0:
        ans = 0
    
    else:
        maxD = max(D_list)
        count_ele_Dlist = [0] * (maxD + 1)

        for i in D_list:
            count_ele_Dlist[i] = count_ele_Dlist[i] + 1

        if count_ele_Dlist[0] == 1:
            ans = 1
            for i in range(1, maxD + 1):
                ans = (ans * count_ele_Dlist[i - 1] ** count_ele_Dlist[i]) % 998244353
        else:
            ans = 0
        
    print(ans)

if __name__ == "__main__":
    main()
N = int(input())
B = list(map(int, input().split()))
A = []

for i in range(N-1):
  if i == 0:
    A.append(B[i])
  elif B[i - 1] <= B[i]:
    A.append(B[i - 1])
  else:
    A.append(B[i])
if B[N-3] <= B[N-2]:
  A.append(B[N-2])
else:
  A.append(B[N-1])
print(sum(A))

### FIXED CODE ###

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

for i in range(N-1):
  if i == 0:
    A.append(B[i])
  elif B[i - 1] <= B[i]:
    A.append(B[i - 1])
  else:
    A.append(B[i])
if A[-1] <= B[N-2]:
  A.append(B[N-2])
else:
  A.append(A[-1])
print(sum(A))
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
interval=[[] for i in range(0,N)]
for i in range(0,M):
    l,r,a=map(int,input().split())
    interval[l-1].append((r-1,a))

#A1 ... AnのBIT(1-indexed)
n=N+1
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

Max=[0 for i in range(0,N+2)]
for i in range(N,0,-1):
    for j in range(0,len(interval[i])):
        r,a=interval[i][j]
        BIT_update(i,a)
        BIT_update(r+1,-a)
    Max[i]=max(BIT_query(j) for j in range(1,N+1))
    if i>1:
        BIT_update(i-1,Max[i])
        BIT_update(i,-Max[i])

print(Max[1])


### FIXED CODE ###

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
interval=[[] for i in range(0,N)]
for i in range(0,M):
    l,r,a=map(int,input().split())
    interval[l-1].append((r-1,a))

# N: 処理する区間の長さ
INF = 10**30-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

Max=[0 for i in range(0,N)]
for i in range(N-1,-1,-1):
    for j in range(0,len(interval[i])):
        r,a=interval[i][j]
        update(i,r+1,-a)
    Max[i]=max(-query(0,N),0)
    if i>0:
        update(i-1,i,-Max[i])

print(Max[0])
N,M=[int(i) for i in input().split(" ")]
number=[-1 for i in range(N)]
for s,c in [[int(i) for i in input().split(" ")] for n in range(M)]:
    if(number[s-1]==-1):
        number[s-1]=c
    elif(number[s-1]!=c):
        print(-1)
        break
else:
    for i in range(len(number)):
        if number[i]==-1:
            if i==0:
                number[i]=1
            else:
                number[i]=0
    n=number[0]*100+number[1]*10+number[2]
    if(len(str(n))!=N):
        print("-1")
    else:
        print(n)


### FIXED CODE ###

N,M=[int(i) for i in input().split(" ")]
number=[-1 for i in range(N)]
for i in range(M):
    s,c=[int(i) for i in input().split(" ")]
    if(number[s-1]==-1):
        number[s-1]=c
    elif(number[s-1]!=c):
        print(-1)
        break
else:
    n=0
    for i in range(N):
        if number[i]==-1:
            if i==0 and N>=2:
                number[i]=1
            else:
                number[i]=0
        n=n*10 + number[i]
    if(len(str(n))==N):
        print(n)
    else:
        print("-1")
#!/usr/bin/env python3
def solve(k, a, b):
    if a - b <= 0 and a < k:
        return -1
    return 1 + (k - a + (a - b) - 1) // (a - b) * 2
k, a, b = map(int, input().split())
print(solve(k, a, b))


### FIXED CODE ###

#!/usr/bin/env python3
def solve(k, a, b):
    if a - b <= 0:
        if k <= a:
            return 1
        else:
            return -1
    return 1 + (k - a + (a - b) - 1) // (a - b) * 2
k, a, b = map(int, input().split())
print(solve(k, a, b))
import io
sys.stdin = io.StringIO("""3 2
#.#
.#.
#.#
#.
.#
""")
import sys
def main():
    t = sys.stdin.readline()
    t1 = t.rstrip()
    t2 = t1.split(' ')
    stra = [] 
    for i in range(int(t2[0])):
        y = sys.stdin.readline()
        t = y.rstrip()
        stra += [t]
    strb = [] 
    for i in range(int(t2[1])):
        y = sys.stdin.readline()
        t = y.rstrip()
        strb += [t]

    suma = 0
    for x in strb:
        for y in stra:
            print(x,y)
            if x in y:
                suma +=1 
    if int(t2[0])*int(t2[1])==suma:
        print("yes")
    
    print(stra,strb)
main()

### FIXED CODE ###

import sys
def main():
    t = sys.stdin.readline()
    t1 = t.rstrip()
    t2 = t1.split(' ')
    stra = [] 
    for i in range(int(t2[0])):
        y = sys.stdin.readline()
        t = y.rstrip()
        stra += [t]
    strb = [] 
    for i in range(int(t2[1])):
        y = sys.stdin.readline()
        t = y.rstrip()
        strb += [t]
 
    suma = 0
    for x in strb:
        for y in stra:
            if x in y:
                suma +=1 
    if int(t2[0])*int(t2[1])==suma:
        print("Yes")
    else:
        print("No")
main()
X = 1
N = input()
K = input()
for i in range(N):
	if(X*2 < X+K):
		X *= 2
	else X += K
print(X)

### FIXED CODE ###

X = 1
N = input()
K = input()
for i in range(N):
	if(X*2 < X+K):
	    X *= 2
	else:
            X += K
print(X)
N = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp[0][0] = 1-p[0]
# dp[0][1] = p[0]

for i in range(N):
    for j in range(i+1):
        # print(f"i {i}, j {j}")
        # print(f"p[i] {p[i]}, dp[i][j] {dp[i][j]}")

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        # print("dp", dp)

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v
print(ans)N = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp[0][0] = 1-p[0]
# dp[0][1] = p[0]

for i in range(N):
    for j in range(i+1):
        # print(f"i {i}, j {j}")
        # print(f"p[i] {p[i]}, dp[i][j] {dp[i][j]}")

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        # print("dp", dp)

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v
print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp[0][0] = 1-p[0]
# dp[0][1] = p[0]

for i in range(N):
    for j in range(i+1):
        # print(f"i {i}, j {j}")
        # print(f"p[i] {p[i]}, dp[i][j] {dp[i][j]}")

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        # print("dp", dp)

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v

print(ans)
print(x**3)

### FIXED CODE ###

x = int(input())
print(x ** 3)
# coding: utf-8

# In[1]:


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


# In[5]:


def p(n):
    return 2 ** (n+1) - 1
def b(n):
    return 2 ** (n+1) - 2
def l(n):
    return 2 ** (n+2) - 3


# In[30]:


def func(i,x):
    if x > l(i):
        print("error")
    else:
        if i == 0:
            if x == 1:
                return 1
            else:
                return 0
        else:
            if x <= 2**(i+1) - 2:
                return func(i-1, x-1)
            else:
                return p(i-1) + 1 + func(i-1, x-(2**(i+1)-2)-1,)


# In[34]:


print(func(n,x))



### FIXED CODE ###


# coding: utf-8

# In[103]:


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


# In[104]:


def p(n):
    return 2 ** (n+1) - 1
def b(n):
    return 2 ** (n+1) - 2
def l(n):
    return 2 ** (n+2) - 3


# In[109]:


def func(i, x):
    if x == 0:
        return 0
    elif x <= l(i-1) + 1:
        return func(i-1, x-1)
    elif x == l(i-1) + 2:
        return p(i-1) + 1
    elif x <= 2 * l(i-1) + 2:
        return p(i-1) + 1 + func(i-1, x - l(i-1) - 2)
    else:
        return 2 * p(i-1) + 1


# In[110]:


print(func(n,x))
n = int(input())
h = [int(i) for i in input().split()]
if n == 1:
    print('Yes')
else:
    cnt = 0
    for i in range(1,n,-1):
        if h[i] - h[i-1] <= -2:
            cnt = 1
            break
        elif h[i] - h[i-1] == -1:
            h[i-1]  -= 1

if cnt == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]

if n == 1:
    print('Yes')
else:
    cnt = 0
    for i in range(1,n):
        if h[n-i] - h[n-i-1] <= -2:
            cnt = 1
            break
        elif h[n-i] - h[n-i-1] == -1:
            h[n-i-1]  -= 1

    if cnt == 0:
        print('Yes')
    else:
        print('No')
n,x = int(input())
ans = n
mi = 10**4
for i in range(n):
  m = int(input())
  x -= m
  mi = min(m,mi)
print(ans + (x//mi)*mi)
  

### FIXED CODE ###

n,x = map(int,input().split())
ans = n
mi = 10**4
for i in range(n):
  m = int(input())
  x -= m
  mi = min(m,mi)
ans += (x//mi)
print(ans)
S = input()
Q = int(input())
Q_list = list()
for i in range(Q):
    Q_list.append(input().split())
  
from collections import deque
def operate(i):
    global count, str_list
    if Q_list[i][0] == '1':
        count += 1
    else:
        if count % 2 == 0:
            if Q_list[i][1] == '1':
                str_list.appendleft(Q_list[i][2])
            else:
                str_list.append(Q_list[i][2])
        else:
            if Q_list[i][1] == '1':
                str_list.append(Q_list[i][2])
            else:
                str_list.appendleft(Q_list[i][2])

check = 0
for i in range(Q):
    if Q_list[i][0] == '1':
        check += 1

if check % 2 == 1:
    S_list = list(reversed(S_list))

str_list = deque()
str_list.append(S)
count = 0
for i in range(Q):
    operate(i)
print(''.join(str_list))

### FIXED CODE ###

S = input()
Q = int(input())
Q_list = list()
for i in range(Q):
    Q_list.append(input().split())

from collections import deque
def operate(i):
    global count, str_list
    if Q_list[i][0] == '1':
        count += 1
    else:
        if count % 2 == 0:
            if Q_list[i][1] == '1':
                str_list.appendleft(Q_list[i][2])
            else:
                str_list.append(Q_list[i][2])
        else:
            if Q_list[i][1] == '1':
                str_list.append(Q_list[i][2])
            else:
                str_list.appendleft(Q_list[i][2])

check = 0
for i in range(Q):
    if Q_list[i][0] == '1':
        check += 1

S_list = [i for i in S]
if check % 2 == 1:
    S_list = list(reversed(S_list))

S_n = ''.join(S_list)

str_list = deque()
str_list.append(S_n)
count = check%2
for i in range(Q):
    operate(i)
print(''.join(str_list))
r =int(input())
return int(r**2)

### FIXED CODE ###

r = int(input())
print(int(r**2))
N = int(input())
primeNum = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999]

pow = 1
time = 0
while True:
    for p in primeNum:
        z = p**pow
        if p <= N:
            if N % z == 0:
                N = int(N / (z))
                time+=1
        else:
            break
    pow+=1
    if pow >= N:
        break

print(time)


### FIXED CODE ###

A,B = input().split()
print(int(A)*int(B))
# -*- coding: utf-8 -*-
import math
def main():
    A,B,C,D = map(int,input().split())
    E = math.lcm(C*D)
    Cc = B / C
    Dd = B / D
    Ee = B / E
    flo = A-1
    Cf = flo / C
    Df = flo / D
    Ef = flo / E
    All = B-(math.floor(Cc)+math.floor(Dd)-math.floor(Ee))
    Sub = flo-(math.floor(Cf)+math.floor(Df)-math.floor(Ef))
    print(All - Sub)
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
def lcm(x, y):
    return (x*y) // fractions.gcd(x, y)
def main():
    A,B,C,D = map(int,input().split())
    E = lcm(C,D)
    Cc = B // C
    Dd = B // D
    Ee = B // E
    flo = A-1
    Cf = flo // C
    Df = flo // D
    Ef = flo // E
    All = B-(Cc+Dd-Ee)
    Sub = flo-(Cf+Df-Ef)
    print(int(All - Sub))
if __name__ == '__main__':
    main()
n,k = map(float, input().split())
p = [float(e) for e in input().split()]

e = [(q+1)/2 for q in p]

max = 0
for i in range(n-k+1):
  s = e[i]+e[i+1]+e[i+2]
  if max < s:
    max = s
    
print(max)

### FIXED CODE ###

n,k = map(int, input().split())
p = [int(e) for e in input().split()]
s = sum(p[0:k])
max = s
for i in range(n-k):
  s = s - p[i] + p[i+k]
  if max < s:
    max = s
    
ex = (max+k)/2.0
print(ex)
H,W=map(int,input().split())
S=[input() for i in [0]*H]
m=[[-1]*W for _ in [0]*H]
def dfs(i,j,k):
    m[i][j]=k
    if i+1<H and m[i+1][j]==-1 and S[i][j]!=S[i+1][j]:
        dfs(i+1,j,k)
    if i-1>0 and m[i-1][j]==-1 and S[i][j]!=S[i-1][j]:
        dfs(i-1,j,k)
    if j+1<W and m[i][j+1]==-1 and S[i][j]!=S[i][j+1]:
        dfs(i,j+1,k)
    if j-1>0 and m[i][j-1]==-1 and S[i][j]!=S[i][j-1]:
        dfs(i,j-1,k)
k=0
for i in range(H):
    for j in range(W):
        if m[i][j]==-1:
            dfs(i,j,k)
            k += 1
d={}
di=set()
for i in range(H):
    for j in range(W):
        mij=m[i][j]
        sij=0 if S[i][j]=='.' else 1
        if (mij,sij) in d.keys():d[(mij,sij)]+=1
        else:d[(mij,sij)]=1
        di|={mij}
r=0
for i in di:
    if (i,0) in d.keys() and (i,1) in d.keys():
        r += d[(i,0)]*d[(i,1)]
#print(m)
#print(d,di)
print(r)

### FIXED CODE ###

import collections
H,W=map(int,input().split())
S=[input() for i in [0]*H]
M=[[-1]*W for _ in [0]*H]
k=0
for y in range(H):
    for x in range(W):
        if M[y][x]!=-1:continue #visited
        M[y][x]=k
        Q=collections.deque()
        Q.append((y,x))
        while len(Q)>0:
            i,j=Q.popleft()
            s=S[i][j]
            if i+1<H and M[i+1][j]==-1 and s!=S[i+1][j]:
                M[i+1][j]=k
                Q.append((i+1,j))
            if i-1>=0 and M[i-1][j]==-1 and s!=S[i-1][j]:
                M[i-1][j]=k
                Q.append((i-1,j))
            if j+1<W and M[i][j+1]==-1 and s!=S[i][j+1]:
                M[i][j+1]=k
                Q.append((i,j+1))
            if j-1>=0 and M[i][j-1]==-1 and s!=S[i][j-1]:
                M[i][j-1]=k
                Q.append((i,j-1))
            #print(k,M,Q)
        k+=1
ds={}
dd={}
for i in range(H):
    for j in range(W):
        m=M[i][j]
        if S[i][j]=='#':ds[m]=ds.get(m,0)+1
        else:dd[m]=dd.get(m,0)+1
r=0
for i in range(k):
    r += ds.get(i,0)*dd.get(i,0)
print(r)
N, Q = map(int, input().split())
S = input()
S_lr = []
for i in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    S_lr.append(s)

import re

for s in S_lr:
    count = len(re.findall('AC', s))
    print(count)



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
def main():
    n = int(input())

    ans = []

    def fanc(i, s):
        if len(s) == n:
            ans.append(s)
        else:
            for x in range(i + 2):
                # print(x,i,s)
                fanc(max([x, i]), s + chr(97 + x))
                # fanc(x + 1, s + chr(97 + x))

    fanc(0, "a")
    ans.sort()
    for i in ans:
        print(i)

    # print(len(ans))
main()


### FIXED CODE ###

from math import sqrt
from decimal import *
a, b, c = map(int, input().split())

getcontext().prec = 50

sa = Decimal(a).sqrt()
sb = Decimal(b).sqrt()
sc = Decimal(c).sqrt()


if sa + sb < sc:
    print("Yes")
else:
    print("No")