結果
| 問題 | No.2494 Sum within Components |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2023-10-07 20:57:08 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 21 ms / 2,000 ms |
| コード長 | 35,880 bytes |
| コンパイル時間 | 15,594 ms |
| コンパイル使用メモリ | 402,464 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-07-26 17:55:45 |
| 合計ジャッジ時間 | 14,456 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
warning: function `find_ws_naive` is never used
--> src/main.rs:781:19
|
781 | pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> {
| ^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
#![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) -> SelfwhereT: 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) ,*) ; } } ; }}