結果
| 問題 | No.803 Very Limited Xor Subset |
| ユーザー |
 37kt
|
| 提出日時 | 2023-08-03 15:32:30 |
| 言語 | Rust (1.77.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 50,152 bytes |
| コンパイル時間 | 11,980 ms |
| コンパイル使用メモリ | 393,364 KB |
| 最終ジャッジ日時 | 2024-04-27 04:53:51 |
| 合計ジャッジ時間 | 13,008 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
error[E0659]: `proconio` is ambiguous
--> src/main.rs:5:5
|
5 | use proconio::{
| ^^^^^^^^ ambiguous name
|
= note: ambiguous because of a conflict between a name from a glob import and an outer scope during import or macro resolution
= note: `proconio` could refer to a crate passed with `--extern`
= help: use `::proconio` to refer to this crate unambiguously
note: `proconio` could also refer to the module imported here
--> src/main.rs:1:9
|
1 | pub use __cargo_equip::prelude::*;
| ^^^^^^^^^^^^^^^^^^^^^^^^^
= help: consider adding an explicit import of `proconio` to disambiguate
= help: or use `crate::proconio` to refer to this module unambiguously
For more information about this error, try `rustc --explain E0659`.
error: could not compile `main` (bin "main") due to 1 previous error
ソースコード
pub use __cargo_equip::prelude::*;
use fixedbitset::FixedBitSet;
#[allow(unused_imports)]
use proconio::{
input,
marker::{Bytes, Chars, Usize1},
};
const P: usize = 1_000_000_007;
fn main() {
input! {
n: usize,
m: usize,
x: usize,
a: [usize; n],
tlr: [(usize, Usize1, usize); m],
}
let mut y = FixedBitSet::with_capacity(m + 30);
let mut b = vec![FixedBitSet::with_capacity(m + 30); n];
for i in 0..m {
let (t, l, r) = tlr[i];
if t == 1 {
y.set(i, true);
}
for j in l..r {
b[j].set(i, true);
}
}
for i in 0..n {
for j in 0..30 {
if a[i] >> j & 1 == 1 {
b[i].set(m + j, true);
}
}
}
for i in 0..30 {
if x >> i & 1 == 1 {
y.set(m + i, true);
}
}
let mut r = 0;
for i in 0..m + 30 {
for j in r..n {
if b[j][i] {
b.swap(r, j);
for k in 0..n {
if r == k {
continue;
}
if b[k][i] {
b[k] = &b[k] ^ &b[r];
}
}
r += 1;
break;
}
}
}
// for i in 0..m + 30 {
// eprint!("{}", y[i] as i32);
// }
// eprintln!();
// for i in 0..n {
// for j in 0..m + 30 {
// eprint!("{}", b[i][j] as i32);
// }
// eprintln!();
// }
let mut res = 1;
let mut s = FixedBitSet::with_capacity(m + 30);
for i in 0..n {
let mut p = !0;
for j in 0..m + 30 {
if b[i][j] {
p = j;
break;
}
}
if p == !0 {
res = res * 2 % P;
continue;
}
if y[p] {
s ^= &b[i];
}
}
if s != y {
res = 0;
}
println!("{}", res);
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `fixedbitset 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::fixedbitset`
/// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::__lazy_static_1_4_0`
/// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
///
/// # License and Copyright Notices
///
/// - `fixedbitset 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// Copyright (c) 2015-2017
///
/// Permission is hereby granted, free of charge, to any
/// person obtaining a copy of this software and associated
/// documentation files (the "Software"), to deal in the
/// Software without restriction, including without
/// limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software
/// is furnished to do so, subject to the following
/// conditions:
///
/// The above copyright notice and this permission notice
/// shall be included in all copies or substantial portions
/// of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
/// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
/// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
/// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
/// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
/// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
/// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
/// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
/// ```
///
/// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// Copyright (c) 2010 The Rust Project Developers
///
/// Permission is hereby granted, free of charge, to any
/// person obtaining a copy of this software and associated
/// documentation files (the "Software"), to deal in the
/// Software without restriction, including without
/// limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software
/// is furnished to do so, subject to the following
/// conditions:
///
/// The above copyright notice and this permission notice
/// shall be included in all copies or substantial portions
/// of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
/// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
/// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
/// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
/// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
/// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
/// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
/// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
/// ```
///
/// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`
///
/// ```text
/// The MIT License
/// Copyright 2019 (C) statiolake <statiolake@gmail.com>
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of
/// this software and associated documentation files (the "Software"), to deal in
/// the Software without restriction, including without limitation the rights to
/// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software is furnished to do so,
/// subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all
/// copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
/// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
/// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
/// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
/// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
///
/// Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019. The
/// original macro is licensed under BSD 3-clause license.
///
/// Redistribution and use in source and binary forms, with or without
/// modification, are permitted provided that the following conditions are met:
///
/// 1. Redistributions of source code must retain the above copyright notice, this
/// list of conditions and the following disclaimer.
///
/// 2. Redistributions in binary form must reproduce the above copyright notice,
/// this list of conditions and the following disclaimer in the documentation
/// and/or other materials provided with the distribution.
///
/// 3. Neither the name of the copyright holder nor the names of its contributors
/// may be used to endorse or promote products derived from this software
/// without specific prior written permission.
///
/// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
/// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
/// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
/// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
/// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
/// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
/// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
/// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
/// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
/// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
/// ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod fixedbitset {#![cfg_attr(not(feature="std"),no_std)]mod range{use std::ops::{RangeFull,RangeFrom,RangeTo,Range,};pub trait IndexRange<T=usize>{#[inline]fn start(&self)->Option<T>{None}#[inline]fn end(&self)->Option<T>{None}}impl<T>IndexRange<T>for RangeFull{}impl<T:Copy>IndexRange<T>for RangeFrom<T>{#[inline]fn start(&self)->Option<T>{Some(self.start)}}impl<T:Copy>IndexRange<T>for RangeTo<T>{#[inline]fn end(&self)->Option<T>{Some(self.end)}}impl<T:Copy>IndexRange<T>for Range<T>{#[inline]fn start(&self)->Option<T>{Some(self.start)}#[inline]fn end(&self)->Option<T>{Some(self.end)}}}use std::fmt::Write;use std::fmt::{Display,Error,Formatter,Binary};use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Index};use std::cmp::{Ord,Ordering};use std::iter::{Chain,FromIterator};pub use range::IndexRange;const BITS:usize=32;type Block=u32;#[inline]fn div_rem(x:usize,d:usize)->(usize,usize){(x/d,x%d)}#[derive(Debug,PartialEq,Eq,PartialOrd,Ord,Hash,Default)]#[cfg_attr(feature="serde",derive(Serialize,Deserialize))]pub struct FixedBitSet{data:Vec<Block>,length:usize,}impl FixedBitSet{pub const fn new()->Self{FixedBitSet{data:Vec::new(),length:0,}}pub fn with_capacity(bits:usize)->Self{let(mut blocks,rem)=div_rem(bits,BITS);blocks+=(rem>0)as usize;FixedBitSet{data:vec![0;blocks],length:bits,}}pub fn with_capacity_and_blocks<I:IntoIterator<Item=Block>>(bits:usize,blocks:I)->Self{let(mut n_blocks,rem)=div_rem(bits,BITS);n_blocks+=(rem>0)as usize;let mut data:Vec<Block> =blocks.into_iter().collect();if data.len()!=n_blocks{data.resize(n_blocks,0);}let end=data.len()*32;for(block,mask)in Masks::new(bits..end,end){unsafe{*data.get_unchecked_mut(block)&=!mask;}}FixedBitSet{data:data,length:bits,}}pub fn grow(&mut self,bits:usize){let(mut blocks,rem)=div_rem(bits,BITS);blocks+=(rem>0)as usize;if bits>self.length{self.length=bits;self.data.resize(blocks,0);}}#[inline]pub fn len(&self)->usize{self.length}#[inline]pub fn contains(&self,bit:usize)->bool{let(block,i)=div_rem(bit,BITS);match self.data.get(block){None=>false,Some(b)=>(b&(1<<i))!=0,}}#[inline]pub fn clear(&mut self){for elt in&mut self.data[..]{*elt=0}}#[inline]pub fn insert(&mut self,bit:usize){assert!(bit<self.length,"insert at index {} exceeds fixbitset size {}",bit,self.length);let(block,i)=div_rem(bit,BITS);unsafe{*self.data.get_unchecked_mut(block)|=1<<i;}}#[inline]pub fn put(&mut self,bit:usize)->bool{assert!(bit<self.length,"put at index {} exceeds fixbitset size {}",bit,self.length);let(block,i)=div_rem(bit,BITS);unsafe{let word=self.data.get_unchecked_mut(block);let prev=*word&(1<<i)!=0;*word|=1<<i;prev}}#[inline]pub fn toggle(&mut self,bit:usize){assert!(bit<self.length,"toggle at index {} exceeds fixbitset size {}",bit,self.length);let(block,i)=div_rem(bit,BITS);unsafe{*self.data.get_unchecked_mut(block)^=1<<i;}}#[inline]pub fn set(&mut self,bit:usize,enabled:bool){assert!(bit<self.length,"set at index {} exceeds fixbitset size {}",bit,self.length);let(block,i)=div_rem(bit,BITS);unsafe{let elt=self.data.get_unchecked_mut(block);if enabled{*elt|=1<<i;}else{*elt&=!(1<<i);}}}#[inline]pub fn copy_bit(&mut self,from:usize,to:usize){assert!(to<self.length,"copy at index {} exceeds fixbitset size {}",to,self.length);let(to_block,t)=div_rem(to,BITS);let enabled=self.contains(from);unsafe{let to_elt=self.data.get_unchecked_mut(to_block);if enabled{*to_elt|=1<<t;}else{*to_elt&=!(1<<t);}}}#[inline]pub fn count_ones<T:IndexRange>(&self,range:T)->usize{Masks::new(range,self.length).map(|(block,mask)|unsafe{let value=*self.data.get_unchecked(block);(value&mask).count_ones()as usize}).sum()}#[inline]pub fn set_range<T:IndexRange>(&mut self,range:T,enabled:bool){for(block,mask)in Masks::new(range,self.length){unsafe{if enabled{*self.data.get_unchecked_mut(block)|=mask;}else{*self.data.get_unchecked_mut(block)&=!mask;}}}}#[inline]pub fn insert_range<T:IndexRange>(&mut self,range:T){self.set_range(range,true);}#[inline]pub fn toggle_range<T:IndexRange>(&mut self,range:T){for(block,mask)in Masks::new(range,self.length){unsafe{*self.data.get_unchecked_mut(block)^=mask;}}}#[inline]pub fn as_slice(&self)->&[u32]{&self.data}#[inline]pub fn as_mut_slice(&mut self)->&mut[u32]{&mut self.data}#[inline]pub fn ones(&self)->Ones{match self.as_slice().split_first(){Some((&block,rem))=>{Ones{bitset:block,block_idx:0,remaining_blocks:rem}}None=>{Ones{bitset:0,block_idx:0,remaining_blocks:&[]}}}}pub fn intersection<'a>(&'a self,other:&'a FixedBitSet)->Intersection<'a>{Intersection{iter:self.ones(),other:other,}}pub fn union<'a>(&'a self,other:&'a FixedBitSet)->Union<'a>{Union{iter:self.ones().chain(other.difference(self)),}}pub fn difference<'a>(&'a self,other:&'a FixedBitSet)->Difference<'a>{Difference{iter:self.ones(),other:other,}}pub fn symmetric_difference<'a>(&'a self,other:&'a FixedBitSet)->SymmetricDifference<'a>{SymmetricDifference{iter:self.difference(other).chain(other.difference(self)),}}pub fn union_with(&mut self,other:&FixedBitSet){if other.len()>=self.len(){self.grow(other.len());}for(x,y)in self.data.iter_mut().zip(other.data.iter()){*x|=*y;}}pub fn intersect_with(&mut self,other:&FixedBitSet){for(x,y)in self.data.iter_mut().zip(other.data.iter()){*x&=*y;}let mn=std::cmp::min(self.data.len(),other.data.len());for wd in&mut self.data[mn..]{*wd=0;}}pub fn difference_with(&mut self,other:&FixedBitSet){for(x,y)in self.data.iter_mut().zip(other.data.iter()){*x&=!*y;}}pub fn symmetric_difference_with(&mut self,other:&FixedBitSet){if other.len()>=self.len(){self.grow(other.len());}for(x,y)in self.data.iter_mut().zip(other.data.iter()){*x^=*y;}}pub fn is_disjoint(&self,other:&FixedBitSet)->bool{self.data.iter().zip(other.data.iter()).all(|(x,y)|x&y==0)}pub fn is_subset(&self,other:&FixedBitSet)->bool{self.data.iter().zip(other.data.iter()).all(|(x,y)|x&!y==0)&&self.data.iter().skip(other.data.len()).all(|x|*x==0)}pub fn is_superset(&self,other:&FixedBitSet)->bool{other.is_subset(self)}}impl Binary for FixedBitSet{fn fmt(&self,f:&mut Formatter<'_>)->Result<(),Error>{if f.alternate(){f.write_str("0b")?;}for i in 0..self.length{if self[i]{f.write_char('1')?;}else{f.write_char('0')?;}}Ok(())}}impl Display for FixedBitSet{fn fmt(&self,f:&mut Formatter<'_>)->Result<(),Error>{Binary::fmt(&self,f)}}pub struct Difference<'a>{iter:Ones<'a>,other:&'a FixedBitSet,}impl<'a>Iterator for Difference<'a>{type Item=usize;#[inline]fn next(&mut self)->Option<Self::Item>{while let Some(nxt)=self.iter.next(){if!self.other.contains(nxt){return Some(nxt);}}None}}pub struct SymmetricDifference<'a>{iter:Chain<Difference<'a>,Difference<'a>>,}impl<'a>Iterator for SymmetricDifference<'a>{type Item=usize;#[inline]fn next(&mut self)->Option<Self::Item>{self.iter.next()}}pub struct Intersection<'a>{iter:Ones<'a>,other:&'a FixedBitSet,}impl<'a>Iterator for Intersection<'a>{type Item=usize;#[inline]fn next(&mut self)->Option<Self::Item>{while let Some(nxt)=self.iter.next(){if self.other.contains(nxt){return Some(nxt);}}None}}pub struct Union<'a>{iter:Chain<Ones<'a>,Difference<'a>>,}impl<'a>Iterator for Union<'a>{type Item=usize;#[inline]fn next(&mut self)->Option<Self::Item>{self.iter.next()}}struct Masks{first_block:usize,first_mask:Block,last_block:usize,last_mask:Block,}impl Masks{#[inline]fn new<T:IndexRange>(range:T,length:usize)->Masks{let start=range.start().unwrap_or(0);let end=range.end().unwrap_or(length);assert!(start<=end&&end<=length,"invalid range {}..{} for a fixedbitset of size {}",start,end,length);let(first_block,first_rem)=div_rem(start,BITS);let(last_block,last_rem)=div_rem(end,BITS);Masks{first_block:first_block as usize,first_mask:Block::max_value()<<first_rem,last_block:last_block as usize,last_mask:(Block::max_value()>>1)>>(BITS-last_rem-1),}}}impl Iterator for Masks{type Item=(usize,Block);#[inline]fn next(&mut self)->Option<Self::Item>{match self.first_block.cmp(&self.last_block){Ordering::Less=>{let res=(self.first_block,self.first_mask);self.first_block+=1;self.first_mask=!0;Some(res)}Ordering::Equal=>{let mask=self.first_mask&self.last_mask;let res=if mask==0{None}else{Some((self.first_block,mask))};self.first_block+=1;res}Ordering::Greater=>None,}}}pub struct Ones<'a>{bitset:Block,block_idx:usize,remaining_blocks:&'a[Block],}impl<'a>Iterator for Ones<'a>{type Item=usize;#[inline]fn next(&mut self)->Option<Self::Item>{while self.bitset==0{if self.remaining_blocks.is_empty(){return None;}self.bitset=self.remaining_blocks[0];self.remaining_blocks=&self.remaining_blocks[1..];self.block_idx+=1;}let t=self.bitset&(0 as Block).wrapping_sub(self.bitset);let r=self.bitset.trailing_zeros()as usize;self.bitset^=t;Some(self.block_idx*BITS+r)}}impl Clone for FixedBitSet{#[inline]fn clone(&self)->Self{FixedBitSet{data:self.data.clone(),length:self.length,}}}impl Index<usize>for FixedBitSet{type Output=bool;#[inline]fn index(&self,bit:usize)->&bool{if self.contains(bit){&true}else{&false}}}impl Extend<usize>for FixedBitSet{fn extend<I:IntoIterator<Item=usize>>(&mut self,src:I){let iter=src.into_iter();for i in iter{if i>=self.len(){self.grow(i+1);}self.put(i);}}}impl FromIterator<usize>for FixedBitSet{fn from_iter<I:IntoIterator<Item=usize>>(src:I)->Self{let mut fbs=FixedBitSet::with_capacity(0);fbs.extend(src);fbs}}impl<'a>BitAnd for&'a FixedBitSet{type Output=FixedBitSet;fn bitand(self,other:&FixedBitSet)->FixedBitSet{let(short,long)={if self.len()<=other.len(){(&self.data,&other.data)}else{(&other.data,&self.data)}};let mut data=short.clone();for(data,block)in data.iter_mut().zip(long.iter()){*data&=*block;}let len=std::cmp::min(self.len(),other.len());FixedBitSet{data:data,length:len}}}impl<'a>BitAndAssign for FixedBitSet{fn bitand_assign(&mut self,other:Self){self.intersect_with(&other);}}impl<'a>BitAndAssign<&Self>for FixedBitSet{fn bitand_assign(&mut self,other:&Self){self.intersect_with(other);}}impl<'a>BitOr for&'a FixedBitSet{type Output=FixedBitSet;fn bitor(self,other:&FixedBitSet)->FixedBitSet{let(short,long)={if self.len()<=other.len(){(&self.data,&other.data)}else{(&other.data,&self.data)}};let mut data=long.clone();for(data,block)in data.iter_mut().zip(short.iter()){*data|=*block;}let len=std::cmp::max(self.len(),other.len());FixedBitSet{data:data,length:len}}}impl<'a>BitOrAssign for FixedBitSet{fn bitor_assign(&mut self,other:Self){self.union_with(&other);}}impl<'a>BitOrAssign<&Self>for FixedBitSet{fn bitor_assign(&mut self,other:&Self){self.union_with(other);}}impl<'a>BitXor for&'a FixedBitSet{type Output=FixedBitSet;fn bitxor(self,other:&FixedBitSet)->FixedBitSet{let(short,long)={if self.len()<=other.len(){(&self.data,&other.data)}else{(&other.data,&self.data)}};let mut data=long.clone();for(data,block)in data.iter_mut().zip(short.iter()){*data^=*block;}let len=std::cmp::max(self.len(),other.len());FixedBitSet{data:data,length:len}}}impl<'a>BitXorAssign for FixedBitSet{fn bitxor_assign(&mut self,other:Self){self.symmetric_difference_with(&other);}}impl<'a>BitXorAssign<&Self>for FixedBitSet{fn bitxor_assign(&mut self,other:&Self){self.symmetric_difference_with(other);}}#[test]fn it_works(){const N:usize=50;let mut fb=FixedBitSet::with_capacity(N);for i in 0..(N+10){assert_eq!(fb.contains(i),false);}fb.insert(10);fb.set(11,false);fb.set(12,false);fb.set(12,true);fb.set(N-1,true);assert!(fb.contains(10));assert!(!fb.contains(11));assert!(fb.contains(12));assert!(fb.contains(N-1));for i in 0..N{let contain=i==10||i==12||i==N-1;assert_eq!(contain,fb[i]);}fb.clear();}#[test]fn with_blocks(){let fb=FixedBitSet::with_capacity_and_blocks(50,vec![8u32,0u32]);assert!(fb.contains(3));let ones:Vec<_> =fb.ones().collect();assert_eq!(ones.len(),1);}#[test]fn with_blocks_too_small(){let mut fb=FixedBitSet::with_capacity_and_blocks(500,vec![8u32,0u32]);fb.insert(400);assert!(fb.contains(400));}#[test]fn with_blocks_too_big(){let fb=FixedBitSet::with_capacity_and_blocks(1,vec![8u32]);assert!(!fb.contains(3));}#[test]fn with_blocks_too_big_range_check(){let fb=FixedBitSet::with_capacity_and_blocks(1,vec![0xff]);assert!(fb.contains(0));for i in 1..0xff{assert!(!fb.contains(i));}}#[test]fn grow(){let mut fb=FixedBitSet::with_capacity(48);for i in 0..fb.len(){fb.set(i,true);}let old_len=fb.len();fb.grow(72);for j in 0..fb.len(){assert_eq!(fb.contains(j),j<old_len);}fb.set(64,true);assert!(fb.contains(64));}#[test]fn test_toggle(){let mut fb=FixedBitSet::with_capacity(16);fb.toggle(1);fb.put(2);fb.toggle(2);fb.put(3);assert!(fb.contains(1));assert!(!fb.contains(2));assert!(fb.contains(3));}#[test]fn copy_bit(){let mut fb=FixedBitSet::with_capacity(48);for i in 0..fb.len(){fb.set(i,true);}fb.set(42,false);fb.copy_bit(42,2);assert!(!fb.contains(42));assert!(!fb.contains(2));assert!(fb.contains(1));fb.copy_bit(1,42);assert!(fb.contains(42));fb.copy_bit(1024,42);assert!(!fb[42]);}#[test]fn count_ones(){let mut fb=FixedBitSet::with_capacity(100);fb.set(11,true);fb.set(12,true);fb.set(7,true);fb.set(35,true);fb.set(40,true);fb.set(77,true);fb.set(95,true);fb.set(50,true);fb.set(99,true);assert_eq!(fb.count_ones(..7),0);assert_eq!(fb.count_ones(..8),1);assert_eq!(fb.count_ones(..11),1);assert_eq!(fb.count_ones(..12),2);assert_eq!(fb.count_ones(..13),3);assert_eq!(fb.count_ones(..35),3);assert_eq!(fb.count_ones(..36),4);assert_eq!(fb.count_ones(..40),4);assert_eq!(fb.count_ones(..41),5);assert_eq!(fb.count_ones(50..),4);assert_eq!(fb.count_ones(70..95),1);assert_eq!(fb.count_ones(70..96),2);assert_eq!(fb.count_ones(70..99),2);assert_eq!(fb.count_ones(..),9);assert_eq!(fb.count_ones(0..100),9);assert_eq!(fb.count_ones(0..0),0);assert_eq!(fb.count_ones(100..100),0);assert_eq!(fb.count_ones(7..),9);assert_eq!(fb.count_ones(8..),8);}#[test]fn ones(){let mut fb=FixedBitSet::with_capacity(100);fb.set(11,true);fb.set(12,true);fb.set(7,true);fb.set(35,true);fb.set(40,true);fb.set(77,true);fb.set(95,true);fb.set(50,true);fb.set(99,true);let ones:Vec<_> =fb.ones().collect();assert_eq!(vec![7,11,12,35,40,50,77,95,99],ones);}#[test]fn iter_ones_range(){fn test_range(from:usize,to:usize,capa:usize){assert!(to<=capa);let mut fb=FixedBitSet::with_capacity(capa);for i in from..to{fb.insert(i);}let ones:Vec<_> =fb.ones().collect();let expected:Vec<_> =(from..to).collect();assert_eq!(expected,ones);}for i in 0..100{test_range(i,100,100);test_range(0,i,100);}}#[should_panic]#[test]fn count_ones_oob(){let fb=FixedBitSet::with_capacity(100);fb.count_ones(90..101);}#[should_panic]#[test]fn count_ones_negative_range(){let fb=FixedBitSet::with_capacity(100);fb.count_ones(90..80);}#[test]fn count_ones_panic(){for i in 1..128{let fb=FixedBitSet::with_capacity(i);for j in 0..fb.len()+1{for k in j..fb.len()+1{assert_eq!(fb.count_ones(j..k),0);}}}}#[test]fn default(){let fb=FixedBitSet::default();assert_eq!(fb.len(),0);}#[test]fn insert_range(){let mut fb=FixedBitSet::with_capacity(97);fb.insert_range(..3);fb.insert_range(9..32);fb.insert_range(37..81);fb.insert_range(90..);for i in 0..97{assert_eq!(fb.contains(i),i<3||9<=i&&i<32||37<=i&&i<81||90<=i);}assert!(!fb.contains(97));assert!(!fb.contains(127));assert!(!fb.contains(128));}#[test]fn set_range(){let mut fb=FixedBitSet::with_capacity(48);fb.insert_range(..);fb.set_range(..32,false);fb.set_range(37..,false);fb.set_range(5..9,true);fb.set_range(40..40,true);for i in 0..48{assert_eq!(fb.contains(i),5<=i&&i<9||32<=i&&i<37);}assert!(!fb.contains(48));assert!(!fb.contains(64));}#[test]fn toggle_range(){let mut fb=FixedBitSet::with_capacity(40);fb.insert_range(..10);fb.insert_range(34..38);fb.toggle_range(5..12);fb.toggle_range(30..);for i in 0..40{assert_eq!(fb.contains(i),i<5||10<=i&&i<12||30<=i&&i<34||38<=i);}assert!(!fb.contains(40));assert!(!fb.contains(64));}#[test]fn bitand_equal_lengths(){let len=109;let a_end=59;let b_start=23;let mut a=FixedBitSet::with_capacity(len);let mut b=FixedBitSet::with_capacity(len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a& &b;for i in 0..b_start{assert!(!ab.contains(i));}for i in b_start..a_end{assert!(ab.contains(i));}for i in a_end..len{assert!(!ab.contains(i));}assert_eq!(a.len(),ab.len());}#[test]fn bitand_first_smaller(){let a_len=113;let b_len=137;let len=std::cmp::min(a_len,b_len);let a_end=97;let b_start=89;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a& &b;for i in 0..b_start{assert!(!ab.contains(i));}for i in b_start..a_end{assert!(ab.contains(i));}for i in a_end..len{assert!(!ab.contains(i));}assert_eq!(a.len(),ab.len());}#[test]fn bitand_first_larger(){let a_len=173;let b_len=137;let len=std::cmp::min(a_len,b_len);let a_end=107;let b_start=43;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a& &b;for i in 0..b_start{assert!(!ab.contains(i));}for i in b_start..a_end{assert!(ab.contains(i));}for i in a_end..len{assert!(!ab.contains(i));}assert_eq!(b.len(),ab.len());}#[test]fn intersection(){let len=109;let a_end=59;let b_start=23;let mut a=FixedBitSet::with_capacity(len);let mut b=FixedBitSet::with_capacity(len);a.set_range(..a_end,true);b.set_range(b_start..,true);let mut ab=a.intersection(&b).collect::<FixedBitSet>();for i in 0..b_start{assert!(!ab.contains(i));}for i in b_start..a_end{assert!(ab.contains(i));}for i in a_end..len{assert!(!ab.contains(i));}a.intersect_with(&b);ab.grow(a.len());assert_eq!(ab,a,"intersection and intersect_with produce the same results");}#[test]fn union(){let a_len=173;let b_len=137;let a_start=139;let b_end=107;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(a_start..,true);b.set_range(..b_end,true);let ab=a.union(&b).collect::<FixedBitSet>();for i in a_start..a_len{assert!(ab.contains(i));}for i in 0..b_end{assert!(ab.contains(i));}for i in b_end..a_start{assert!(!ab.contains(i));}a.union_with(&b);assert_eq!(ab,a,"union and union_with produce the same results");}#[test]fn difference(){let a_len=83;let b_len=151;let a_start=0;let a_end=79;let b_start=53;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(a_start..a_end,true);b.set_range(b_start..b_len,true);let mut a_diff_b=a.difference(&b).collect::<FixedBitSet>();for i in a_start..b_start{assert!(a_diff_b.contains(i));}for i in b_start..b_len{assert!(!a_diff_b.contains(i));}a.difference_with(&b);a_diff_b.grow(a.len());assert_eq!(a_diff_b,a,"difference and difference_with produce the same results");}#[test]fn symmetric_difference(){let a_len=83;let b_len=151;let a_start=47;let a_end=79;let b_start=53;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(a_start..a_end,true);b.set_range(b_start..b_len,true);let a_sym_diff_b=a.symmetric_difference(&b).collect::<FixedBitSet>();for i in 0..a_start{assert!(!a_sym_diff_b.contains(i));}for i in a_start..b_start{assert!(a_sym_diff_b.contains(i));}for i in b_start..a_end{assert!(!a_sym_diff_b.contains(i));}for i in a_end..b_len{assert!(a_sym_diff_b.contains(i));}a.symmetric_difference_with(&b);assert_eq!(a_sym_diff_b,a,"symmetric_difference and _with produce the same results");}#[test]fn bitor_equal_lengths(){let len=109;let a_start=17;let a_end=23;let b_start=19;let b_end=59;let mut a=FixedBitSet::with_capacity(len);let mut b=FixedBitSet::with_capacity(len);a.set_range(a_start..a_end,true);b.set_range(b_start..b_end,true);let ab=&a|&b;for i in 0..a_start{assert!(!ab.contains(i));}for i in a_start..b_end{assert!(ab.contains(i));}for i in b_end..len{assert!(!ab.contains(i));}assert_eq!(ab.len(),len);}#[test]fn bitor_first_smaller(){let a_len=113;let b_len=137;let a_end=89;let b_start=97;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a|&b;for i in 0..a_end{assert!(ab.contains(i));}for i in a_end..b_start{assert!(!ab.contains(i));}for i in b_start..b_len{assert!(ab.contains(i));}assert_eq!(b_len,ab.len());}#[test]fn bitor_first_larger(){let a_len=173;let b_len=137;let a_start=139;let b_end=107;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(a_start..,true);b.set_range(..b_end,true);let ab=&a|&b;for i in a_start..a_len{assert!(ab.contains(i));}for i in 0..b_end{assert!(ab.contains(i));}for i in b_end..a_start{assert!(!ab.contains(i));}assert_eq!(a_len,ab.len());}#[test]fn bitxor_equal_lengths(){let len=109;let a_end=59;let b_start=23;let mut a=FixedBitSet::with_capacity(len);let mut b=FixedBitSet::with_capacity(len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a^&b;for i in 0..b_start{assert!(ab.contains(i));}for i in b_start..a_end{assert!(!ab.contains(i));}for i in a_end..len{assert!(ab.contains(i));}assert_eq!(a.len(),ab.len());}#[test]fn bitxor_first_smaller(){let a_len=113;let b_len=137;let len=std::cmp::max(a_len,b_len);let a_end=97;let b_start=89;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a^&b;for i in 0..b_start{assert!(ab.contains(i));}for i in b_start..a_end{assert!(!ab.contains(i));}for i in a_end..len{assert!(ab.contains(i));}assert_eq!(b.len(),ab.len());}#[test]fn bitxor_first_larger(){let a_len=173;let b_len=137;let len=std::cmp::max(a_len,b_len);let a_end=107;let b_start=43;let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.set_range(..a_end,true);b.set_range(b_start..,true);let ab=&a^&b;for i in 0..b_start{assert!(ab.contains(i));}for i in b_start..a_end{assert!(!ab.contains(i));}for i in a_end..b_len{assert!(ab.contains(i));}for i in b_len..len{assert!(!ab.contains(i));}assert_eq!(a.len(),ab.len());}#[test]fn bitand_assign_shorter(){let a_ones:Vec<usize> =vec![2,3,7,19,31,32,37,41,43,47,71,73,101];let b_ones:Vec<usize> =vec![2,7,8,11,23,31,32];let a_and_b:Vec<usize> =vec![2,7,31,32];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();a&=b;let res=a.ones().collect::<Vec<usize>>();assert!(res==a_and_b);}#[test]fn bitand_assign_longer(){let a_ones:Vec<usize> =vec![2,7,8,11,23,31,32];let b_ones:Vec<usize> =vec![2,3,7,19,31,32,37,41,43,47,71,73,101];let a_and_b:Vec<usize> =vec![2,7,31,32];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();a&=b;let res=a.ones().collect::<Vec<usize>>();assert!(res==a_and_b);}#[test]fn bitor_assign_shorter(){let a_ones:Vec<usize> =vec![2,3,7,19,31,32,37,41,43,47,71,73,101];let b_ones:Vec<usize> =vec![2,7,8,11,23,31,32];let a_or_b:Vec<usize> =vec![2,3,7,8,11,19,23,31,32,37,41,43,47,71,73,101];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();a|=b;let res=a.ones().collect::<Vec<usize>>();assert!(res==a_or_b);}#[test]fn bitor_assign_longer(){let a_ones:Vec<usize> =vec![2,7,8,11,23,31,32];let b_ones:Vec<usize> =vec![2,3,7,19,31,32,37,41,43,47,71,73,101];let a_or_b:Vec<usize> =vec![2,3,7,8,11,19,23,31,32,37,41,43,47,71,73,101];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();a|=b;let res=a.ones().collect::<Vec<usize>>();assert!(res==a_or_b);}#[test]fn bitxor_assign_shorter(){let a_ones:Vec<usize> =vec![2,3,7,19,31,32,37,41,43,47,71,73,101];let b_ones:Vec<usize> =vec![2,7,8,11,23,31,32];let a_xor_b:Vec<usize> =vec![3,8,11,19,23,37,41,43,47,71,73,101];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();a^=b;let res=a.ones().collect::<Vec<usize>>();assert!(res==a_xor_b);}#[test]fn bitxor_assign_longer(){let a_ones:Vec<usize> =vec![2,7,8,11,23,31,32];let b_ones:Vec<usize> =vec![2,3,7,19,31,32,37,41,43,47,71,73,101];let a_xor_b:Vec<usize> =vec![3,8,11,19,23,37,41,43,47,71,73,101];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();a^=b;let res=a.ones().collect::<Vec<usize>>();assert!(res==a_xor_b);}#[test]fn op_assign_ref(){let mut a=FixedBitSet::with_capacity(8);let b=FixedBitSet::with_capacity(8);a&=&b;a|=&b;a^=&b;}#[test]fn subset_superset_shorter(){let a_ones:Vec<usize> =vec![7,31,32,63];let b_ones:Vec<usize> =vec![2,7,19,31,32,37,41,43,47,63,73,101];let mut a=a_ones.iter().cloned().collect::<FixedBitSet>();let b=b_ones.iter().cloned().collect::<FixedBitSet>();assert!(a.is_subset(&b)&&b.is_superset(&a));a.insert(14);assert!(!a.is_subset(&b)&&!b.is_superset(&a));}#[test]fn subset_superset_longer(){let a_len=153;let b_len=75;let a_ones:Vec<usize> =vec![7,31,32,63];let b_ones:Vec<usize> =vec![2,7,19,31,32,37,41,43,47,63,73];let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.extend(a_ones.iter().cloned());b.extend(b_ones.iter().cloned());assert!(a.is_subset(&b)&&b.is_superset(&a));a.insert(100);assert!(!a.is_subset(&b)&&!b.is_superset(&a));}#[test]fn is_disjoint_first_shorter(){let a_len=75;let b_len=153;let a_ones:Vec<usize> =vec![2,19,32,37,41,43,47,73];let b_ones:Vec<usize> =vec![7,23,31,63,124];let mut a=FixedBitSet::with_capacity(a_len);let mut b=FixedBitSet::with_capacity(b_len);a.extend(a_ones.iter().cloned());b.extend(b_ones.iter().cloned());assert!(a.is_disjoint(&b));a.insert(63);assert!(!a.is_disjoint(&b));}#[test]fn is_disjoint_first_longer(){let a_ones:Vec<usize> =vec![2,19,32,37,41,43,47,73,101];let b_ones:Vec<usize> =vec![7,23,31,63];let a=a_ones.iter().cloned().collect::<FixedBitSet>();let mut b=b_ones.iter().cloned().collect::<FixedBitSet>();assert!(a.is_disjoint(&b));b.insert(2);assert!(!a.is_disjoint(&b));}#[test]fn extend_on_empty(){let items:Vec<usize> =vec![2,3,5,7,11,13,17,19,23,27,29,31,37,167];let mut fbs=FixedBitSet::with_capacity(0);fbs.extend(items.iter().cloned());let ones=fbs.ones().collect::<Vec<usize>>();assert!(ones==items);}#[test]fn extend(){let items:Vec<usize> =vec![2,3,5,7,11,13,17,19,23,27,29,31,37,167];let mut fbs=FixedBitSet::with_capacity(168);let new:Vec<usize> =vec![7,37,67,137];for i in&new{fbs.put(*i);}fbs.extend(items.iter().cloned());let ones=fbs.ones().collect::<Vec<usize>>();let expected={let mut tmp=items.clone();tmp.extend(new);tmp.sort();tmp.dedup();tmp};assert!(ones==expected);}#[test]fn from_iterator(){let items:Vec<usize> =vec![0,2,4,6,8];let fb=items.iter().cloned().collect::<FixedBitSet>();for i in items{assert!(fb.contains(i));}for i in vec![1,3,5,7]{assert!(!fb.contains(i));}assert_eq!(fb.len(),9);}#[test]fn from_iterator_ones(){let len=257;let mut fb=FixedBitSet::with_capacity(len);for i in(0..len).filter(|i|i%7==0){fb.put(i);}fb.put(len-1);let dup=fb.ones().collect::<FixedBitSet>();assert_eq!(fb.len(),dup.len());assert_eq!(fb.ones().collect::<Vec<usize>>(),dup.ones().collect::<Vec<usize>>());}#[test]fn binary_trait(){let items:Vec<usize> =vec![1,5,7,10,14,15];let fb=items.iter().cloned().collect::<FixedBitSet>();assert_eq!(format!("{:b}",fb),"0100010100100011");assert_eq!(format!("{:#b}",fb),"0b0100010100100011");}#[test]fn display_trait(){let len=8;let mut fb=FixedBitSet::with_capacity(len);fb.put(4);fb.put(2);assert_eq!(format!("{}",fb),"00101000");assert_eq!(format!("{:#}",fb),"0b00101000");}}
pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T>{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T>{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R>>Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Self::Output;}impl<T:FromStr>Readable for T where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::__Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input. ","This is a bug in `proconio`. ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));lock.is_empty()}}
}
pub(crate) mod macros {
pub mod fixedbitset {}
pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};}
pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};}
mod preludes {
pub mod fixedbitset {}
pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;}
pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__lazy_static_1_4_0 as lazy_static;}
}
}