from math import ceil, floor

def between(a, b, c, d):
    q = 1
    while 1:
        u, v = floor(a * q / b) + 1, ceil(c * q / d) - 1
        if u <= v:
            print(f"{a}/{b} < {v}/{q} < {c}/{d}")
            return (v, q)
        q += 1

def recurs(a,b,c,d,p0,q0,p1,q1):
    p, q = p0 + p1, q0 + q1
    if a * q < p * b:
        if p * d < c * q:
            return (p, q)
        else:
            return recurs(a,b,c,d,p0,q0,p,q)
    else:
        return recurs(a,b,c,d,p,q,p1,q1)
        
def _between(a, b, c, d):
    p0, q0 = 0, 1  # left bound
    p1, q1 = 1, 0  # right bound
    return recurs(a,b,c,d,p0,q0,p1,q1)
    while True:
        p, q = p0 + p1, q0 + q1
        if a * q < p * b:
            if p * d < c * q:
                return (p, q)
            else: 
                p1, q1 = p, q
        else: 
            p0, q0 = p, q 
    
r = between(97,103,101,103)
print(r)
r = _between(97,103,101,103)
print(r)