func MinVal(val int, vals ...int) int {
	res := val
	for _, v := range vals {
		if v < res {
			res = v
		}
	}
	return res
}
MinVal returns the smallest argument passed.
package mathutil
import (
	"math"
	"math/big"
)
const (
	MaxInt      = 1<<(IntBits-1) - 1
	MinInt      = -MaxInt - 1
	MaxUint     = 1<<IntBits - 1
	IntBits     = 1 << (^uint(0)>>32&1 + ^uint(0)>>16&1 + ^uint(0)>>8&1 + 3)
	UintPtrBits = 1 << (^uintptr(0)>>32&1 + ^uintptr(0)>>16&1 + ^uintptr(0)>>8&1 + 3)
)
var (
	_1 = big.NewInt(1)
	_2 = big.NewInt(2)
)
func GCDByte(a, b byte) byte {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func GCDUint16(a, b uint16) uint16 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func GCDUint32(a, b uint32) uint32 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func GCDUint64(a, b uint64) uint64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func ISqrt(n uint32) (x uint32) {
	if n == 0 {
		return
	}
	if n >= math.MaxUint16*math.MaxUint16 {
		return math.MaxUint16
	}
	var px, nx uint32
	for x = n; ; px, x = x, nx {
		nx = (x + n/x) / 2
		if nx == x || nx == px {
			break
		}
	}
	return
}
func SqrtUint64(n uint64) (x uint64) {
	if n == 0 {
		return
	}
	if n >= math.MaxUint32*math.MaxUint32 {
		return math.MaxUint32
	}
	var px, nx uint64
	for x = n; ; px, x = x, nx {
		nx = (x + n/x) / 2
		if nx == x || nx == px {
			break
		}
	}
	return
}
func SqrtBig(n *big.Int) (x *big.Int) {
	switch n.Sign() {
	case -1:
		panic(-1)
	case 0:
		return big.NewInt(0)
	}
	var px, nx big.Int
	x = big.NewInt(0)
	x.SetBit(x, n.BitLen()/2+1, 1)
	for {
		nx.Rsh(nx.Add(x, nx.Div(n, x)), 1)
		if nx.Cmp(x) == 0 || nx.Cmp(&px) == 0 {
			break
		}
		px.Set(x)
		x.Set(&nx)
	}
	return
}
func Log2Byte(n byte) int {
	return log2[n]
}
func Log2Uint16(n uint16) int {
	if b := n >> 8; b != 0 {
		return log2[b] + 8
	}
	return log2[n]
}
func Log2Uint32(n uint32) int {
	if b := n >> 24; b != 0 {
		return log2[b] + 24
	}
	if b := n >> 16; b != 0 {
		return log2[b] + 16
	}
	if b := n >> 8; b != 0 {
		return log2[b] + 8
	}
	return log2[n]
}
func Log2Uint64(n uint64) int {
	if b := n >> 56; b != 0 {
		return log2[b] + 56
	}
	if b := n >> 48; b != 0 {
		return log2[b] + 48
	}
	if b := n >> 40; b != 0 {
		return log2[b] + 40
	}
	if b := n >> 32; b != 0 {
		return log2[b] + 32
	}
	if b := n >> 24; b != 0 {
		return log2[b] + 24
	}
	if b := n >> 16; b != 0 {
		return log2[b] + 16
	}
	if b := n >> 8; b != 0 {
		return log2[b] + 8
	}
	return log2[n]
}
func ModPowByte(b, e, m byte) byte {
	if b == 0 && e == 0 {
		panic(0)
	}
	if m == 1 {
		return 0
	}
	r := uint16(1)
	for b, m := uint16(b), uint16(m); e > 0; b, e = b*b%m, e>>1 {
		if e&1 == 1 {
			r = r * b % m
		}
	}
	return byte(r)
}
func ModPowUint16(b, e, m uint16) uint16 {
	if b == 0 && e == 0 {
		panic(0)
	}
	if m == 1 {
		return 0
	}
	r := uint32(1)
	for b, m := uint32(b), uint32(m); e > 0; b, e = b*b%m, e>>1 {
		if e&1 == 1 {
			r = r * b % m
		}
	}
	return uint16(r)
}
func ModPowUint32(b, e, m uint32) uint32 {
	if b == 0 && e == 0 {
		panic(0)
	}
	if m == 1 {
		return 0
	}
	r := uint64(1)
	for b, m := uint64(b), uint64(m); e > 0; b, e = b*b%m, e>>1 {
		if e&1 == 1 {
			r = r * b % m
		}
	}
	return uint32(r)
}
func ModPowUint64(b, e, m uint64) (r uint64) {
	if b == 0 && e == 0 {
		panic(0)
	}
	if m == 1 {
		return 0
	}
	return modPowBigInt(big.NewInt(0).SetUint64(b), big.NewInt(0).SetUint64(e), big.NewInt(0).SetUint64(m)).Uint64()
}
func modPowBigInt(b, e, m *big.Int) (r *big.Int) {
	r = big.NewInt(1)
	for i, n := 0, e.BitLen(); i < n; i++ {
		if e.Bit(i) != 0 {
			r.Mod(r.Mul(r, b), m)
		}
		b.Mod(b.Mul(b, b), m)
	}
	return
}
func ModPowBigInt(b, e, m *big.Int) (r *big.Int) {
	if b.Sign() == 0 && e.Sign() == 0 {
		panic(0)
	}
	if m.Cmp(_1) == 0 {
		return big.NewInt(0)
	}
	if e.Sign() < 0 {
		return
	}
	return modPowBigInt(big.NewInt(0).Set(b), big.NewInt(0).Set(e), m)
}
var uint64ToBigIntDelta big.Int
func init() {
	uint64ToBigIntDelta.SetBit(&uint64ToBigIntDelta, 63, 1)
}
var uintptrBits int
func init() {
	x := uint64(math.MaxUint64)
	uintptrBits = BitLenUintptr(uintptr(x))
}
func UintptrBits() int {
	return uintptrBits
}
func AddUint128_64(a, b uint64) (hi uint64, lo uint64) {
	lo = a + b
	if lo < a {
		hi = 1
	}
	return
}
func MulUint128_64(a, b uint64) (hi, lo uint64) {
	const w = 32
	const m = 1<<w - 1
	ahi, bhi, alo, blo := a>>w, b>>w, a&m, b&m
	lo = alo * blo
	mid1 := alo * bhi
	mid2 := ahi * blo
	c1, lo := AddUint128_64(lo, mid1<<w)
	c2, lo := AddUint128_64(lo, mid2<<w)
	_, hi = AddUint128_64(ahi*bhi, mid1>>w+mid2>>w+c1+c2)
	return
}
func PowerizeBigInt(b, n *big.Int) (e uint32, p *big.Int) {
	switch {
	case b.Cmp(_2) < 0 || n.Sign() < 0:
		return
	case n.Sign() == 0 || n.Cmp(_1) == 0:
		return 0, big.NewInt(1)
	case b.Cmp(_2) == 0:
		p = big.NewInt(0)
		e = uint32(n.BitLen() - 1)
		p.SetBit(p, int(e), 1)
		if p.Cmp(n) < 0 {
			p.Mul(p, _2)
			e++
		}
		return
	}
	bw := b.BitLen()
	nw := n.BitLen()
	p = big.NewInt(1)
	var bb, r big.Int
	for {
		switch p.Cmp(n) {
		case -1:
			x := uint32((nw - p.BitLen()) / bw)
			if x == 0 {
				x = 1
			}
			e += x
			switch x {
			case 1:
				p.Mul(p, b)
			default:
				r.Set(_1)
				bb.Set(b)
				e := x
				for {
					if e&1 != 0 {
						r.Mul(&r, &bb)
					}
					if e >>= 1; e == 0 {
						break
					}
					bb.Mul(&bb, &bb)
				}
				p.Mul(p, &r)
			}
		case 0, 1:
			return
		}
	}
}
func PowerizeUint32BigInt(b uint32, n *big.Int) (e uint32, p *big.Int) {
	switch {
	case b < 2 || n.Sign() < 0:
		return
	case n.Sign() == 0 || n.Cmp(_1) == 0:
		return 0, big.NewInt(1)
	case b == 2:
		p = big.NewInt(0)
		e = uint32(n.BitLen() - 1)
		p.SetBit(p, int(e), 1)
		if p.Cmp(n) < 0 {
			p.Mul(p, _2)
			e++
		}
		return
	}
	var bb big.Int
	bb.SetInt64(int64(b))
	return PowerizeBigInt(&bb, n)
}
func ProbablyPrimeUint32(n, a uint32) bool {
	d, s := n-1, 0
	for ; d&1 == 0; d, s = d>>1, s+1 {
	}
	x := uint64(ModPowUint32(a, d, n))
	if x == 1 || uint32(x) == n-1 {
		return true
	}
	for ; s > 1; s-- {
		if x = x * x % uint64(n); x == 1 {
			return false
		}
		if uint32(x) == n-1 {
			return true
		}
	}
	return false
}
func ProbablyPrimeUint64_32(n uint64, a uint32) bool {
	d, s := n-1, 0
	for ; d&1 == 0; d, s = d>>1, s+1 {
	}
	x := ModPowUint64(uint64(a), d, n)
	if x == 1 || x == n-1 {
		return true
	}
	bx, bn := big.NewInt(0).SetUint64(x), big.NewInt(0).SetUint64(n)
	for ; s > 1; s-- {
		if x = bx.Mod(bx.Mul(bx, bx), bn).Uint64(); x == 1 {
			return false
		}
		if x == n-1 {
			return true
		}
	}
	return false
}
func ProbablyPrimeBigInt_32(n *big.Int, a uint32) bool {
	var d big.Int
	d.Set(n)
	d.Sub(&d, _1)  
	s := 0
	for ; d.Bit(s) == 0; s++ {
	}
	nMinus1 := big.NewInt(0).Set(&d)
	d.Rsh(&d, uint(s))
	x := ModPowBigInt(big.NewInt(int64(a)), &d, n)
	if x.Cmp(_1) == 0 || x.Cmp(nMinus1) == 0 {
		return true
	}
	for ; s > 1; s-- {
		if x = x.Mod(x.Mul(x, x), n); x.Cmp(_1) == 0 {
			return false
		}
		if x.Cmp(nMinus1) == 0 {
			return true
		}
	}
	return false
}
func ProbablyPrimeBigInt(n, a *big.Int) bool {
	var d big.Int
	d.Set(n)
	d.Sub(&d, _1)  
	s := 0
	for ; d.Bit(s) == 0; s++ {
	}
	nMinus1 := big.NewInt(0).Set(&d)
	d.Rsh(&d, uint(s))
	x := ModPowBigInt(a, &d, n)
	if x.Cmp(_1) == 0 || x.Cmp(nMinus1) == 0 {
		return true
	}
	for ; s > 1; s-- {
		if x = x.Mod(x.Mul(x, x), n); x.Cmp(_1) == 0 {
			return false
		}
		if x.Cmp(nMinus1) == 0 {
			return true
		}
	}
	return false
}
func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func MaxVal(val int, vals ...int) int {
	res := val
	for _, v := range vals {
		if v > res {
			res = v
		}
	}
	return res
}