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;}
    }
}