#[inline]
pub fn udivmod_1e19(n: u128) -> (u128, u64) {
let d = 10_000_000_000_000_000_000_u64;
let high = (n >> 64) as u64;
if high == 0 {
let low = n as u64;
return ((low / d) as u128, low % d);
}
let sr = 65 - high.leading_zeros();
let mut q: u128 = n << (128 - sr);
let mut r: u128 = n >> sr;
let mut carry: u64 = 0;
let mut i = 0;
while i < sr {
i += 1;
r = (r << 1) | (q >> 127);
q = (q << 1) | carry as u128;
let s = (d as u128).wrapping_sub(r).wrapping_sub(1) as i128 >> 127;
carry = (s & 1) as u64;
r -= (d as u128) & s as u128;
}
((q << 1) | carry as u128, r as u64)
}