func newCap(n, prevCap int) int {
	return max(n, nextPow2(prevCap))
}
newCap suggests a new increased capacity, favoring powers of two,
when growing a slice to length n. The suggested capacities guarantee
linear amortized cost for repeated memory allocations.
package bit
import (
	"fmt"
	"math/bits"
	"strings"
)
const (
	bpw   = 64          
	maxw  = 1<<bpw - 1  
	shift = 6
	mask  = 0x3f
)
type Set struct {
	data []uint64
}
func New(n ...int) *Set {
	if len(n) == 0 {
		return new(Set)
	}
	max := n[0]
	for _, e := range n {
		if e > max {
			max = e
		}
	}
	if max < 0 {
		return new(Set)
	}
	s := &Set{
		data: make([]uint64, max>>shift+1),
	}
	for _, e := range n {
		if e >= 0 {
			s.data[e>>shift] |= 1 << uint(e&mask)
		}
	}
	return s
}
func (s *Set) Contains(n int) bool {
	if n < 0 {
		return false
	}
	d := s.data
	i := n >> shift
	if i >= len(d) {
		return false
	}
	return d[i]&(1<<uint(n&mask)) != 0
}
func (s1 *Set) Equal(s2 *Set) bool {
	if s1 == s2 {
		return true
	}
	a, b := s1.data, s2.data
	la := len(a)
	if la != len(b) {
		return false
	}
	for i := 0; i < la; i++ {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}
func (s1 *Set) Subset(s2 *Set) bool {
	if s1 == s2 {
		return true
	}
	a, b := s1.data, s2.data
	la := len(a)
	if la > len(b) {
		return false
	}
	for i := 0; i < la; i++ {
		if a[i]&^b[i] != 0 {
			return false
		}
	}
	return true
}
func (s *Set) Max() int {
	if len(s.data) == 0 {
		panic("max not defined for empty set")
	}
	d := s.data
	i := len(d) - 1
	return i<<shift + bits.Len64(d[i]) - 1
}
func (s *Set) Size() int {
	d := s.data
	n := 0
	for i, len := 0, len(d); i < len; i++ {
		if w := d[i]; w != 0 {
			n += bits.OnesCount64(w)
		}
	}
	return n
}
func (s *Set) Empty() bool {
	return len(s.data) == 0
}
func (s *Set) Next(m int) int {
	d := s.data
	len := len(d)
	if len == 0 {
		return -1
	}
	if m < 0 {
		if d[0]&1 != 0 {
			return 0
		}
		m = 0
	}
	i := m >> shift
	if i >= len {
		return -1
	}
	t := 1 + uint(m&mask)
	w := d[i] >> t << t  
	for i < len-1 && w == 0 {
		i++
		w = d[i]
	}
	if w == 0 {
		return -1
	}
	return i<<shift + bits.TrailingZeros64(w)
}
func (s *Set) Prev(m int) int {
	d := s.data
	len := len(d)
	if len == 0 || m <= 0 {
		return -1
	}
	i := len - 1
	if max := i<<shift + bits.Len64(d[i]) - 1; m > max {
		return max
	}
	i = m >> shift
	t := bpw - uint(m&mask)
	w := d[i] << t >> t  
	for i > 0 && w == 0 {
		i--
		w = d[i]
	}
	if w == 0 {
		return -1
	}
	return i<<shift + bits.Len64(w) - 1
}
func (s *Set) Visit(do func(n int) (skip bool)) (aborted bool) {
	d := s.data
	for i, len := 0, len(d); i < len; i++ {
		w := d[i]
		if w == 0 {
			continue
		}
		n := i << shift  
		for w != 0 {
			b := bits.TrailingZeros64(w)
			n += b
			if do(n) {
				return true
			}
			n++
			w >>= uint(b + 1)
			for w&1 != 0 {  
				if do(n) {
					return true
				}
				n++
				w >>= 1
			}
		}
	}
	return false
}
func (s *Set) String() string {
	buf := new(strings.Builder)
	buf.WriteByte('{')
	a, b := -1, -2  
	first := true
	s.Visit(func(n int) (skip bool) {
		if n == b+1 {
			b++  
			return
		}
		if first && a <= b {
			first = false
		} else if a <= b {
			buf.WriteByte(' ')
		}
		writeRange(buf, a, b)
		a, b = n, n  
		return
	})
	if !first && a <= b {
		buf.WriteByte(' ')
	}
	writeRange(buf, a, b)
	buf.WriteByte('}')
	return buf.String()
}
func writeRange(buf *strings.Builder, a, b int) {
	switch {
	case a > b:
		return  
	case a == b:
		fmt.Fprintf(buf, "%d", a)
	case a+1 == b:
		fmt.Fprintf(buf, "%d %d", a, b)
	default:
		fmt.Fprintf(buf, "%d..%d", a, b)
	}
}
func (s *Set) Add(n int) *Set {
	if n < 0 {
		return s
	}
	i := n >> shift
	if i >= len(s.data) {
		s.resize(i + 1)
	}
	s.data[i] |= 1 << uint(n&mask)
	return s
}
func (s *Set) Delete(n int) *Set {
	if n < 0 {
		return s
	}
	i := n >> shift
	if i >= len(s.data) {
		return s
	}
	s.data[i] &^= 1 << uint(n&mask)
	s.trim()
	return s
}
func (s *Set) AddRange(m, n int) *Set {
	if n < 1 || m >= n {
		return s
	}
	m = max(0, m)
	n--
	low, high := m>>shift, n>>shift
	if high >= len(s.data) {
		s.resize(high + 1)
	}
	d := s.data
	if low == high {
		d[low] |= bitMask(m&mask, n&mask)
		return s
	}
	d[low] |= bitMask(m&mask, bpw-1)
	for i := low + 1; i < high; i++ {
		d[i] = maxw
	}
	d[high] |= bitMask(0, n&mask)
	return s
}
func (s *Set) DeleteRange(m, n int) *Set {
	if n < 1 || m >= n {
		return s
	}
	m = max(0, m)
	n--
	d := s.data
	low, high := m>>shift, n>>shift
	if low >= len(d) {
		return s
	}
	if len(d) <= high {
		high = len(d) - 1  
		n = bpw - 1        
	}
	if low == high {
		d[low] &^= bitMask(m&mask, n&mask)
		s.trim()
		return s
	}
	d[low] &^= bitMask(m&mask, bpw-1)
	for i := low + 1; i < high; i++ {
		d[i] = 0
	}
	d[high] &^= bitMask(0, n&mask)
	s.trim()
	return s
}
func (s1 *Set) And(s2 *Set) *Set {
	return new(Set).SetAnd(s1, s2)
}
func (s1 *Set) Or(s2 *Set) *Set {
	return new(Set).SetOr(s1, s2)
}
func (s1 *Set) Xor(s2 *Set) *Set {
	return new(Set).SetXor(s1, s2)
}
func (s1 *Set) AndNot(s2 *Set) *Set {
	return new(Set).SetAndNot(s1, s2)
}
func (s *Set) Set(s1 *Set) *Set {
	s.realloc(len(s1.data))
	copy(s.data, s1.data)
	return s
}
func (s *Set) SetAnd(s1, s2 *Set) *Set {
	a, b := s1.data, s2.data
	n := min(len(a), len(b)) - 1
	for n >= 0 && a[n]&b[n] == 0 {
		n--
	}
	if s == s1 || s == s2 {
		s.resize(n + 1)
	} else {
		s.realloc(n + 1)
	}
	for i := 0; i <= n; i++ {
		s.data[i] = a[i] & b[i]
	}
	return s
}
func (s *Set) SetAndNot(s1, s2 *Set) *Set {
	a, b := s1.data, s2.data
	la, lb := len(a), len(b)
	n := la - 1
	if la <= lb {
		for n >= 0 && a[n]&^b[n] == 0 {
			n--
		}
	}
	if s == s1 || s == s2 {
		s.resize(n + 1)
	} else {
		s.realloc(n + 1)
	}
	d := s.data
	if m := lb; m <= n {
		copy(d[m:n+1], a[m:n+1])
		n = m - 1
	}
	for i := 0; i <= n; i++ {
		d[i] = a[i] &^ b[i]
	}
	return s
}
func (s *Set) SetOr(s1, s2 *Set) *Set {
	if len(s1.data) > len(s2.data) {
		s1, s2 = s2, s1
	}
	a, b := s1.data, s2.data
	la := len(a)
	n := len(b) - 1
	if s == s1 || s == s2 {
		s.resize(n + 1)
	} else {
		s.realloc(n + 1)
	}
	d := s.data
	copy(d[la:n+1], b[la:n+1])
	for i := 0; i < la; i++ {
		d[i] = a[i] | b[i]
	}
	return s
}
func (s *Set) SetXor(s1, s2 *Set) *Set {
	if len(s1.data) > len(s2.data) {
		s1, s2 = s2, s1
	}
	a, b := s1.data, s2.data
	la, lb := len(a), len(b)
	n := lb - 1
	if la == lb {  
		for n >= 0 && a[n]^b[n] == 0 {
			n--
		}
		if n == -1 {  
			s.realloc(0)
			return s
		}
	}
	if s == s1 || s == s2 {
		s.resize(n + 1)
	} else {
		s.realloc(n + 1)
	}
	d := s.data
	if la <= n {
		copy(d[la:n+1], b[la:n+1])
		n = la - 1
	}
	for i := 0; i <= n; i++ {
		d[i] = a[i] ^ b[i]
	}
	return s
}
func (s *Set) resize(n int) {
	d := s.data
	if s.realloc(n) {
		copy(s.data, d)
	}
}
func (s *Set) realloc(n int) (didAlloc bool) {
	if c := cap(s.data); c < n {
		s.data = make([]uint64, n, newCap(n, c))
		return true
	}
	d := s.data
	for i := len(d) - 1; i >= n; i-- {
		d[i] = 0
	}
	s.data = d[:n]
	return false
}