結果

問題 No.2260 Adic Sum
ユーザー cotton_fn_
提出日時 2023-04-07 22:47:08
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 24,285 bytes
コンパイル時間 13,310 ms
コンパイル使用メモリ 405,084 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-06 07:22:00
合計ジャッジ時間 15,474 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(unused_imports)]
use input::*;
use std::{
collections::*,
io::{self, BufWriter, Read, Write},
};
fn run<I: Input, O: Write>(mut ss: I, mut out: O) {
let t: u32 = 1;
for _ in 0..t {
case(&mut ss, &mut out);
}
}
fn case<I: Input, O: Write>(mut ss: I, mut out: O) {
use modint2::*;
let n: usize = ss.parse();
let p: u32 = ss.parse();
let a: Vec<u32> = ss.seq().take(n).collect();
let mut ans = 0;
let mut map = HashMap::new();
let mut pp = p;
while pp <= 1000000000 {
map.clear();
set_var_mod(pp);
for &a in &a {
let e = map.entry(var_mint(a)).or_insert(0);
ans += *e as i64;
*e += 1;
}
pp = pp.saturating_mul(p);
}
wln!(out, "{}", ans);
}
fn main() {
let stdin = io::stdin();
let ss = SplitWs::new(stdin.lock());
let stdout = io::stdout();
let out = BufWriter::new(stdout.lock());
run(ss, out);
}
pub mod input {
use std::{
io::{self, prelude::*},
marker::PhantomData,
};
#[macro_export]
macro_rules ! input { ($ src : expr , $ ($ var : ident $ (($ count : expr $ (, $ map : expr) ?)) ? $ (: $ ty : ty) ?) ,* $ (,) ?) => { $ (input !
        (@ $ src , $ var $ (($ count $ (, $ map) ?)) ? $ (: $ ty) ?) ;) * } ; (@ $ src : expr , $ var : ident $ (: $ ty : ty) ?) => { let $ var $ (:
        $ ty) ? = $ src . parse () ; } ; (@ $ src : expr , $ var : ident ($ count : expr) : $ ($ ty : ty) ?) => { let $ var $ (: $ ty) ? = $ src .
        seq () . take ($ count) . collect () ; } ; (@ $ src : expr , $ var : ident ($ count : expr , $ map : expr) : $ ($ ty : ty) ?) => { let $ var
        $ (: $ ty) ? = $ src . seq () . take ($ count) . map ($ map) . collect () ; } ; }
pub trait Input {
fn bytes(&mut self) -> &[u8];
fn bytes_vec(&mut self) -> Vec<u8> {
self.bytes().to_vec()
}
fn str(&mut self) -> &str {
std::str::from_utf8(self.bytes()).unwrap()
}
fn parse<T: Parse>(&mut self) -> T {
self.parse_with(DefaultParser)
}
fn parse_with<T>(&mut self, mut parser: impl Parser<T>) -> T {
parser.parse(self)
}
fn seq<T: Parse>(&mut self) -> Seq<T, Self, DefaultParser> {
self.seq_with(DefaultParser)
}
fn seq_with<T, P: Parser<T>>(&mut self, parser: P) -> Seq<T, Self, P> {
Seq {
input: self,
parser,
marker: PhantomData,
}
}
fn collect<T: Parse, C: std::iter::FromIterator<T>>(&mut self, n: usize) -> C {
self.seq().take(n).collect()
}
}
impl<T: Input> Input for &mut T {
fn bytes(&mut self) -> &[u8] {
(**self).bytes()
}
}
pub trait Parser<T> {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T;
}
impl<T, P: Parser<T>> Parser<T> for &mut P {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {
(**self).parse(s)
}
}
pub trait Parse {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self;
}
pub struct DefaultParser;
impl<T: Parse> Parser<T> for DefaultParser {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {
T::parse(s)
}
}
pub struct Seq<'a, T, I: ?Sized, P> {
input: &'a mut I,
parser: P,
marker: PhantomData<*const T>,
}
impl<'a, T, I: Input + ?Sized, P: Parser<T>> Iterator for Seq<'a, T, I, P> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
Some(self.input.parse_with(&mut self.parser))
}
fn size_hint(&self) -> (usize, Option<usize>) {
(!0, None)
}
}
impl Parse for char {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let s = s.bytes();
debug_assert_eq!(s.len(), 1);
*s.first().expect("zero length") as char
}
}
macro_rules ! tuple { ($ ($ T : ident) ,*) => { impl <$ ($ T : Parse) ,*> Parse for ($ ($ T ,) *) { # [inline] # [allow (unused_variables)] #
        [allow (clippy :: unused_unit)] fn parse < I : Input + ? Sized > (s : & mut I) -> Self { ($ ($ T :: parse (s) ,) *) } } } ; }
tuple!();
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);
#[cfg(feature = "newer")]
impl<T: Parse, const N: usize> Parse for [T; N] {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
use std::{
mem::{self, MaybeUninit},
ptr,
};
struct Guard<T, const N: usize> {
arr: [MaybeUninit<T>; N],
i: usize,
}
impl<T, const N: usize> Drop for Guard<T, N> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(&mut self.arr[..self.i] as *mut _ as *mut [T]);
}
}
}
let mut g = Guard::<T, N> {
arr: unsafe { MaybeUninit::uninit().assume_init() },
i: 0,
};
while g.i < N {
g.arr[g.i] = MaybeUninit::new(s.parse());
g.i += 1;
}
unsafe { mem::transmute_copy(&g.arr) }
}
}
macro_rules! uint {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let s = s.bytes();
s.iter().fold(0, |x, d| 10 * x + (0xf & d) as $ty)
}
}
};
}
macro_rules! int {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let f = |s: &[u8]| {
s.iter()
.fold(0 as $ty, |x, d| (10 * x).wrapping_add((0xf & d) as $ty))
};
let s = s.bytes();
if let Some((b'-', s)) = s.split_first() {
f(s).wrapping_neg()
} else {
f(s)
}
}
}
};
}
macro_rules! float {
($ ty : ty) => {
impl Parse for $ty {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
const POW: [$ty; 18] = [
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
1e14, 1e15, 1e16, 1e17,
];
let s = s.bytes();
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, &[][..])
};
let x = int
.iter()
.chain(fract)
.fold(0u64, |x, d| 10 * x + (0xf & *d) as u64);
let x = x as $ty;
let x = if minus { -x } else { x };
let exp = fract.len();
if exp == 0 {
x
} else if let Some(pow) = POW.get(exp) {
x / pow
} else {
x / (10.0 as $ty).powi(exp as i32)
}
}
}
};
}
macro_rules! from_bytes {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
s.bytes().into()
}
}
};
}
macro_rules! from_str {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
s.str().into()
}
}
};
}
macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; }
impls!(uint, usize, u8, u16, u32, u64, u128);
impls!(int, isize, i8, i16, i32, i64, i128);
impls!(float, f32, f64);
impls!(from_bytes, Vec<u8>, Box<[u8]>);
impls!(from_str, String);
#[derive(Clone)]
pub struct SplitWs<T> {
src: T,
buf: Vec<u8>,
pos: usize,
len: usize,
}
const BUF_SIZE: usize = 1 << 26;
impl<T: Read> SplitWs<T> {
pub fn new(src: T) -> Self {
Self {
src,
buf: vec![0; BUF_SIZE],
pos: 0,
len: 0,
}
}
#[inline(always)]
fn peek(&self) -> &[u8] {
unsafe { self.buf.get_unchecked(self.pos..self.len) }
}
#[inline(always)]
fn consume(&mut self, n: usize) -> &[u8] {
let pos = self.pos;
self.pos += n;
unsafe { self.buf.get_unchecked(pos..self.pos) }
}
fn read(&mut self) -> usize {
self.buf.copy_within(self.pos..self.len, 0);
self.len -= self.pos;
self.pos = 0;
if self.len == self.buf.len() {
self.buf.resize(2 * self.buf.len(), 0);
}
loop {
match self.src.read(&mut self.buf[self.len..]) {
Ok(n) => {
self.len += n;
return n;
}
Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}
Err(e) => panic!("io error: {:?}", e),
}
}
}
}
impl<T: Read> Input for SplitWs<T> {
#[inline]
fn bytes(&mut self) -> &[u8] {
loop {
if let Some(del) = self.peek().iter().position(|c| c.is_ascii_whitespace()) {
if del > 0 {
let s = self.consume(del + 1);
return s.split_last().unwrap().1;
} else {
self.consume(1);
}
} else if self.read() == 0 {
return self.consume(self.len - self.pos);
}
}
}
}
}
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) ,*) ; } } ; }
}
pub mod modint2 {
use std::{cell::Cell, 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 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 }) ; }
pub struct ModInt<M> {
value: u32,
marker: PhantomData<M>,
}
impl<M> ModInt<M> {
#[inline]
pub fn unnormalized(value: u32) -> Self {
Self {
value,
marker: PhantomData,
}
}
#[inline]
pub 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 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::unnormalized(0)
}
}
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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0