#![allow(unused_imports)]
use input2::*;
use std::{
    collections::*,
    io::{self, BufWriter, Read, Write},
};
fn run<I: Read, O: Write>(mut ss: Input<I>, mut out: O) {
    let t: u32 = 1;
    for _ in 0..t {
        case(&mut ss, &mut out);
    }
}
fn case<I: Read, O: Write>(ss: &mut Input<I>, mut out: O) {
    use modint2::*;
    let (n, m): (usize, usize) = ss.input();
    let mut dsu =
        dsu::DsuMerge::from_iterator(ss.seq(n).map(|x: u32| mint::<998244353>(x)), |x, y| *x += y);
    for (u, v) in ss.seq::<(usize, usize)>(m) {
        let (u, v) = (u - 1, v - 1);
        dsu.unite(u, v);
    }
    let mut ans = mint(1);
    for i in 0..n {
        if dsu.is_root(i) {
            ans *= dsu.data(i).pow(dsu.size(i));
        }
    }
    wln!(out, "{ans}")
}
fn main() {
    let stdin = io::stdin();
    let ss = Input::new(stdin.lock());
    let stdout = io::stdout();
    let out = BufWriter::new(stdout.lock());
    run(ss, out);
}
pub mod dsu {
    #[derive(Clone)]
    pub struct Dsu(Vec<isize>);
    impl Dsu {
        pub fn new(n: usize) -> Self {
            Self(vec![-1; n])
        }
        pub fn root(&self, mut u: usize) -> usize {
            while self.0[u] >= 0 {
                u = self.0[u] as usize;
            }
            u
        }
        pub fn is_root(&self, u: usize) -> bool {
            self.0[u] < 0
        }
        pub fn unite(&mut self, u: usize, v: usize) -> UniteResult {
            let ru = self.root(u);
            let rv = self.root(v);
            if ru == rv {
                return UniteResult {
                    root: ru,
                    united_root: None,
                    size: -self.0[ru] as _,
                };
            }
            let (r, c) = if -self.0[ru] >= -self.0[rv] {
                (ru, rv)
            } else {
                (rv, ru)
            };
            self.0[r] += self.0[c];
            self.0[c] = r as isize;
            UniteResult {
                root: r,
                united_root: Some(c),
                size: -self.0[r] as _,
            }
        }
        pub fn is_same(&self, u: usize, v: usize) -> bool {
            self.root(u) == self.root(v)
        }
        pub fn size(&self, u: usize) -> usize {
            -self.0[self.root(u)] as usize
        }
        pub fn reset(&mut self) {
            todo!();
        }
    }
    #[derive(Clone, Copy, PartialEq, Eq, Debug)]
    pub struct UniteResult {
        pub root: usize,
        pub united_root: Option<usize>,
        pub size: usize,
    }
    impl UniteResult {
        pub fn is_united(&self) -> bool {
            self.united_root.is_some()
        }
    }
    use std::mem::ManuallyDrop;
    pub struct DsuMerge<T, F> {
        inner: Dsu,
        data: Vec<ManuallyDrop<T>>,
        merge: F,
    }
    impl<T, F: FnMut(&mut T, T)> DsuMerge<T, F> {
        pub fn new(n: usize, init: T, merge: F) -> Self
        where
            T: Clone,
        {
            Self::from_iterator((0..n).map(|_| init.clone()), merge)
        }
        pub fn from_fn(n: usize, init: impl FnMut(usize) -> T, merge: F) -> Self {
            Self::from_iterator((0..n).map(init), merge)
        }
        pub fn from_iterator(iter: impl IntoIterator<Item = T>, merge: F) -> Self {
            let data: Vec<_> = iter.into_iter().map(|x| ManuallyDrop::new(x)).collect();
            Self {
                inner: Dsu::new(data.len()),
                data,
                merge,
            }
        }
        pub fn root(&self, u: usize) -> usize {
            self.inner.root(u)
        }
        pub fn is_root(&self, u: usize) -> bool {
            self.inner.is_root(u)
        }
        pub fn unite(&mut self, u: usize, v: usize) -> (UniteResult, &mut T) {
            let res = self.inner.unite(u, v);
            if let Some(c) = res.united_root {
                let taken = unsafe { ManuallyDrop::take(&mut self.data[c]) };
                (self.merge)(&mut self.data[res.root], taken);
            }
            (res, &mut self.data[res.root])
        }
        pub fn is_same(&self, u: usize, v: usize) -> bool {
            self.inner.is_same(u, v)
        }
        pub fn size(&self, u: usize) -> usize {
            self.inner.size(u)
        }
        pub fn data(&self, u: usize) -> &T {
            &self.data[self.root(u)]
        }
        pub fn data_mut(&mut self, u: usize) -> &mut T {
            &mut self.data[self.inner.root(u)]
        }
    }
    impl<T, F> Drop for DsuMerge<T, F> {
        fn drop(&mut self) {
            if std::mem::needs_drop::<T>() {
                for (u, data) in self.data.iter_mut().enumerate() {
                    if self.inner.is_root(u) {
                        unsafe {
                            ManuallyDrop::drop(data);
                        }
                    }
                }
            }
        }
    }
}
pub mod modint2 {
    use std::{
        cell::{Cell, UnsafeCell},
        cmp, fmt,
        hash::Hash,
        iter,
        marker::PhantomData,
        ops,
    };
    #[inline]
    pub fn mint<const M: u32>(value: impl Into<ModInt<ConstMod<M>>>) -> ModInt<ConstMod<M>> {
        value.into()
    }
    #[inline]
    pub fn var_mint(value: impl Into<ModInt<VarMod>>) -> ModInt<VarMod> {
        value.into()
    }
    pub type Mint<const N: u32> = ModInt<ConstMod<N>>;
    pub type VarMint = ModInt<VarMod>;
    pub trait Modulo {
        fn modulo() -> u32;
        #[inline]
        fn rem32(x: u32) -> u32 {
            x % Self::modulo()
        }
        #[inline]
        fn rem64(x: u64) -> u32 {
            (x % Self::modulo() as u64) as u32
        }
    }
    pub struct ConstMod<const M: u32>;
    impl<const M: u32> Modulo for ConstMod<M> {
        #[inline]
        fn modulo() -> u32 {
            M
        }
    }
    #[inline]
    pub fn set_var_mod(m: u32) {
        BarrettReduction::new(m).store_thread();
    }
    pub struct VarMod;
    impl Modulo for VarMod {
        #[inline]
        fn modulo() -> u32 {
            BarrettReduction::load_thread().m
        }
        #[inline]
        fn rem32(x: u32) -> u32 {
            Self::rem64(x as u64) as u32
        }
        #[inline]
        fn rem64(x: u64) -> u32 {
            BarrettReduction::load_thread().rem(x)
        }
    }
    #[derive(Clone, Copy, Debug)]
    struct BarrettReduction {
        m: u32,
        e: u32,
        s: u64,
    }
    impl BarrettReduction {
        #[inline]
        pub fn new(m: u32) -> Self {
            assert_ne!(m, 0);
            assert_ne!(m, 1);
            let e = 31 - (m - 1).leading_zeros();
            Self {
                s: ((1u128 << (64 + e)) / m as u128) as u64 + (!m.is_power_of_two()) as u64,
                m,
                e,
            }
        }
        #[inline]
        pub fn div(&self, x: u64) -> u64 {
            ((self.s as u128 * x as u128) >> 64) as u64 >> self.e
        }
        #[inline]
        pub fn rem(&self, x: u64) -> u32 {
            (x - self.m as u64 * self.div(x)) as u32
        }
        #[inline]
        pub fn store_thread(self) {
            BR.with(|br| br.set(self));
        }
        #[inline]
        pub fn load_thread() -> Self {
            BR.with(|br| br.get())
        }
    }
    thread_local! { static BR : Cell < BarrettReduction > = Cell :: new (BarrettReduction { m : 0 , s : 0 , e : 0 }) ; }
    #[repr(transparent)]
    pub struct ModInt<M> {
        value: u32,
        marker: PhantomData<M>,
    }
    impl<M> ModInt<M> {
        pub const ZERO: Self = Self::unnormalized(0);
        #[inline]
        pub const fn unnormalized(value: u32) -> Self {
            Self {
                value,
                marker: PhantomData,
            }
        }
        #[inline]
        pub const fn get(self) -> u32 {
            self.value
        }
    }
    impl<M: Modulo> ModInt<M> {
        #[inline]
        pub fn new(value: u32) -> Self {
            Self::unnormalized(M::rem32(value))
        }
        #[inline]
        pub fn normalize(self) -> Self {
            Self::new(self.value)
        }
        #[inline]
        pub fn modulo() -> u32 {
            M::modulo()
        }
        #[inline]
        pub fn set<T: Into<ModInt<M>>>(&mut self, value: T) {
            *self = value.into();
        }
        #[inline]
        pub fn inv(self) -> Self {
            self.pow(M::modulo() - 2)
        }
    }
    impl<M: Modulo> ops::Neg for ModInt<M> {
        type Output = Self;
        #[inline]
        fn neg(self) -> Self::Output {
            Self::unnormalized(if self.value == 0 {
                0
            } else {
                M::modulo() - self.value
            })
        }
    }
    impl<M: Modulo> ops::Neg for &ModInt<M> {
        type Output = ModInt<M>;
        #[inline]
        fn neg(self) -> Self::Output {
            -(*self)
        }
    }
    impl<M: Modulo> ops::Add for ModInt<M> {
        type Output = Self;
        #[inline]
        fn add(self, other: Self) -> Self {
            let sum = self.value + other.value;
            Self::unnormalized(if sum < M::modulo() {
                sum
            } else {
                sum - M::modulo()
            })
        }
    }
    impl<M: Modulo> ops::Sub for ModInt<M> {
        type Output = Self;
        #[inline]
        fn sub(self, other: Self) -> Self {
            let (diff, of) = self.value.overflowing_sub(other.value);
            Self::unnormalized(if of {
                diff.wrapping_add(M::modulo())
            } else {
                diff
            })
        }
    }
    impl<M: Modulo> ops::Mul for ModInt<M> {
        type Output = Self;
        #[inline]
        fn mul(self, other: Self) -> Self {
            Self::unnormalized(M::rem64(self.value as u64 * other.value as u64))
        }
    }
    impl<M: Modulo> ops::Div for ModInt<M> {
        type Output = Self;
        #[inline]
        fn div(self, other: Self) -> Self {
            self * other.inv()
        }
    }
    macro_rules! binop {
        ($ Op : ident , $ op : ident , $ OpAssign : ident , $ op_assign : ident) => {
            impl<M: Modulo> ops::$Op<&ModInt<M>> for ModInt<M> {
                type Output = Self;
                #[inline]
                fn $op(self, other: &ModInt<M>) -> Self::Output {
                    self.$op(*other)
                }
            }
            impl<M: Modulo> ops::$Op<ModInt<M>> for &ModInt<M> {
                type Output = ModInt<M>;
                #[inline]
                fn $op(self, other: ModInt<M>) -> Self::Output {
                    (*self).$op(other)
                }
            }
            impl<M: Modulo> ops::$Op for &ModInt<M> {
                type Output = ModInt<M>;
                #[inline]
                fn $op(self, other: Self) -> Self::Output {
                    (*self).$op(*other)
                }
            }
            impl<M: Modulo> ops::$OpAssign for ModInt<M> {
                #[inline]
                fn $op_assign(&mut self, rhs: Self) {
                    *self = <Self as ops::$Op>::$op(*self, rhs);
                }
            }
            impl<M: Modulo> ops::$OpAssign<&ModInt<M>> for ModInt<M> {
                #[inline]
                fn $op_assign(&mut self, rhs: &ModInt<M>) {
                    *self = <Self as ops::$Op>::$op(*self, *rhs);
                }
            }
        };
    }
    binop!(Add, add, AddAssign, add_assign);
    binop!(Sub, sub, SubAssign, sub_assign);
    binop!(Mul, mul, MulAssign, mul_assign);
    binop!(Div, div, DivAssign, div_assign);
    impl<M: Modulo> iter::Sum for ModInt<M> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            let sum = iter.fold(0u64, |acc, x| acc + x.get() as u64);
            Self::from(sum)
        }
    }
    impl<M: Modulo> iter::Product for ModInt<M> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(ModInt::new(1), |x, y| x * y)
        }
    }
    macro_rules! fold {
        ($ Trait : ident , $ f : ident) => {
            impl<'a, M: Modulo + 'a> iter::$Trait<&'a ModInt<M>> for ModInt<M> {
                fn $f<I: Iterator<Item = &'a ModInt<M>>>(iter: I) -> Self {
                    <Self as iter::$Trait>::$f(iter.copied())
                }
            }
        };
    }
    fold!(Sum, sum);
    fold!(Product, product);
    pub trait Pow<Exp> {
        fn pow(self, exp: Exp) -> Self;
    }
    macro_rules! pow {
        ($ Uint : ident , $ Int : ident) => {
            impl<M: Modulo> Pow<$Uint> for ModInt<M> {
                #[inline]
                fn pow(self, mut exp: $Uint) -> Self {
                    let mut res = Self::unnormalized(1);
                    if exp == 0 {
                        return res;
                    }
                    let mut base = self;
                    while exp > 1 {
                        if exp & 1 == 1 {
                            res *= base;
                        }
                        base *= base;
                        exp >>= 1;
                    }
                    res * base
                }
            }
            impl<M: Modulo> Pow<$Int> for ModInt<M> {
                #[inline]
                fn pow(self, exp: $Int) -> Self {
                    let p = self.pow(exp.abs() as $Uint);
                    if exp >= 0 {
                        p
                    } else {
                        p.inv()
                    }
                }
            }
        };
    }
    pow!(usize, isize);
    pow!(u8, i8);
    pow!(u16, i16);
    pow!(u32, i32);
    pow!(u64, i64);
    pow!(u128, i128);
    impl<M> Clone for ModInt<M> {
        fn clone(&self) -> Self {
            *self
        }
    }
    impl<M> Copy for ModInt<M> {}
    impl<M> Default for ModInt<M> {
        fn default() -> Self {
            Self::ZERO
        }
    }
    impl<M> PartialEq for ModInt<M> {
        fn eq(&self, other: &Self) -> bool {
            self.value == other.value
        }
    }
    impl<M> Eq for ModInt<M> {}
    impl<M> PartialOrd for ModInt<M> {
        fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
            self.value.partial_cmp(&other.value)
        }
    }
    impl<M> Ord for ModInt<M> {
        fn cmp(&self, other: &Self) -> cmp::Ordering {
            self.value.cmp(&other.value)
        }
    }
    impl<M> Hash for ModInt<M> {
        fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
            self.value.hash(state)
        }
    }
    impl<M> fmt::Display for ModInt<M> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            fmt::Display::fmt(&self.value, f)
        }
    }
    impl<M> fmt::Debug for ModInt<M> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            fmt::Debug::fmt(&self.value, f)
        }
    }
    impl<M: Modulo> From<u32> for ModInt<M> {
        fn from(value: u32) -> Self {
            Self::new(value)
        }
    }
    impl<M: Modulo> From<u64> for ModInt<M> {
        fn from(value: u64) -> Self {
            Self::unnormalized(M::rem64(value))
        }
    }
    impl<M: Modulo> From<u128> for ModInt<M> {
        fn from(value: u128) -> Self {
            Self::unnormalized((value % M::modulo() as u128) as u32)
        }
    }
    macro_rules! from_small_uint {
        ($ ty : ident) => {
            impl<M: Modulo> From<$ty> for ModInt<M> {
                fn from(value: $ty) -> Self {
                    Self::new(value as u32)
                }
            }
        };
    }
    from_small_uint!(u8);
    from_small_uint!(u16);
    impl<M: Modulo> From<usize> for ModInt<M> {
        fn from(value: usize) -> Self {
            if cfg!(target_pointer_width = "64") {
                ModInt::from(value as u64)
            } else {
                ModInt::from(value as u32)
            }
        }
    }
    macro_rules! from_signed {
        ($ Uint : ident , $ Int : ident) => {
            impl<M: Modulo> From<$Int> for ModInt<M> {
                fn from(value: $Int) -> Self {
                    let abs = ModInt::from(value.abs() as $Uint);
                    if value >= 0 {
                        abs
                    } else {
                        -abs
                    }
                }
            }
        };
    }
    from_signed!(usize, isize);
    from_signed!(u8, i8);
    from_signed!(u16, i16);
    from_signed!(u32, i32);
    from_signed!(u64, i64);
    from_signed!(u128, i128);
    pub struct Fact<M>(UnsafeCell<FactInner<M>>);
    impl<M: Modulo> Fact<M> {
        #[inline]
        pub fn new() -> Self {
            Self(UnsafeCell::new(FactInner {
                fact: vec![],
                fact_inv: vec![],
            }))
        }
        #[inline]
        pub fn fact(&self, n: usize) -> ModInt<M> {
            unsafe { (*self.0.get()).fact(n) }
        }
        #[inline]
        pub fn fact_inv(&self, n: usize) -> ModInt<M> {
            unsafe { (*self.0.get()).fact_inv(n) }
        }
        #[inline]
        pub fn binom(&self, n: usize, k: usize) -> ModInt<M> {
            if n >= k {
                self.fact(n) * self.fact_inv(n - k) * self.fact_inv(k)
            } else {
                ModInt::unnormalized(0)
            }
        }
        #[inline]
        pub fn perm(&self, n: usize, k: usize) -> ModInt<M> {
            if n >= k {
                self.fact(n) * self.fact_inv(n - k)
            } else {
                ModInt::unnormalized(0)
            }
        }
        #[inline]
        pub fn catalan(&self, n: usize) -> ModInt<M> {
            self.fact(2 * n) * self.fact_inv(n + 1) * self.fact_inv(n)
        }
    }
    struct FactInner<M> {
        fact: Vec<ModInt<M>>,
        fact_inv: Vec<ModInt<M>>,
    }
    impl<M: Modulo> FactInner<M> {
        #[inline]
        fn fact(&mut self, n: usize) -> ModInt<M> {
            if let Some(&val) = self.fact.get(n) {
                val
            } else {
                self.grow_fact(n)
            }
        }
        fn grow_fact(&mut self, n: usize) -> ModInt<M> {
            self.fact.reserve(n + 1 - self.fact.len());
            if self.fact.is_empty() {
                self.fact.push(ModInt::new(1));
            }
            unsafe {
                let ptr = self.fact.as_mut_ptr();
                let mut val = *ptr.add(self.fact.len() - 1);
                for i in self.fact.len()..=n {
                    val *= ModInt::new(i as u32);
                    *ptr.add(i) = val;
                }
                self.fact.set_len(n + 1);
                val
            }
        }
        #[inline]
        fn fact_inv(&mut self, n: usize) -> ModInt<M> {
            if let Some(&val) = self.fact_inv.get(n) {
                val
            } else {
                self.grow_fact_inv(n)
            }
        }
        fn grow_fact_inv(&mut self, n: usize) -> ModInt<M> {
            self.fact(n);
            self.fact_inv.reserve(n + 1 - self.fact_inv.len());
            unsafe {
                let res = self.fact[n].inv();
                let mut val = res;
                let ptr = self.fact_inv.as_mut_ptr();
                *ptr.add(n) = val;
                for i in (self.fact.len()..n).rev() {
                    val *= ModInt::new(i as u32 + 1);
                    *ptr.add(i) = val;
                }
                self.fact_inv.set_len(n + 1);
                res
            }
        }
    }
}
pub mod input2 {
    use std::{
        convert::TryInto,
        io::{self, Read},
        marker::PhantomData,
        mem::{self, MaybeUninit},
        ptr, slice,
    };
    pub struct Input<R> {
        src: R,
        buf: Vec<u8>,
        pos: usize,
        len: usize,
    }
    macro_rules! def_input {
        ($ ty : ident) => {
            pub fn $ty(&mut self) -> $ty {
                self.input()
            }
        };
    }
    impl<R: Read> Input<R> {
        pub fn new(src: R) -> Self {
            Self::with_capacity(src, 1 << 20)
        }
        pub fn with_capacity(src: R, cap: usize) -> Self {
            Self {
                src,
                buf: vec![0; cap],
                pos: 0,
                len: 0,
            }
        }
        pub fn input<T: Parse>(&mut self) -> T {
            T::parse(self)
        }
        pub fn seq<T: Parse>(&mut self, n: usize) -> Seq<T, R> {
            Seq {
                src: self,
                n,
                marker: PhantomData,
            }
        }
        pub fn vec<T: Parse>(&mut self, n: usize) -> Vec<T> {
            self.seq(n).collect()
        }
        pub fn str(&mut self) -> &str {
            std::str::from_utf8(self.bytes()).expect("utf8 error")
        }
        pub fn bytes(&mut self) -> &[u8] {
            let range = self.bytes_inner();
            unsafe { self.buf.get_unchecked(range) }
        }
        pub fn bytes_vec(&mut self) -> Vec<u8> {
            let range = self.bytes_inner();
            if range.start == 0 && 2 * range.end >= self.buf.len() {
                let buf_len = self.buf.len();
                let mut new_buf = vec![0; buf_len];
                new_buf[..self.len].copy_from_slice(self.remaining());
                let mut res = mem::replace(&mut self.buf, new_buf);
                self.pos = 0;
                res.truncate(range.end);
                res
            } else {
                self.buf[range].to_vec()
            }
        }
        #[inline]
        fn bytes_inner(&mut self) -> std::ops::Range<usize> {
            let mut i = 0;
            loop {
                if self.len > 0 {
                    if let Some(d) = find_ws(unsafe {
                        self.buf.get_unchecked(self.pos + i..self.pos + self.len)
                    }) {
                        let del = i + d;
                        let range = self.pos..self.pos + del;
                        self.pos += del + 1;
                        self.len -= del + 1;
                        if del == 0 {
                            continue;
                        }
                        return range;
                    }
                    i = self.len;
                }
                if self.read() == 0 {
                    let range = self.pos..self.pos + self.len;
                    self.pos = 0;
                    self.len = 0;
                    return range;
                }
            }
        }
        #[cold]
        fn read(&mut self) -> usize {
            if self.pos != 0 {
                self.buf.copy_within(self.pos..self.pos + self.len, 0);
                self.pos = 0;
            }
            if self.len == self.buf.len() {
                self.buf.resize((2 * self.buf.len()).max(1 << 13), 0);
            }
            loop {
                match self
                    .src
                    .read(unsafe { self.buf.get_unchecked_mut(self.len..) })
                {
                    Ok(n) => {
                        self.len += n;
                        return n;
                    }
                    Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}
                    Err(e) => panic!("io error: {}", e),
                }
            }
        }
        #[inline]
        fn remaining(&self) -> &[u8] {
            unsafe { self.buf.get_unchecked(self.pos..self.pos + self.len) }
        }
        def_input!(usize);
        def_input!(u8);
        def_input!(u16);
        def_input!(u32);
        def_input!(u64);
        def_input!(isize);
        def_input!(i8);
        def_input!(i16);
        def_input!(i32);
        def_input!(i64);
        def_input!(f32);
        def_input!(f64);
    }
    #[inline]
    pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> {
        for (i, c) in s.iter().enumerate() {
            if *c <= b' ' {
                return Some(i);
            }
        }
        None
    }
    const CHUNK_SIZE: usize = mem::size_of::<usize>();
    #[inline]
    pub(crate) fn find_ws(s: &[u8]) -> Option<usize> {
        let offset = (32 + s.as_ptr().align_offset(CHUNK_SIZE)).min(s.len());
        let mut i = 0;
        while i < offset {
            if s[i] <= b' ' {
                return Some(i);
            }
            i += 1;
        }
        if i < s.len() {
            find_ws_long(s, i)
        } else {
            None
        }
    }
    fn find_ws_long(s: &[u8], mut i: usize) -> Option<usize> {
        while i + CHUNK_SIZE <= s.len() {
            if let Some(j) = find_ws_usize(usize::from_le_bytes(
                unsafe { s.get_unchecked(i..i + CHUNK_SIZE) }
                    .try_into()
                    .unwrap(),
            )) {
                return Some(i + j);
            }
            i += CHUNK_SIZE;
        }
        while i < s.len() {
            if s[i] <= b' ' {
                return Some(i);
            }
            i += 1;
        }
        None
    }
    #[inline]
    fn find_ws_usize(s: usize) -> Option<usize> {
        const SUB: usize = 0x2121212121212121;
        const MASK: usize = 0x8080808080808080;
        let t = s.wrapping_sub(SUB) & MASK;
        (t != 0).then(|| (t.trailing_zeros() / 8) as usize)
    }
    pub struct Seq<'a, T, R> {
        src: &'a mut Input<R>,
        n: usize,
        marker: PhantomData<*const T>,
    }
    impl<'a, T: Parse, R: Read> Iterator for Seq<'a, T, R> {
        type Item = T;
        fn next(&mut self) -> Option<Self::Item> {
            if self.n > 0 {
                self.n -= 1;
                Some(self.src.input())
            } else {
                None
            }
        }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.n, Some(self.n))
        }
    }
    impl<'a, T: Parse, R: Read> ExactSizeIterator for Seq<'a, T, R> {
        fn len(&self) -> usize {
            self.size_hint().0
        }
    }
    pub trait Parse {
        fn parse<T: Read>(src: &mut Input<T>) -> Self;
    }
    impl Parse for Vec<u8> {
        fn parse<T: Read>(src: &mut Input<T>) -> Self {
            src.bytes_vec()
        }
    }
    impl Parse for String {
        fn parse<T: Read>(src: &mut Input<T>) -> Self {
            String::from_utf8(src.bytes_vec()).unwrap()
        }
    }
    pub trait ParseBytes {
        fn parse_bytes(s: &[u8]) -> Self;
    }
    macro_rules! parse_int {
        ($ ty : ident , $ ity : ident) => {
            impl ParseBytes for $ty {
                fn parse_bytes(s: &[u8]) -> Self {
                    $ty(s, 0)
                }
            }
            impl ParseBytes for $ity {
                fn parse_bytes(s: &[u8]) -> Self {
                    let (minus, s) = if let Some((b'-', s)) = s.split_first() {
                        (true, s)
                    } else {
                        (false, s)
                    };
                    let x = $ty(s, 0);
                    (if minus { (!x).wrapping_add(1) } else { x }) as $ity
                }
            }
        };
    }
    parse_int!(usize, isize);
    parse_int!(u8, i8);
    parse_int!(u16, i16);
    parse_int!(u32, i32);
    parse_int!(u64, i64);
    macro_rules! parse {
        ($ ty : ident) => {
            impl Parse for $ty {
                fn parse<T: Read>(src: &mut Input<T>) -> Self {
                    Self::parse_bytes(src.bytes())
                }
            }
        };
    }
    parse!(usize);
    parse!(u8);
    parse!(u16);
    parse!(u32);
    parse!(u64);
    parse!(isize);
    parse!(i8);
    parse!(i16);
    parse!(i32);
    parse!(i64);
    parse!(f32);
    parse!(f64);
    macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T : Parse) ,+> Parse for ($ ($ T ,) +) { fn parse < T : Read > (src : & mut Input < T >) -> Self { ($ ($ T :: parse (src) ,) +) } } } ; }
    tuple!(A);
    tuple!(A, B);
    tuple!(A, B, C);
    tuple!(A, B, C, D);
    tuple!(A, B, C, D, E);
    tuple!(A, B, C, D, E, F);
    tuple!(A, B, C, D, E, F, G);
    tuple!(A, B, C, D, E, F, G, H);
    impl<T: Parse, const N: usize> Parse for [T; N] {
        fn parse<R: Read>(src: &mut Input<R>) -> Self {
            struct Guard<T> {
                ptr: *mut T,
                i: usize,
            }
            impl<T> Drop for Guard<T> {
                fn drop(&mut self) {
                    unsafe {
                        ptr::drop_in_place(slice::from_raw_parts_mut(self.ptr, self.i));
                    }
                }
            }
            let mut res: MaybeUninit<[T; N]> = MaybeUninit::uninit();
            let mut g = Guard {
                ptr: res.as_mut_ptr() as *mut T,
                i: 0,
            };
            unsafe {
                while g.i < N {
                    g.ptr.add(g.i).write(src.input());
                    g.i += 1;
                }
                mem::forget(g);
                res.assume_init()
            }
        }
    }
    #[inline]
    fn toi8bytes(s: &[u8]) -> (u32, &[u8]) {
        let (p, rest) = s.split_at(8);
        let x = u64::from_le_bytes(p.try_into().unwrap());
        const MASK1: u64 = 0x000f000f000f000f;
        let hi = (x >> 8) & MASK1;
        let lo = x & MASK1;
        let x = 10 * lo + hi;
        const MASK2: u64 = 0x0000ffff0000ffff;
        let hi = (x >> 16) & MASK2;
        let lo = x & MASK2;
        let x = 100 * lo + hi;
        let hi = (x >> 32) as u32;
        let lo = x as u32;
        let x = 10000 * lo + hi;
        (x, rest)
    }
    #[inline]
    fn toi4bytes(s: &[u8]) -> (u32, &[u8]) {
        let (p, rest) = s.split_at(4);
        let x = u32::from_le_bytes(p.try_into().unwrap());
        const MASK: u32 = 0x000f000f;
        let hi = (x >> 8) & MASK;
        let lo = x & MASK;
        let x = 10 * lo + hi;
        let hi = x >> 16;
        let lo = x & 0x0000ffff;
        let x = 100 * lo + hi;
        (x, rest)
    }
    #[cfg(target_pointer_width = "32")]
    fn usize(s: &[u8], pre: usize) -> usize {
        u32(s, pre as u32) as usize
    }
    #[cfg(target_pointer_width = "64")]
    fn usize(s: &[u8], pre: usize) -> usize {
        u64(s, pre as u64) as usize
    }
    #[inline]
    fn u64(mut s: &[u8], pre: u64) -> u64 {
        let mut res = pre;
        while s.len() >= 8 {
            let (x, rest) = toi8bytes(s);
            res = 100000000 * res + x as u64;
            s = rest;
        }
        if s.len() >= 4 {
            let (x, rest) = toi4bytes(s);
            res = 10000 * res + x as u64;
            s = rest;
        }
        for &c in s {
            res = 10 * res + (c & 0xf) as u64;
        }
        res
    }
    #[inline]
    fn u32(mut s: &[u8], pre: u32) -> u32 {
        let mut res = pre;
        if s.len() >= 8 {
            let (x, rest) = toi8bytes(s);
            res = x;
            s = rest;
        }
        if s.len() >= 4 {
            let (x, rest) = toi4bytes(s);
            res = 10000 * res + x;
            s = rest;
        }
        for &c in s {
            res = 10 * res + (c & 0xf) as u32;
        }
        res
    }
    #[inline]
    fn u16(mut s: &[u8], pre: u16) -> u16 {
        let mut res = pre;
        if s.len() >= 4 {
            let (x, rest) = toi4bytes(s);
            res = 10000 * res + x as u16;
            s = rest;
        }
        for &c in s {
            res = 10 * res + (c & 0xf) as u16;
        }
        res
    }
    #[inline]
    fn u8(s: &[u8], pre: u8) -> u8 {
        let mut res = pre;
        for &c in s {
            res = 10 * res + (c & 0xf);
        }
        res
    }
    macro_rules! float {
        ($ ty : ident , $ uty : ident) => {
            impl ParseBytes for $ty {
                fn parse_bytes(s: &[u8]) -> Self {
                    const TEN: [$ty; 18] = [
                        1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
                        1e14, 1e15, 1e16, 1e17,
                    ];
                    let (minus, s) = if let Some((b'-', s)) = s.split_first() {
                        (true, s)
                    } else {
                        (false, s)
                    };
                    let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {
                        (&s[..p], &s[p + 1..])
                    } else {
                        (s, &s[..0])
                    };
                    let x = $uty(int, 0);
                    let x = if fract.is_empty() {
                        x as $ty
                    } else {
                        let ten = TEN
                            .get(fract.len())
                            .copied()
                            .unwrap_or_else(|| $ty::powi(10.0, fract.len() as _));
                        $uty(fract, x) as $ty / ten
                    };
                    if minus {
                        -x
                    } else {
                        x
                    }
                }
            }
        };
    }
    float!(f32, u32);
    float!(f64, u64);
    impl Parse for char {
        fn parse<T: Read>(src: &mut Input<T>) -> Self {
            let s = src.str();
            let mut cs = s.chars();
            match cs.next() {
                Some(c) if cs.as_str().is_empty() => c,
                _ => panic!("input is not single char"),
            }
        }
    }
    pub struct Byte(pub u8);
    impl Parse for Byte {
        fn parse<T: Read>(src: &mut Input<T>) -> Self {
            if let [b] = src.bytes() {
                Byte(*b)
            } else {
                panic!("input is not single byte")
            }
        }
    }
}
pub mod macros {
    extern "C" {
        pub fn isatty(fd: i32) -> i32;
    }
    #[macro_export]
    macro_rules ! w { ($ dst : expr , $ ($ arg : tt) *) => { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write ! ($ dst , "\x1B[1;33m") . unwrap () ; write ! ($ dst , $ ($ arg) *) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { write ! ($ dst , $ ($ arg) *) . unwrap () ; } } }
    #[macro_export]
    macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write ! ($ dst , "\x1B[1;33m") . unwrap () ; writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; } # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
    #[macro_export]
    macro_rules! w_iter {
        ($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{
            let mut first = true;
            for elem in $iter {
                if first {
                    w!($dst, $fmt, elem);
                    first = false;
                } else {
                    w!($dst, concat!($delim, $fmt), elem);
                }
            }
        }};
        ($ dst : expr , $ fmt : expr , $ iter : expr) => {
            w_iter!($dst, $fmt, $iter, " ")
        };
    }
    #[macro_export]
    macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
    #[macro_export]
    macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
    #[macro_export]
    #[doc(hidden)]
    macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
    #[macro_export]
    macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }
}