use std::u32;
use std::u64;

type U32DivModResult = (u32, u32);
type U64DivModResult = (u64, u64);

fn divmod(dividend: u32, divisor: u32) -> U32DivModResult {
    let quotient = dividend / divisor;
    let remainder = dividend % divisor;
    (quotient, remainder)
}

fn div_mod_u64_v9(numerator: u64, divisor: u64) -> U64DivModResult {
    let num_hi = (numerator >> 32) as u32;
    let num_lo = (numerator & u32::MAX as u64) as u32;
    let div_hi = (divisor >> 32) as u32;
    let div_lo = (divisor & u32::MAX as u64) as u32;

    if div_hi == 0 && num_hi == 0 {
        let (quotient, remainder) = divmod(num_lo, div_lo);
        return (quotient as u64, remainder as u64);
    }

    let mut res;

    let mut q1 = 0;
    if div_hi != 0 {
        res = divmod(num_hi, div_hi);
        q1 = res.0 as u64;
    }

    let mut r1_lo = q1 * div_lo as u64;
    let mut r1_hi = q1 * div_hi as u64 + (r1_lo >> 32);
    r1_lo = r1_lo & u32::MAX as u64;

    if r1_hi > num_hi as u64 || (r1_hi == num_hi as u64 && r1_lo > num_lo as u64) {
        q1 -= 1;
        r1_lo = q1 * div_lo as u64;
        r1_hi = q1 * div_hi as u64 + (r1_lo >> 32);
        r1_lo = r1_lo & u32::MAX as u64;
    }

    let rem1_hi = num_hi.wrapping_sub(r1_hi as u32);
    let (rem1_lo, borrow) = num_lo.overflowing_sub(r1_lo as u32);
    let rem2 = ((rem1_hi as u64) << 32) | rem1_lo as u64;
    let rem2 = if borrow {
        rem2.wrapping_sub(1 << 32)
    } else {
        rem2
    };

    res = divmod((rem2 >> 32) as u32, div_hi);
    let mut q2 = res.0 as u64;

    let mut r2_lo = q2 * div_lo as u64;
    let mut r2_hi = q2 * div_hi as u64 + (r2_lo >> 32);
    r2_lo = r2_lo & u32::MAX as u64;

    if r2_hi > rem1_hi as u64 || (r2_hi == rem1_hi as u64 && r2_lo > rem1_lo as u64) {
        q2 -= 1;
        r2_lo = q2 * div_lo as u64;
        r2_hi = q2 * div_hi as u64 + (r2_lo >> 32);
        r2_lo = r2_lo & u32::MAX as u64;
    }

    let remainder = rem2 - ((r2_hi << 32) | r2_lo);
    let quotient = (q1) + q2;

    (quotient, remainder)
}