Harryxun/stf_run huggingface dataset:
from collections import deque
import math
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
    
N,K=LI()
mp = {}
for i in range(N-1):
    a,b = LI()
    if not a in mp: mp[a] = []
    if not b in mp: mp[b] = []
    mp[a].append(b)
    mp[b].append(a)

QU = deque([])
visited = set([1])

fact=[1]*100010
for i in range(1,100010):
    fact[i] = fact[i-1]*i%DVSR

def ncr(n,r):
    return fact[n]*INV(fact[r])*INV(fact[n-r])

pat = ncr(K, len(mp[1])+1)*fact[len(mp[1])+1]%DVSR
for i in mp[1]:
    visited.add(i)
    QU.append((i, len(mp[i])))

# print("initial {}".format(pat))
while QU:
    vx, cnt = QU.popleft()
    # print(vx)
    nxcnt = len(mp[vx])
    notvisited = 0
    for nx in mp[vx]:
        if not nx in visited: notvisited +=1

    for nx in mp[vx]:
        if not nx in visited:
            QU.append((nx, nxcnt))
            visited.add(nx)
    # print("keisuu {} ncr {}C{}".format(keisuu,nxcnt+1-notvisited, notvisited))
    pat = pat*fact[notvisited]*ncr(K-(nxcnt+1-notvisited), notvisited)%DVSR

print(pat)


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())


N,K=LI()
mp = {}

if N == 1:
    print(K)
    exit()

for i in range(N-1):
    a,b = LI()
    if not a in mp: mp[a] = []
    if not b in mp: mp[b] = []
    mp[a].append(b)
    mp[b].append(a)

QU = deque([])
visited = set([1])

fact=[1]*(max(N,K)+1)
for i in range(1, max(N,K)+1):
    fact[i] = fact[i-1]*i%DVSR

def ncr(n,r):
    return fact[n]*INV(fact[r])*INV(fact[n-r])%DVSR

pat = ncr(K, len(mp[1])+1)*fact[len(mp[1])+1]%DVSR
for i in mp[1]:
    visited.add(i)
    QU.append(i)

# print("initial {}".format(pat))
while QU:
    vx = QU.popleft()
    # print(vx)
    nxcnt = len(mp[vx])
    if (nxcnt+1) > K:
        print(0)
        exit()
    notvisited = 0
    for nx in mp[vx]:
        if not nx in visited:
            QU.append(nx)
            visited.add(nx)
    pat = pat*fact[nxcnt-1]*ncr(K-2, nxcnt-1)%DVSR

print(pat)
s=input()
t=input()
s1="".join(sorted(s));
t1="".join(sorted(t, reverse=true))
if s1<t1:
	print("Yes\n")
else:
	print("No\n")

### FIXED CODE ###

import math
a, b = map(int, input().split())
print(math.ceil((a+b)/2))
from collections import deque
sys.setrecursionlimit(100000)


def copyDeque(d):
    x = deque()
    for i in d:
        x.append(i)
    return x

def cndP(w):
    if len(w)>1:
        x = w.pop()
        cndP(copyDeque(w))
        w.append(x)
        s = 0
        while(len(w)>0):
            s += w.pop()
            st.add(s)
    else:
        st.add(w[0])
        
def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    d = copyDeque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

n,k = [int(x) for x in input().split()]
w = deque([int(x) for x in input().split()])

#for i in range(n):
#    w.append(int(input()))
    
st = set()
cndP(copyDeque(w))

sorted_st = sorted(st)
for i in sorted_st:
    if pIsAccptbl(w,k,i):
        print(i)
        break

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
n,i = map(int,input())
print(n-i+1)

### FIXED CODE ###

n,i = map(int,input().split())
print(n-i+1)
A, B, K = map(int, input().split())

tmp = []

for i in range(1,A):
    if((A % i == 0) and (B%i==0)):
        tmp.append(i)

tmp.reverse()
print(tmp[K-1])


### FIXED CODE ###

A, B, K = map(int, input().split())

tmp = []

for i in range(1,max(A,B)+1):
    if((A % i == 0) and (B%i==0)):
        tmp.append(i)

tmp.reverse()
#print(tmp)
print(tmp[K-1])
def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))%(XC-1)
        if tx<0:
            tx+=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)

### FIXED CODE ###

def f(n):
    if n in memo:
        return memo[n]
    c=list(str(bin(n)))[2:].count('1')
    r=n%c
    if r>0:
        memo[n]=f(r)+1
    else:
        memo[n]=1
    return memo[n]

memo={0:0}
N=int(input())
X=list(input())
XC=X.count('1')
XN=int('0b'+''.join(X),2)
for i in range(N):
    if X[i]=='1':
        if XC==1:
            print(0)
            continue
        tx=(XN%(XC-1)-pow(2,N-i-1,XC-1))
        if tx<0:
            tx+=XC-1
        tx%=XC-1
    else:
        tx=(XN%(XC+1)+pow(2,N-i-1,XC+1))%(XC+1)
    print(f(tx)+1)
n=int(input())
a=list(map(int,input().split()))
b=a.copy()
for i in a:
  b.append(i-1)
  b.append(i+1)
import collection
c=collection.Counter(b)
d=c.most_common()
print(d[0][1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=a.copy()
for i in a:
  b.append(i-1)
  b.append(i+1)
import collections
c=collections.Counter(b)
d=c.most_common()
print(d[0][1])
import sys
print(sys.stdin()[::-1])

### FIXED CODE ###

a = 1
while a:
    print(input()[::-1])
    a = 0
a = input()
b = input()
if a < b:
  swap(a,b)
if a == b:
  print(a*2)
else:
  print(a*2-1)

### FIXED CODE ###

a,b = map(int,input().split())
if a < b:
  a,b = b,a
if a == b:
  print(a*2)
else:
  print(a*2-1)
N, K = map(int,input().split())
A = list(map(int,input().split()))
n = A.index(min(A))
n2 = N-1-n
a,b = divmod(n,K-1)
c,d = divmod(n2,K-1)
if b == d == 0:
    print(a+c)
elif b+d < K
    print(a+c+1)
else:
    print(a+c+2)

### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
n = A.index(min(A))
n2 = N-1-n
a,b = divmod(n,K-1)
c,d = divmod(n2,K-1)
if b == d == 0:
    print(a+c)
elif b+d < K:
    print(a+c+1)
else:
    print(a+c+2)
num = input().split()
a, b, c, d = int(num[0]), nt(num[1]), nt(num[2]), nt(num[3])

if abs(a-b)<=d and abs(b-c)<=d:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

num = input().split()
a, b, c, d = int(num[0]), int(num[1]), int(num[2]), int(num[3])

if abs(a-b)<=d and abs(b-c)<=d or abs(a-c) <= d:
  print("Yes")
else:
  print("No")
s = input()
t = input()
count = 0
for i in range(len(a)):
  if not s[i] == t[i]:
    count += 1
print(count)

### FIXED CODE ###

m=input()
n=input()
count=0
for i in range(len(m)):
   if m[i]!=n[i]:
      count+=1
print(count)
import numpy as np


def calculate(h, w, arr):
    L = np.zeros([h, w])
    U = np.zeros([h, w])
    D = np.zeros([h, w])
    R = np.zeros([h, w])

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)

### FIXED CODE ###

def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)
a=input()
d=input()

if a[2]==d[0] and a[1]==d[1] and a[0]==d[2]:
    print("YES")
else:
    NO

### FIXED CODE ###


a=input()
d=input()

if a[2]==d[0] and a[1]==d[1] and a[0]==d[2]:
    print("YES")
else:
    print("NO")
if(S == ABC){
	print("ARC")
}
else if(S == ARC){
	print("ABC");
}

### FIXED CODE ###

S = input()

if(S == "ABC"):
	print("ARC")
elif(S == "ARC"):
	print("ABC")
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    c = collections.Counter(A)
    C = max(c.values())
    if C > 1 :
        print('NO')
    else:
        print('YES')
resolve()

### FIXED CODE ###

import  collections
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    c = collections.Counter(A)
    C = max(c.values())
    if C > 1 :
        print('NO')
    else:
        print('YES')
resolve()
n=int(input())
w=list(map(int,input().split()))
su =sum(w)

ans = 1234567890
cnt =0
for i in range(n):
    cnt += w[i]
    ans = min(ans,abs(su-cnt)
print(ans)

### FIXED CODE ###

n=int(input())
w=list(map(int,input().split()))
wa=[0]*(n+1)
for i in range(n):
	wa[i+1] = wa[i]+w[i]

ans = 1234567890
for i in range(1,n+1):
	ans = min(ans,abs(wa[n]-2*wa[i]))
print(ans)
N = int(input())
A = list(map(int, input().split()))

def up(i,pre):
    if i == len(A) - 1:
        return abs(A[pre] - A[i])
    res1 = res2 = float("inf")
    if i + 2 <=len(A) -1: 
        res1 = up(i + 1,i)
        res2 = up(i + 2,i)
        return min(abs(A[pre] - A[i]) + res1, abs(A[pre] - A[i]) + res2)
    elif i + 1 <=len(A) -1: 
        res1 = up(i + 1,i)
        return abs(A[pre] - A[i]) + res1
  
if N>2:
    print(min(up(1,0),up(2,0)))
else:
    print(up(1,0))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(len(A))]
dp[0] = 0 
for i in range(1,N):
    if i - 2>=0:
        dp[i] = min(dp[i-1] + abs(A[i] - A[i-1]),dp[i-2] + abs(A[i] - A[i-2]))
    else:
        dp[i] =dp[i-1] + abs(A[i] - A[i-1])

print(dp[len(A)-1])
N,A,B,C,D =list(map(int,input().split()))
s = input()
flag = 0
if C<D:
    if s[B-1:D].count('##') == 0 and s[A-1:C].count('##') == 0:
        print('Yes')
    else:
        print('No')
else:
    if s[B-1:C].count('...')>=1 and s[A:C].count('##')==0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

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

if sum(a) == 0:
    print('Yes')
    exit()

if N%3 != 0:
    print('No')
    exit()    

ac = collections.Counter(a)

if len(ac) == 2 and ac[0] ==N/3:
    print('Yes')
    exit()


if len(ac) != 3 :
    print('No')
    exit()
else:
    lk1,lk2,lk3 = ac.keys()
    lv1,lv2,lv3 = ac.values()
if lv1 == lv2 ==lv3:
    if lk1^lk2 == lk3:
        print('Yes')
    else:
        print('No')
else:
    print('No')
    exit()
import sys

def main(lines):
  line=lines[0].split()
  n = int(line[0])
  x = int(line[1])
  t = int(line[2])
  ans = math.ceil(n/x)*t
  print(ans)

if __name__ == '__main__':
    lines = []
    for l in sys.stdin
        lines.append(l.rstrip('\r\n'))
    main(lines)


### FIXED CODE ###

import sys
import math

def main(lines):
    line=lines.split()
    n = int(line[0])
    x = int(line[1])
    t = int(line[2])
    ans = math.ceil(n/x)*t
    print(ans)

if __name__ == '__main__':
    lines=input()
    main(lines)
import numpy as np

N = int(input())
X = str(input())

def func(x):
    if a[x] != -1:
        return a[x]
    else:
        counter = 0
        x_tmp = x
        while x > 0:
            if x % 2 == 1:
                counter += 1
            x = x >> 1
        a[x_tmp] = func(x_tmp % counter) + 1
        return func(x_tmp % counter) + 1
if N <= 10:
    print(func(int(X, 2)))
    
else:
    a = [-1] * (2 * 10 ** 5)
    a[0] = 0
    num_one = X.count("1")
    zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
    bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
    for i in range(1,N+1):
        tmp_bool = bool_arr.copy()
        start = 0
        if tmp_bool[N-i] == False:
            tmp_bool[N-i] = True
            start = sum(zero_ver[tmp_bool]) % (num_one + 1)
        else:
            tmp_bool[N-i] = False
            start = sum(one_ver[tmp_bool]) %  (num_one - 1)
        print(func(start)+1)


### FIXED CODE ###

import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
zero_ver_sum = sum(zero_ver[bool_arr])

one_ver = -1
one_ver_sum = 0
flag = False
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
    one_ver_sum = sum(one_ver[bool_arr])
else:
    flag = True
for i in range(1,N+1):
    start = 0
    if bool_arr[N-i] == False:
        start = (zero_ver_sum + pow(2, N - i, num_one + 1)) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if flag:
            print(0)
        else:
            start = (one_ver_sum - pow(2, N - i, num_one - 1))  %  (num_one - 1)
            print(dfs(start)+1)
normal_ant = [i for i, direction in ants if direction==1]
counter_ant = [i for i, direction in ants if direction==2]
cnt = (t // l) * len(normal_ant) + sum([1 for i in normal_ant if i + t%l >= l])
counter_cnt = (t // l) * len(counter_ant) + sum([1 for i in counter_ant if i - t%l < 0])
final_pos = sorted([(i-t)%l for i in counter_ant] + [(i+t)%l for i in normal_ant])
print(*final_pos[(cnt-counter_cnt)%n:] + final_pos[:(cnt-counter_cnt)%n], sep='\n')

### FIXED CODE ###

n, l, t = list(map(int, input().split()))
ants = []
for i in range(n):
    ants.append(list(map(int, input().split())))
normal_ant = [i for i, direction in ants if direction==1]
counter_ant = [i for i, direction in ants if direction==2]
cnt = (t // l) * len(normal_ant) + sum([1 for i in normal_ant if i + t%l >= l])
counter_cnt = (t // l) * len(counter_ant) + sum([1 for i in counter_ant if i - t%l < 0])
final_pos = sorted([(i-t)%l for i in counter_ant] + [(i+t)%l for i in normal_ant])
print(*final_pos[(cnt-counter_cnt)%n:] + final_pos[:(cnt-counter_cnt)%n], sep='\n')
# coding: utf-8
# Your code here!
n,m=map(int,input().split(" "))
mae=0
usiro=1000000000
for i in range(m):
    s,t=map(int,input().split(" "))
    if(mae<=s):
        mae=s
    if(usiro>=t):
        usiro=t
#print(mae,usiro)
ans=usiro-mae+1
if(ans<0):
    ans=0
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
n,ans=map(int,input().split(" "))
if(n<=12):
    ans/=2
if(n<6):
    ans=0
print(round(ans))
first=input()
P=first[0]
S=first[1]
count=0
for t in range(len(P)-1):
  if P eq 0:count=count+1
    else count=count
print(count)

### FIXED CODE ###

a=[input() for i in range(2)]
P=a[0]
S=a[1]
count=0
for t in range(len(P)):
  if P[t] != S[t]:
    count=count+1
print(count)
import numpy as np

N, K = list(map(int, input().split()))
R, S, P = list(map(int, input().split()))
T = str(input())

# マシンの出し手を整列させて、K分割してペア作成
# TODO: zero padding
num_split = (N + K - 1) // K
if N % K != 0:
    machine_arr = np.array(list(T) + ['0'] * (N % K)).reshape((-1, num_split), order='F')
else:    
    machine_arr = np.array(list(T)).reshape((-1, num_split), order='F')

ans = 0
for idx in range(machine_arr.shape[0]):
    orig_str = ''.join(machine_arr[idx].tolist())
    rep_str = orig_str.replace('rr', 'r').replace('ss', 's').replace('pp', 'p')
    point = rep_str.count('r') * P + rep_str.count('s') * R + rep_str.count('p') * S
    ans += point

print(ans)

### FIXED CODE ###

import numpy as np

N, K = list(map(int, input().split()))
R, S, P = list(map(int, input().split()))
T = str(input())

ans = 0
for k in range(K):
    orig_str = T[k::K]
    rep_str = orig_str.replace('rr', 'r').replace('ss', 's').replace('pp', 'p')
    point = rep_str.count('r') * P + rep_str.count('s') * R + rep_str.count('p') * S
    ans += point

print(ans)
order = list(map(len, input().split("T")))
x, y = map(int, input().split())
ans = "No"
longi = [order[i] for i in range(len(order)) if i % 2 == 0]
lati = [order[i] for i in range(len(order)) if i % 2 == 1]
def f(x, y, A, B, D):
  for p in A:
      if x > 0:
        x -= p
      else:
        x += p
  if x == 0:
    for q in B:
      if y > 0:
        y -= q
      else:
        y += q
    if y == 0:
      D = "Yes"
  return D
  
print(longi, lati)
if sum(longi) >= abs(x):
  if sum(lati) >= abs(y):
    longi.sort(reverse=True)
    lati.sort(reverse=True)
    ans = f(x, y, longi, lati, ans)
    if ans == "No":
      x += x // abs(x) * abs(longi[-1])
      y += y // abs(y) * abs(lati[-1])
      ans = f(x, y, longi[:-2], lati[:-2], ans)
    
    
print(ans)

### FIXED CODE ###

order = list(map(len, input().split("T")))
x, y = map(int, input().split())
ans = "No"
lon = [order[i] for i in range(len(order)) if i % 2 == 0]
lat = [order[i] for i in range(len(order)) if i % 2 == 1]
x -= lon[0]
lon = lon[1:]
def f(x, A):
  A.append(abs(x))
  A.sort(reverse=True)
  k = A[0]
  for p in A[1:]:
      if k > 0:
        k -= p
      else:
        k += p
  if k == 0:
    return True
  else:
    return False
  
#print(lon, lat)
if f(x, lon) == f(y, lat) == True:
  ans = "Yes"
  
print(ans)
import math

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


A,B,C,D = map(int,input().split())
c = B//C - (A-1)//C
d = B//D - (A-1)//D
E = lcm(C,D)
e = B//E - (A-1)//E
answer = B-A+1-(c+d-e)
print(answer)
            


### FIXED CODE ###

import fractions
A,B,C,D = map(int,input().split())
c = B//C - (A-1)//C
d = B//D - (A-1)//D
E = (C*D)//fractions.gcd(C,D)
e = B//E - (A-1)//E
answer = B-A+1-(c+d-e)
print(answer)
x = list(map(int,input().split()))
n = 1
if x>0:
    print("case",n,":",x[n])
    n = n+1



### FIXED CODE ###

n = 1
x = int(input())
while x != 0 :
    print("Case {}: {}".format(n,x))
    n = n+1
    x = int(input())
from fractions import Fraction


N = int(input())

AB = [tuple(map(int, input().split())) for _ in range(N)]

MOD = 10**9 + 7

from collections import defaultdict

d = defaultdict(int)
ans = 1
cnt_00 = 0
for a,b in AB:
    if a == 0 and b == 0:
        cnt_00 += 1 
    elif a == b:
        d[1] += 1
    else:
        d[Fraction(a,b)] += 1




ans = 1
ks = list(d.keys())
for k in ks:
    if d[k] == 0:
        continue
    
    elif k == 1 or k == -1:

        num = (((pow(2,d[1], MOD) + pow(2, d[-1], MOD)) % MOD) -1) % MOD
        ans *= num
        ans %= MOD
        d[1] = 0
        d[-1] = 0

    else:

        num = (((pow(2, d[k], MOD) + pow(2,d[Fraction(-1, k)], MOD)) % MOD)-1) % MOD
        ans *= num
        ans %= MOD
        d[k] = 0
        d[Fraction(-1, k)] = 0
        



ans -=1
ans %= MOD
print(ans) 

### FIXED CODE ###

from math import gcd
from collections import defaultdict

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

d = defaultdict(int)
cnt_00 = 0
cnt_0b = 0
cnt_a0 = 0
for a,b in AB:
    if a == b == 0:
        cnt_00 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_0b += 1
    else:
        num_gcd = gcd(a,b)
        grad = 1 if a * b > 0 else -1
        a //= num_gcd
        b //= num_gcd
        d[(grad, abs(a), abs(b))] += 1



ans = 1
for k in d.keys():
    if d[k] == 0:
        continue
    
    grad, a, b = k[0], k[1], k[2]
    if (-grad, b, a) in d:
        
        # 傾き a/bのものを一つ以上選ぶ場合（-b/aは選ばない） + -b/aから一つ以上選ぶ場合（a/bは選ばない） + どちらからも選ばない場合
        ans *= (pow(2, d[(grad, a, b)], MOD)-1) + (pow(2, d[(-grad, b, a)], MOD)-1) + 1
        ans %= MOD
        d[(grad, a, b)] = 0
        d[(-grad, b, a)] = 0
    else:
        # a/bから0個以上選ぶ場合
        ans *= pow(2, d[(grad, a, b)], MOD)
        ans %= MOD
        d[(grad, a, b)] = 0

# a,bの一方のみ0の場合 + どちらからも選ばない場合
ans *= (pow(2, cnt_a0, MOD)-1) + (pow(2, cnt_0b, MOD)-1) + 1
ans %= MOD

# 0,0のみを１つだけ入れる場合
ans += cnt_00
# なにも選ばない場合を除く
ans -= 1

ans %= MOD

print(ans)
N=int(input())
a = list(map(int, input().split()))

dp=[[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    dp[i][i]=a[i-1]
for j in range(1,N+1):
    for i in reversed(range(1,N+1)):
        if i>j:
            continue
        if i==j:
            dp[i][j]=a[i-1]
        if i<j:
            dp[i][j]=max(a[i-1]-dp[i+1][j],a[j-1]-dp[i][j-1])
print(dp[1][N]

### FIXED CODE ###

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

dp=[[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    dp[i][i]=a[i-1]
for j in range(1,N+1):
    for i in reversed(range(1,N+1)):
        if i>j:
            continue
        if i==j:
            dp[i][j]=a[i-1]
        if i<j:
            dp[i][j]=max(a[i-1]-dp[i+1][j],a[j-1]-dp[i][j-1])
print(dp[1][N])