func (z *Int128) Div(x, y *Int128) *Int128 {
	var r Int128
	z.DivMod(x, y, &r)
	return z
}
Div sets z to the quotient x/y and returns z.
package decimal
type Int128 struct {
	lo uint64
	hi int64
}
var (
	intOne = &Int128{1, 0}
	intTen = &Int128{10, 0}
)
func overflow() {
	panic("Arithmetic overflow")
}
func (z *Int128) SetInt64(x int64) *Int128 {
	z.lo = uint64(x)
	if x < 0 {
		z.hi = -1
	} else {
		z.hi = 0
	}
	return z
}
func (z *Int128) Set(x *Int128) *Int128 {
	if z != x {
		z.lo = x.lo
		z.hi = x.hi
	}
	return z
}
func (x Int128) Int64() int64 {
	return int64(x.lo)
}
func (x Int128) Float64() float64 {
	var d Int128
	d.Abs(&x)
	f := float64(d.lo) + float64(d.hi)*float64(1<<64)
	if x.Sign() < 0 {
		return -f
	}
	return f
}
func (x Int128) Sign() int {
	if x.lo == 0 && x.hi == 0 {
		return 0
	}
	if x.hi < 0 {
		return -1
	}
	return 1
}
func (x Int128) Cmp(y *Int128) int {
	if x.hi > y.hi {
		return 1
	} else if x.hi < y.hi {
		return -1
	} else if x.lo > y.lo {
		return 1
	} else if x.lo < y.lo {
		return -1
	}
	return 0
}
func (z *Int128) Abs(x *Int128) *Int128 {
	if x.hi < 0 {
		z.Neg(x)
	} else if z != x {
		z.hi = x.hi
		z.lo = x.lo
	}
	return z
}
func (z *Int128) Neg(x *Int128) *Int128 {
	if x.lo != 0 || x.hi != 0 {
		z.hi = ^x.hi
		z.lo = -x.lo
	} else if x != z {
		z.hi = 0
		z.lo = 0
	}
	return z
}
func (z *Int128) Add(x, y *Int128) *Int128 {
	lo := x.lo
	xneg := x.hi < 0
	yneg := y.hi < 0
	z.lo = x.lo + y.lo
	z.hi = x.hi + y.hi
	if z.lo < lo {
		z.hi++
	}
	if xneg == yneg && xneg != (z.hi < 0) {
		overflow()
	}
	return z
}
func (z *Int128) Sub(x, y *Int128) *Int128 {
	lo := x.lo
	xneg := x.hi < 0
	yneg := y.hi < 0
	z.lo = x.lo - y.lo
	z.hi = x.hi - y.hi
	if z.lo > lo {
		z.hi--
	}
	if xneg != yneg && xneg != (z.hi < 0) {
		overflow()
	}
	return z
}
func (z *Int128) Lsh(x *Int128, n uint) *Int128 {
	if n > 63 {
		n -= 64
		z.hi = int64(x.lo)
		z.lo = 0
	} else {
		z.hi = x.hi
		z.lo = x.lo
	}
	if n == 0 {
		return z
	}
	z.hi = int64(uint64(z.hi)<<n + z.lo>>(64-n))
	z.lo <<= n
	return z
}
func (z *Int128) Rsh(x *Int128, n uint) *Int128 {
	if n > 63 {
		n -= 64
		z.lo = uint64(z.hi)
		if x.hi < 0 {
			x.hi = -1
		} else {
			x.hi = 0
		}
	} else {
		z.hi = x.hi
		z.lo = x.lo
	}
	if n == 0 {
		return z
	}
	z.hi >>= n
	z.lo = uint64(z.hi)<<(64-n) + z.lo>>n
	return z
}
func (x *Int128) Bit(i int) uint {
	if i < 64 {
		return uint(x.lo>>uint(i)) & 1
	}
	return uint(x.hi>>uint(i-64)) & 1
}
func (z *Int128) SetBit(x *Int128, i int, b uint) *Int128 {
	if x != z {
		z.lo = x.lo
		z.hi = x.hi
	}
	if i < 64 {
		if b == 0 {
			z.lo = x.lo &^ (1 << uint(i))
		} else {
			z.lo = x.lo | (1 << uint(i))
		}
	} else {
		if b == 0 {
			z.hi = x.hi &^ (1 << uint(i-64))
		} else {
			z.hi = x.hi | (1 << uint(i-64))
		}
	}
	return z
}
const mask = 0xffffffff
func mul(x, y, z *Int128) {
	var u, v [4]uint64
	var w [8]uint64
	u[0] = x.lo & mask
	u[1] = x.lo >> 32
	u[2] = uint64(x.hi) & mask
	u[3] = uint64(x.hi) >> 32
	v[0] = y.lo & mask
	v[1] = y.lo >> 32
	v[2] = uint64(y.hi) & mask
	v[3] = uint64(y.hi) >> 32
	var k, t uint64
	for j := 0; j < 4; j++ {
		k = 0
		for i := 0; i < 4; i++ {
			t = u[i]*v[j] + w[i+j] + k
			w[i+j] = t & mask  
			k = t >> 32        
		}
		w[j+4] = k
	}
	if w[4] != 0 || w[5] != 0 || w[6] != 0 || w[7] != 0 || w[3]&0x80000000 != 0 {
		overflow()
	}
	z.lo = w[0] | (w[1] << 32)
	z.hi = int64(w[2] | (w[3] << 32))
}
func (z *Int128) Mul(x, y *Int128) *Int128 {
	if (x.lo == 0 && x.hi == 0) ||
		(y.lo == 0 && y.hi == 0) {
		z.lo = 0
		z.hi = 0
		return z
	}
	var u, v, w Int128
	u.Abs(x)
	v.Abs(y)
	mul(&u, &v, &w)
	if (x.Sign() < 0) != (y.Sign() < 0) {
		z.Neg(&w)
	} else {
		*z = w
	}
	return z
}
func leadingZeros(x uint32) uint {
	if x == 0 {
		return 32
	}
	var n uint = 0
	if x <= 0x0000ffff {
		n += 16
		x <<= 16
	}
	if x <= 0x00ffffff {
		n += 8
		x <<= 8
	}
	if x <= 0x0fffffff {
		n += 4
		x <<= 4
	}
	if x <= 0x3fffffff {
		n += 2
		x <<= 2
	}
	if x <= 0x7fffffff {
		n++
	}
	return n
}
func divmod(xu, xv, xq, xr *Int128) {
	var v, q, r [4]uint32
	var u [5]uint32
	u[0] = uint32(xu.lo & mask)
	u[1] = uint32(xu.lo >> 32)
	u[2] = uint32(uint64(xu.hi) & mask)
	u[3] = uint32(uint64(xu.hi) >> 32)
	v[0] = uint32(xv.lo & mask)
	v[1] = uint32(xv.lo >> 32)
	v[2] = uint32(uint64(xv.hi) & mask)
	v[3] = uint32(uint64(xv.hi) >> 32)
	n := 4
	for n >= 0 && v[n-1] == 0 {
		n--
	}
	shift := leadingZeros(uint32(v[n-1]))
	u[4] = u[3] >> (32 - shift)
	for i := 3; i > 0; i-- {
		u[i] = u[i]<<shift | u[i-1]>>(32-shift)
	}
	u[0] <<= shift
	for i := n - 1; i > 0; i-- {
		v[i] = v[i]<<shift | v[i-1]>>(32-shift)
	}
	v[0] <<= shift
	var b uint64 = 1 << 32
	var qhat, rhat uint64
	for j := 4 - n; j >= 0; j-- {
		if u[j+n] == v[n-1] {
			qhat = b - 1
		} else {
			qhat = (uint64(u[j+n])<<32 + uint64(u[j+n-1])) / uint64(v[n-1])
		}
		rhat = (uint64(u[j+n])<<32 + uint64(u[j+n-1])) - qhat*uint64(v[n-1])
		for uint64(v[n-2])*qhat > rhat<<32+uint64(u[j+n-2]) {
			qhat--
			rhat += uint64(v[n-1])
			if rhat >= b {
				break
			}
		}
		var p uint64
		var k, t int64
		k = 0
		for i := 0; i < n; i++ {
			p = qhat * uint64(v[i])
			t = int64(u[i+j]) - k - int64(p&mask)
			u[i+j] = uint32(t & mask)
			k = int64(p>>32) - t>>32
		}
		t = int64(u[j+n]) - k
		u[j+n] = uint32(t & mask)
		q[j] = uint32(qhat)
		if t < 0 {
			q[j]--
			k = 0
			for i := 0; i < n; i++ {
				t = int64(u[i+j]) + int64(v[i]) + k
				u[i+j] = uint32(t & mask)
				k = t >> 32
			}
			u[j+n] += uint32(k)
		}
	}
	for i := 0; i < n-1; i++ {
		r[i] = u[i]>>shift | u[i+1]<<(32-shift)
	}
	r[n-1] = u[n-1] >> shift
	xq.hi = int64(uint64(q[2]) | (uint64(q[3]) << 32))
	xq.lo = uint64(q[0]) | (uint64(q[1]) << 32)
	xr.hi = int64(uint64(r[2]) | (uint64(r[3]) << 32))
	xr.lo = uint64(r[0]) | (uint64(r[1]) << 32)
	return
}
func divmod32(xu, xv, xq, xr *Int128) {
	var u, q [4]uint64
	u[0] = xu.lo & mask
	u[1] = xu.lo >> 32
	u[2] = uint64(xu.hi) & mask
	u[3] = uint64(xu.hi) >> 32
	var r uint64
	for j := 3; j >= 0; j-- {
		q[j] = (r<<32 + u[j]) / xv.lo
		r = (r<<32 + u[j]) % xv.lo
	}
	xq.hi = int64(q[2] | (q[3] << 32))
	xq.lo = q[0] | (q[1] << 32)
	xr.hi = 0
	xr.lo = r
	return
}
func (z *Int128) DivMod(x, y, r *Int128) (*Int128, *Int128) {
	if y.hi == 0 && y.lo == 0 {
		panic("Division by zero")
	} else if y.lo == 1 && y.hi == 0 {
		if z != x {
			z.lo = x.lo
			z.hi = x.hi
		}
		r.lo = 0
		r.hi = 0
		return z, r
	} else if x.lo == 0 && x.hi == 0 {
		z.lo = 0
		z.hi = 0
		r.lo = 0
		r.hi = 0
		return z, r
	} else if x == y || (x.lo == y.lo && x.hi == y.hi) {
		z.lo = 1
		z.hi = 0
		r.lo = 0
		r.hi = 0
		return z, r
	}
	var u, v, q Int128
	u.Abs(x)
	v.Abs(y)
	if v.Cmp(&u) > 0 {
		if r != x {
			r.lo = x.lo
			r.hi = x.hi
		}
		z.lo = 0
		z.hi = 0
		return z, r
	}
	if u.hi == 0 && v.hi == 0 {
		q.lo = u.lo / v.lo
		r.lo = u.lo % v.lo
	} else if v.hi == 0 && (v.lo>>32) == 0 {
		divmod32(&u, &v, &q, r)
	} else {
		divmod(&u, &v, &q, r)
	}
	if (x.Sign() < 0) != (y.Sign() < 0) {
		q.Neg(&q)
	}
	if x.Sign() < 0 {
		r.Neg(r)
	}
	z.lo = q.lo
	z.hi = q.hi
	return z, r
}