func (z *Int) Rsh(x *Int, n uint) *Int {
	if n&0x3f == 0 {
		switch n {
		case 0:
			return z.Set(x)
		case 64:
			return z.rsh64(x)
		case 128:
			return z.rsh128(x)
		case 192:
			return z.rsh192(x)
		default:
			return z.Clear()
		}
	}
	var (
		a, b uint64
	)
	switch {
	case n > 192:
		if n > 256 {
			return z.Clear()
		}
		z.rsh192(x)
		n -= 192
		goto sh192
	case n > 128:
		z.rsh128(x)
		n -= 128
		goto sh128
	case n > 64:
		z.rsh64(x)
		n -= 64
		goto sh64
	default:
		z.Set(x)
	}
	a = z[3] << (64 - n)
	z[3] = z[3] >> n
sh64:
	b = z[2] << (64 - n)
	z[2] = (z[2] >> n) | a
sh128:
	a = z[1] << (64 - n)
	z[1] = (z[1] >> n) | b
sh192:
	z[0] = (z[0] >> n) | a
	return z
}
Rsh sets z = x >> n and returns z.
package uint256
import (
	"encoding/binary"
	"math"
	"math/bits"
)
type Int [4]uint64
func NewInt(val uint64) *Int {
	z := &Int{}
	z.SetUint64(val)
	return z
}
func (z *Int) SetBytes(buf []byte) *Int {
	switch l := len(buf); l {
	case 0:
		z.Clear()
	case 1:
		z.SetBytes1(buf)
	case 2:
		z.SetBytes2(buf)
	case 3:
		z.SetBytes3(buf)
	case 4:
		z.SetBytes4(buf)
	case 5:
		z.SetBytes5(buf)
	case 6:
		z.SetBytes6(buf)
	case 7:
		z.SetBytes7(buf)
	case 8:
		z.SetBytes8(buf)
	case 9:
		z.SetBytes9(buf)
	case 10:
		z.SetBytes10(buf)
	case 11:
		z.SetBytes11(buf)
	case 12:
		z.SetBytes12(buf)
	case 13:
		z.SetBytes13(buf)
	case 14:
		z.SetBytes14(buf)
	case 15:
		z.SetBytes15(buf)
	case 16:
		z.SetBytes16(buf)
	case 17:
		z.SetBytes17(buf)
	case 18:
		z.SetBytes18(buf)
	case 19:
		z.SetBytes19(buf)
	case 20:
		z.SetBytes20(buf)
	case 21:
		z.SetBytes21(buf)
	case 22:
		z.SetBytes22(buf)
	case 23:
		z.SetBytes23(buf)
	case 24:
		z.SetBytes24(buf)
	case 25:
		z.SetBytes25(buf)
	case 26:
		z.SetBytes26(buf)
	case 27:
		z.SetBytes27(buf)
	case 28:
		z.SetBytes28(buf)
	case 29:
		z.SetBytes29(buf)
	case 30:
		z.SetBytes30(buf)
	case 31:
		z.SetBytes31(buf)
	default:
		z.SetBytes32(buf[l-32:])
	}
	return z
}
func (z *Int) Bytes32() [32]byte {
	var b [32]byte
	binary.BigEndian.PutUint64(b[0:8], z[3])
	binary.BigEndian.PutUint64(b[8:16], z[2])
	binary.BigEndian.PutUint64(b[16:24], z[1])
	binary.BigEndian.PutUint64(b[24:32], z[0])
	return b
}
func (z *Int) Bytes20() [20]byte {
	var b [20]byte
	binary.BigEndian.PutUint32(b[0:4], uint32(z[2]))
	binary.BigEndian.PutUint64(b[4:12], z[1])
	binary.BigEndian.PutUint64(b[12:20], z[0])
	return b
}
func (z *Int) Bytes() []byte {
	b := z.Bytes32()
	return b[32-z.ByteLen():]
}
func (z *Int) WriteToSlice(dest []byte) {
	end := len(dest) - 1
	if end > 31 {
		end = 31
	}
	for i := 0; i <= end; i++ {
		dest[end-i] = byte(z[i/8] >> uint64(8*(i%8)))
	}
}
func (z *Int) WriteToArray32(dest *[32]byte) {
	for i := 0; i < 32; i++ {
		dest[31-i] = byte(z[i/8] >> uint64(8*(i%8)))
	}
}
func (z *Int) WriteToArray20(dest *[20]byte) {
	for i := 0; i < 20; i++ {
		dest[19-i] = byte(z[i/8] >> uint64(8*(i%8)))
	}
}
func (z *Int) Uint64() uint64 {
	return z[0]
}
func (z *Int) Uint64WithOverflow() (uint64, bool) {
	return z[0], (z[1] | z[2] | z[3]) != 0
}
func (z *Int) Clone() *Int {
	return &Int{z[0], z[1], z[2], z[3]}
}
func (z *Int) Add(x, y *Int) *Int {
	var carry uint64
	z[0], carry = bits.Add64(x[0], y[0], 0)
	z[1], carry = bits.Add64(x[1], y[1], carry)
	z[2], carry = bits.Add64(x[2], y[2], carry)
	z[3], _ = bits.Add64(x[3], y[3], carry)
	return z
}
func (z *Int) AddOverflow(x, y *Int) (*Int, bool) {
	var carry uint64
	z[0], carry = bits.Add64(x[0], y[0], 0)
	z[1], carry = bits.Add64(x[1], y[1], carry)
	z[2], carry = bits.Add64(x[2], y[2], carry)
	z[3], carry = bits.Add64(x[3], y[3], carry)
	return z, carry != 0
}
func (z *Int) AddMod(x, y, m *Int) *Int {
	if (m[3] != 0) && (x[3] <= m[3]) && (y[3] <= m[3]) {
		var (
			s, t     Int
			overflow bool
		)
		s = *x
		if _, overflow = s.SubOverflow(&s, m); overflow {
			s = *x
		}
		t = *y
		if _, overflow = t.SubOverflow(&t, m); overflow {
			t = *y
		}
		if _, overflow = s.AddOverflow(&s, &t); overflow {
			s.Sub(&s, m)
		}
		t = s
		if _, overflow = s.SubOverflow(&s, m); overflow {
			s = t
		}
		*z = s
		return z
	}
	if m.IsZero() {
		return z.Clear()
	}
	if z == m {  
		m = m.Clone()
	}
	if _, overflow := z.AddOverflow(x, y); overflow {
		sum := [5]uint64{z[0], z[1], z[2], z[3], 1}
		var quot [5]uint64
		rem := udivrem(quot[:], sum[:], m)
		return z.Set(&rem)
	}
	return z.Mod(z, m)
}
func (z *Int) AddUint64(x *Int, y uint64) *Int {
	var carry uint64
	z[0], carry = bits.Add64(x[0], y, 0)
	z[1], carry = bits.Add64(x[1], 0, carry)
	z[2], carry = bits.Add64(x[2], 0, carry)
	z[3], _ = bits.Add64(x[3], 0, carry)
	return z
}
func (z *Int) PaddedBytes(n int) []byte {
	b := make([]byte, n)
	for i := 0; i < 32 && i < n; i++ {
		b[n-1-i] = byte(z[i/8] >> uint64(8*(i%8)))
	}
	return b
}
func (z *Int) SubUint64(x *Int, y uint64) *Int {
	var carry uint64
	z[0], carry = bits.Sub64(x[0], y, carry)
	z[1], carry = bits.Sub64(x[1], 0, carry)
	z[2], carry = bits.Sub64(x[2], 0, carry)
	z[3], _ = bits.Sub64(x[3], 0, carry)
	return z
}
func (z *Int) SubOverflow(x, y *Int) (*Int, bool) {
	var carry uint64
	z[0], carry = bits.Sub64(x[0], y[0], 0)
	z[1], carry = bits.Sub64(x[1], y[1], carry)
	z[2], carry = bits.Sub64(x[2], y[2], carry)
	z[3], carry = bits.Sub64(x[3], y[3], carry)
	return z, carry != 0
}
func (z *Int) Sub(x, y *Int) *Int {
	var carry uint64
	z[0], carry = bits.Sub64(x[0], y[0], 0)
	z[1], carry = bits.Sub64(x[1], y[1], carry)
	z[2], carry = bits.Sub64(x[2], y[2], carry)
	z[3], _ = bits.Sub64(x[3], y[3], carry)
	return z
}
func umulStep(z, x, y, carry uint64) (hi, lo uint64) {
	hi, lo = bits.Mul64(x, y)
	lo, carry = bits.Add64(lo, carry, 0)
	hi, _ = bits.Add64(hi, 0, carry)
	lo, carry = bits.Add64(lo, z, 0)
	hi, _ = bits.Add64(hi, 0, carry)
	return hi, lo
}
func umulHop(z, x, y uint64) (hi, lo uint64) {
	hi, lo = bits.Mul64(x, y)
	lo, carry := bits.Add64(lo, z, 0)
	hi, _ = bits.Add64(hi, 0, carry)
	return hi, lo
}
func umul(x, y *Int) [8]uint64 {
	var (
		res                           [8]uint64
		carry, carry4, carry5, carry6 uint64
		res1, res2, res3, res4, res5  uint64
	)
	carry, res[0] = bits.Mul64(x[0], y[0])
	carry, res1 = umulHop(carry, x[1], y[0])
	carry, res2 = umulHop(carry, x[2], y[0])
	carry4, res3 = umulHop(carry, x[3], y[0])
	carry, res[1] = umulHop(res1, x[0], y[1])
	carry, res2 = umulStep(res2, x[1], y[1], carry)
	carry, res3 = umulStep(res3, x[2], y[1], carry)
	carry5, res4 = umulStep(carry4, x[3], y[1], carry)
	carry, res[2] = umulHop(res2, x[0], y[2])
	carry, res3 = umulStep(res3, x[1], y[2], carry)
	carry, res4 = umulStep(res4, x[2], y[2], carry)
	carry6, res5 = umulStep(carry5, x[3], y[2], carry)
	carry, res[3] = umulHop(res3, x[0], y[3])
	carry, res[4] = umulStep(res4, x[1], y[3], carry)
	carry, res[5] = umulStep(res5, x[2], y[3], carry)
	res[7], res[6] = umulStep(carry6, x[3], y[3], carry)
	return res
}
func (z *Int) Mul(x, y *Int) *Int {
	var (
		res              Int
		carry            uint64
		res1, res2, res3 uint64
	)
	carry, res[0] = bits.Mul64(x[0], y[0])
	carry, res1 = umulHop(carry, x[1], y[0])
	carry, res2 = umulHop(carry, x[2], y[0])
	res3 = x[3]*y[0] + carry
	carry, res[1] = umulHop(res1, x[0], y[1])
	carry, res2 = umulStep(res2, x[1], y[1], carry)
	res3 = res3 + x[2]*y[1] + carry
	carry, res[2] = umulHop(res2, x[0], y[2])
	res3 = res3 + x[1]*y[2] + carry
	res[3] = res3 + x[0]*y[3]
	return z.Set(&res)
}
func (z *Int) MulOverflow(x, y *Int) (*Int, bool) {
	p := umul(x, y)
	copy(z[:], p[:4])
	return z, (p[4] | p[5] | p[6] | p[7]) != 0
}
func (z *Int) squared() {
	var (
		res                    Int
		carry0, carry1, carry2 uint64
		res1, res2             uint64
	)
	carry0, res[0] = bits.Mul64(z[0], z[0])
	carry0, res1 = umulHop(carry0, z[0], z[1])
	carry0, res2 = umulHop(carry0, z[0], z[2])
	carry1, res[1] = umulHop(res1, z[0], z[1])
	carry1, res2 = umulStep(res2, z[1], z[1], carry1)
	carry2, res[2] = umulHop(res2, z[0], z[2])
	res[3] = 2*(z[0]*z[3]+z[1]*z[2]) + carry0 + carry1 + carry2
	z.Set(&res)
}
func (z *Int) isBitSet(n uint) bool {
	return (z[n/64] & (1 << (n % 64))) != 0
}
func addTo(x, y []uint64) uint64 {
	var carry uint64
	for i := 0; i < len(y); i++ {
		x[i], carry = bits.Add64(x[i], y[i], carry)
	}
	return carry
}
func subMulTo(x, y []uint64, multiplier uint64) uint64 {
	var borrow uint64
	for i := 0; i < len(y); i++ {
		s, carry1 := bits.Sub64(x[i], borrow, 0)
		ph, pl := bits.Mul64(y[i], multiplier)
		t, carry2 := bits.Sub64(s, pl, 0)
		x[i] = t
		borrow = ph + carry1 + carry2
	}
	return borrow
}
func udivremBy1(quot, u []uint64, d uint64) (rem uint64) {
	reciprocal := reciprocal2by1(d)
	rem = u[len(u)-1]  
	for j := len(u) - 2; j >= 0; j-- {
		quot[j], rem = udivrem2by1(rem, u[j], d, reciprocal)
	}
	return rem
}
func udivremKnuth(quot, u, d []uint64) {
	dh := d[len(d)-1]
	dl := d[len(d)-2]
	reciprocal := reciprocal2by1(dh)
	for j := len(u) - len(d) - 1; j >= 0; j-- {
		u2 := u[j+len(d)]
		u1 := u[j+len(d)-1]
		u0 := u[j+len(d)-2]
		var qhat, rhat uint64
		if u2 >= dh {  
			qhat = ^uint64(0)
		} else {
			qhat, rhat = udivrem2by1(u2, u1, dh, reciprocal)
			ph, pl := bits.Mul64(qhat, dl)
			if ph > rhat || (ph == rhat && pl > u0) {
				qhat--
			}
		}
		borrow := subMulTo(u[j:], d, qhat)
		u[j+len(d)] = u2 - borrow
		if u2 < borrow {  
			qhat--
			u[j+len(d)] += addTo(u[j:], d)
		}
		quot[j] = qhat  
	}
}
func udivrem(quot, u []uint64, d *Int) (rem Int) {
	var dLen int
	for i := len(d) - 1; i >= 0; i-- {
		if d[i] != 0 {
			dLen = i + 1
			break
		}
	}
	shift := uint(bits.LeadingZeros64(d[dLen-1]))
	var dnStorage Int
	dn := dnStorage[:dLen]
	for i := dLen - 1; i > 0; i-- {
		dn[i] = (d[i] << shift) | (d[i-1] >> (64 - shift))
	}
	dn[0] = d[0] << shift
	var uLen int
	for i := len(u) - 1; i >= 0; i-- {
		if u[i] != 0 {
			uLen = i + 1
			break
		}
	}
	var unStorage [9]uint64
	un := unStorage[:uLen+1]
	un[uLen] = u[uLen-1] >> (64 - shift)
	for i := uLen - 1; i > 0; i-- {
		un[i] = (u[i] << shift) | (u[i-1] >> (64 - shift))
	}
	un[0] = u[0] << shift
	if dLen == 1 {
		r := udivremBy1(quot, un, dn[0])
		rem.SetUint64(r >> shift)
		return rem
	}
	udivremKnuth(quot, un, dn)
	for i := 0; i < dLen-1; i++ {
		rem[i] = (un[i] >> shift) | (un[i+1] << (64 - shift))
	}
	rem[dLen-1] = un[dLen-1] >> shift
	return rem
}
func (z *Int) Div(x, y *Int) *Int {
	if y.IsZero() || y.Gt(x) {
		return z.Clear()
	}
	if x.Eq(y) {
		return z.SetOne()
	}
	if x.IsUint64() {
		return z.SetUint64(x.Uint64() / y.Uint64())
	}
	var quot Int
	udivrem(quot[:], x[:], y)
	return z.Set(&quot)
}
func (z *Int) Mod(x, y *Int) *Int {
	if x.IsZero() || y.IsZero() {
		return z.Clear()
	}
	switch x.Cmp(y) {
	case -1:
		copy(z[:], x[:])
		return z
	case 0:
		return z.Clear()  
	}
	if x.IsUint64() {
		return z.SetUint64(x.Uint64() % y.Uint64())
	}
	var quot Int
	rem := udivrem(quot[:], x[:], y)
	return z.Set(&rem)
}
func (z *Int) SMod(x, y *Int) *Int {
	ys := y.Sign()
	xs := x.Sign()
	if xs == -1 {
		x = new(Int).Neg(x)
	}
	if ys == -1 {
		y = new(Int).Neg(y)
	}
	z.Mod(x, y)
	if xs == -1 {
		z.Neg(z)
	}
	return z
}
func (z *Int) MulModWithReciprocal(x, y, m *Int, mu *[5]uint64) *Int {
	if x.IsZero() || y.IsZero() || m.IsZero() {
		return z.Clear()
	}
	p := umul(x, y)
	if m[3] != 0 {
		r := reduce4(p, m, *mu)
		return z.Set(&r)
	}
	var (
		pl Int
		ph Int
	)
	copy(pl[:], p[:4])
	copy(ph[:], p[4:])
	if ph.IsZero() {
		return z.Mod(&pl, m)
	}
	var quot [8]uint64
	rem := udivrem(quot[:], p[:], m)
	return z.Set(&rem)
}
func (z *Int) MulMod(x, y, m *Int) *Int {
	if x.IsZero() || y.IsZero() || m.IsZero() {
		return z.Clear()
	}
	p := umul(x, y)
	if m[3] != 0 {
		mu := Reciprocal(m)
		r := reduce4(p, m, mu)
		return z.Set(&r)
	}
	var (
		pl Int
		ph Int
	)
	copy(pl[:], p[:4])
	copy(ph[:], p[4:])
	if ph.IsZero() {
		return z.Mod(&pl, m)
	}
	var quot [8]uint64
	rem := udivrem(quot[:], p[:], m)
	return z.Set(&rem)
}
func (z *Int) Abs(x *Int) *Int {
	if x[3] < 0x8000000000000000 {
		return z.Set(x)
	}
	return z.Sub(new(Int), x)
}
func (z *Int) Neg(x *Int) *Int {
	return z.Sub(new(Int), x)
}
func (z *Int) SDiv(n, d *Int) *Int {
	if n.Sign() > 0 {
		if d.Sign() > 0 {
			z.Div(n, d)
			return z
		} else {
			z.Div(n, new(Int).Neg(d))
			return z.Neg(z)
		}
	}
	if d.Sign() < 0 {
		z.Div(new(Int).Neg(n), new(Int).Neg(d))
		return z
	}
	z.Div(new(Int).Neg(n), d)
	return z.Neg(z)
}
func (z *Int) Sign() int {
	if z.IsZero() {
		return 0
	}
	if z[3] < 0x8000000000000000 {
		return 1
	}
	return -1
}
func (z *Int) BitLen() int {
	switch {
	case z[3] != 0:
		return 192 + bits.Len64(z[3])
	case z[2] != 0:
		return 128 + bits.Len64(z[2])
	case z[1] != 0:
		return 64 + bits.Len64(z[1])
	default:
		return bits.Len64(z[0])
	}
}
func (z *Int) ByteLen() int {
	return (z.BitLen() + 7) / 8
}
func (z *Int) lsh64(x *Int) *Int {
	z[3], z[2], z[1], z[0] = x[2], x[1], x[0], 0
	return z
}
func (z *Int) lsh128(x *Int) *Int {
	z[3], z[2], z[1], z[0] = x[1], x[0], 0, 0
	return z
}
func (z *Int) lsh192(x *Int) *Int {
	z[3], z[2], z[1], z[0] = x[0], 0, 0, 0
	return z
}
func (z *Int) rsh64(x *Int) *Int {
	z[3], z[2], z[1], z[0] = 0, x[3], x[2], x[1]
	return z
}
func (z *Int) rsh128(x *Int) *Int {
	z[3], z[2], z[1], z[0] = 0, 0, x[3], x[2]
	return z
}
func (z *Int) rsh192(x *Int) *Int {
	z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]
	return z
}
func (z *Int) srsh64(x *Int) *Int {
	z[3], z[2], z[1], z[0] = math.MaxUint64, x[3], x[2], x[1]
	return z
}
func (z *Int) srsh128(x *Int) *Int {
	z[3], z[2], z[1], z[0] = math.MaxUint64, math.MaxUint64, x[3], x[2]
	return z
}
func (z *Int) srsh192(x *Int) *Int {
	z[3], z[2], z[1], z[0] = math.MaxUint64, math.MaxUint64, math.MaxUint64, x[3]
	return z
}
func (z *Int) Not(x *Int) *Int {
	z[3], z[2], z[1], z[0] = ^x[3], ^x[2], ^x[1], ^x[0]
	return z
}
func (z *Int) Gt(x *Int) bool {
	return x.Lt(z)
}
func (z *Int) Slt(x *Int) bool {
	zSign := z.Sign()
	xSign := x.Sign()
	switch {
	case zSign >= 0 && xSign < 0:
		return false
	case zSign < 0 && xSign >= 0:
		return true
	default:
		return z.Lt(x)
	}
}
func (z *Int) Sgt(x *Int) bool {
	zSign := z.Sign()
	xSign := x.Sign()
	switch {
	case zSign >= 0 && xSign < 0:
		return true
	case zSign < 0 && xSign >= 0:
		return false
	default:
		return z.Gt(x)
	}
}
func (z *Int) Lt(x *Int) bool {
	_, carry := bits.Sub64(z[0], x[0], 0)
	_, carry = bits.Sub64(z[1], x[1], carry)
	_, carry = bits.Sub64(z[2], x[2], carry)
	_, carry = bits.Sub64(z[3], x[3], carry)
	return carry != 0
}
func (z *Int) SetUint64(x uint64) *Int {
	z[3], z[2], z[1], z[0] = 0, 0, 0, x
	return z
}
func (z *Int) Eq(x *Int) bool {
	return (z[0] == x[0]) && (z[1] == x[1]) && (z[2] == x[2]) && (z[3] == x[3])
}
func (z *Int) Cmp(x *Int) (r int) {
	d0, carry := bits.Sub64(z[0], x[0], 0)
	d1, carry := bits.Sub64(z[1], x[1], carry)
	d2, carry := bits.Sub64(z[2], x[2], carry)
	d3, carry := bits.Sub64(z[3], x[3], carry)
	if carry == 1 {
		return -1
	}
	if d0|d1|d2|d3 == 0 {
		return 0
	}
	return 1
}
func (z *Int) LtUint64(n uint64) bool {
	return z[0] < n && (z[1]|z[2]|z[3]) == 0
}
func (z *Int) GtUint64(n uint64) bool {
	return z[0] > n || (z[1]|z[2]|z[3]) != 0
}
func (z *Int) IsUint64() bool {
	return (z[1] | z[2] | z[3]) == 0
}
func (z *Int) IsZero() bool {
	return (z[0] | z[1] | z[2] | z[3]) == 0
}
func (z *Int) Clear() *Int {
	z[3], z[2], z[1], z[0] = 0, 0, 0, 0
	return z
}
func (z *Int) SetAllOne() *Int {
	z[3], z[2], z[1], z[0] = math.MaxUint64, math.MaxUint64, math.MaxUint64, math.MaxUint64
	return z
}
func (z *Int) SetOne() *Int {
	z[3], z[2], z[1], z[0] = 0, 0, 0, 1
	return z
}
func (z *Int) Lsh(x *Int, n uint) *Int {
	if n&0x3f == 0 {
		switch n {
		case 0:
			return z.Set(x)
		case 64:
			return z.lsh64(x)
		case 128:
			return z.lsh128(x)
		case 192:
			return z.lsh192(x)
		default:
			return z.Clear()
		}
	}
	var (
		a, b uint64
	)
	switch {
	case n > 192:
		if n > 256 {
			return z.Clear()
		}
		z.lsh192(x)
		n -= 192
		goto sh192
	case n > 128:
		z.lsh128(x)
		n -= 128
		goto sh128
	case n > 64:
		z.lsh64(x)
		n -= 64
		goto sh64
	default:
		z.Set(x)
	}
	a = z[0] >> (64 - n)
	z[0] = z[0] << n
sh64:
	b = z[1] >> (64 - n)
	z[1] = (z[1] << n) | a
sh128:
	a = z[2] >> (64 - n)
	z[2] = (z[2] << n) | b
sh192:
	z[3] = (z[3] << n) | a
	return z
}