import math

def isqrt(n):
    if n < 0:
        return None
    return math.isqrt(n)

def reconstruct_xy(d, z, k):
    """Given d = x+y, z, and k, try to recover integer x,y with x+y=d, x^3+y^3+z^3=k.
    x^3+y^3 = d^3 - 3*d*x*y = k - z^3
    => x*y = (d**3 - (k - z**3)) / (3*d)
    x,y are roots of t^2 - d*t + xy = 0 => discriminant = d^2 - 4*xy must be a perfect square,
    and same parity as d."""
    if d == 0:
        return None
    numer = d**3 - (k - z**3)
    denom = 3 * d
    if numer % denom != 0:
        return None
    xy = numer // denom
    disc = d*d - 4*xy
    if disc < 0:
        return None
    r = isqrt(disc)
    if r*r != disc:
        return None
    if (d - r) % 2 != 0:
        return None
    x = (d + r) // 2
    y = (d - r) // 2
    if x**3 + y**3 + z**3 == k:
        return (x, y, z)
    return None

def verify(x, y, z, k):
    return x**3 + y**3 + z**3 == k

def search(k, d_max, b_max):
    """Booker-style search: for each d in [1, d_max] (both signs), find residues r mod |d|
    with r^3 = k (mod |d|), then scan z = r (mod d) within [-b_max, b_max] and try to
    reconstruct x,y. Returns (solution, d_used) or (None, None)."""
    for d_abs in range(1, d_max + 1):
        for d in (d_abs, -d_abs):
            km = k % d_abs
            residues = [r for r in range(d_abs) if pow(r, 3, d_abs) == km]
            for r in residues:
                z = r
                while z <= b_max:
                    if z >= -b_max:
                        sol = reconstruct_xy(d, z, k)
                        if sol:
                            return sol, d
                    z += d_abs
                z = r - d_abs
                while z >= -b_max:
                    sol = reconstruct_xy(d, z, k)
                    if sol:
                        return sol, d
                    z -= d_abs
    return None, None