// codesnip-guard: BitDp
#[cfg_attr(any(),rustfmt::skip)]pub use self::bitdp::{BitDpExt,Combinations,Subsets};#[cfg_attr(any(),rustfmt::skip)]mod bitdp{use super::{One,Zero};use std::ops::{Add,BitAnd,BitOr,BitXor,Div,Not,Shl,Shr,Sub};pub trait BitDpExt:Sized+Copy+Default+PartialEq+Eq+PartialOrd+Ord+Not<Output=Self>+BitAnd<Output=Self>+BitOr<Output=Self>+BitXor<Output=Self>+Shl<usize,Output=Self>+Shr<usize,Output=Self>+Add<Output=Self>+Sub<Output=Self>+Div<Output=Self>+Zero+One{fn contains(self,x:usize)->bool{self&(Self::one()<<x)!=Self::zero()}fn insert(self,x:usize)->Self{self|(Self::one()<<x)}fn remove(self,x:usize)->Self{self&!(Self::one()<<x)}fn is_subset(self,elements:Self)->bool{self&elements==elements}fn is_superset(self,elements:Self)->bool{elements.is_subset(self)}fn subsets(self)->Subsets<Self>{Subsets{mask:self,cur:Some(self)}}fn combinations(n:usize,k:usize)->Combinations<Self>{Combinations{mask:Self::one()<<n,cur:Some((Self::one()<<k)-Self::one())}}}impl BitDpExt for u8{}impl BitDpExt for u16{}impl BitDpExt for u32{}impl BitDpExt for u64{}impl BitDpExt for u128{}impl BitDpExt for usize{}#[derive(Debug,Clone)]pub struct Subsets<T>{mask:T,cur:Option<T>}impl<T>Iterator for Subsets<T>where T:BitDpExt{type Item=T;fn next(&mut self)->Option<Self::Item>{if let Some(cur)=self.cur{self.cur=if cur.is_zero(){None}else{Some((cur-T::one())&self.mask)};Some(cur)}else{None}}}#[derive(Debug,Clone)]pub struct Combinations<T>{mask:T,cur:Option<T>}impl<T>Iterator for Combinations<T>where T:BitDpExt{type Item=T;fn next(&mut self)->Option<Self::Item>{if let Some(cur)=self.cur{if cur<self.mask{self.cur=if cur==T::zero(){None}else{let x=cur&(!cur+T::one());let y=cur+x;Some(((cur&!y)/x/(T::one()+T::one()))|y)};Some(cur)}else{None}}else{None}}}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}