QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #836120 | #9921. Yelkrab | ucup-team296# | AC ✓ | 1548ms | 892840kb | Rust | 85.0kb | 2024-12-28 16:41:37 | 2024-12-28 16:41:53 |
Judging History
answer
// https://contest.ucup.ac/contest/1885/problem/9921
use crate::algo_lib::collections::iter_ext::iter_copied::ItersCopied;
use crate::algo_lib::collections::segment_tree::{Pushable, SegmentTree, SegmentTreeNode};
use crate::algo_lib::collections::vec_ext::default::default_vec;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::misc::recursive_function::{Callable2, RecursiveFunction2};
use crate::algo_lib::misc::test_type::TaskType;
use crate::algo_lib::misc::test_type::TestType;
use crate::algo_lib::numbers::primes::factorize::all_divisors;
use crate::algo_lib::string::str::StrReader;
type PreCalc = ();
fn solve(input: &mut Input, out: &mut Output, _test_case: usize, _data: &mut PreCalc) {
let n = input.read_size();
let s = input.read_str_vec(n);
#[derive(Default, Clone)]
struct Node {
val: usize,
}
impl SegmentTreeNode for Node {
fn new(_left: usize, _right: usize) -> Self {
Default::default()
}
fn join(&mut self, left_val: &Self, right_val: &Self) {
self.val = left_val.val ^ right_val.val;
}
}
impl Pushable<usize> for Node {
fn push(&mut self, delta: usize) {
self.val += delta;
}
}
let ad: Vec<Vec<usize>> = all_divisors(n + 1, false);
#[derive(Default)]
struct Bor {
qty: usize,
to: Vec<Option<Bor>>,
}
impl Bor {
fn new() -> Self {
Self {
qty: 0,
to: default_vec(26),
}
}
}
let mut root = Bor::new();
let mut st: SegmentTree<Node> = SegmentTree::new(n);
let mut ans = Vec::new();
for s in s {
let mut first = true;
let mut rec = RecursiveFunction2::new(|rec, node: &mut Bor, s: &[u8]| {
node.qty += 1;
if !first {
for d in ad[node.qty].copy_iter() {
st.point_update(d - 1, d);
}
} else {
first = false;
}
if !s.is_empty() {
let c = (s[0] - b'a') as usize;
if node.to[c].is_none() {
node.to[c] = Some(Bor::new());
}
rec.call(node.to[c].as_mut().unwrap(), &s[1..]);
}
});
rec.call(&mut root, s.as_slice());
ans.push(st.query(..).val);
}
out.print_line(ans);
}
pub static TEST_TYPE: TestType = TestType::MultiNumber;
pub static TASK_TYPE: TaskType = TaskType::Classic;
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
let mut pre_calc = ();
match TEST_TYPE {
TestType::Single => solve(&mut input, &mut output, 1, &mut pre_calc),
TestType::MultiNumber => {
let t = input.read();
for i in 1..=t {
solve(&mut input, &mut output, i, &mut pre_calc);
}
}
TestType::MultiEof => {
let mut i = 1;
while input.peek().is_some() {
solve(&mut input, &mut output, i, &mut pre_calc);
i += 1;
}
}
}
output.flush();
match TASK_TYPE {
TaskType::Classic => input.is_empty(),
TaskType::Interactive => true,
}
}
fn main() {
let mut sin = std::io::stdin();
let input = crate::algo_lib::io::input::Input::new(&mut sin);
let mut stdout = std::io::stdout();
let output = crate::algo_lib::io::output::Output::new(&mut stdout);
run(input, output);
}
pub mod algo_lib {
pub mod collections {
pub mod bit_set {
use crate::algo_lib::collections::iter_ext::iter_copied::ItersCopied;
use crate::algo_lib::collections::slice_ext::legacy_fill::LegacyFill;
use crate::algo_lib::numbers::num_traits::bit_ops::BitOps;
use std::ops::{BitAndAssign, BitOrAssign, BitXorAssign, Index, ShlAssign, ShrAssign};
const TRUE: bool = true;
const FALSE: bool = false;
#[derive(Clone, Eq, PartialEq, Hash)]
pub struct BitSet {
data: Vec<u64>,
len: usize,
}
impl BitSet {
pub fn new(len: usize) -> Self {
let data_len = if len == 0 { 0 } else { Self::index(len - 1) + 1 };
Self {
data: vec![0; data_len],
len,
}
}
pub fn from_slice(len: usize, set: &[usize]) -> Self {
let mut res = Self::new(len);
for &i in set {
res.set(i);
}
res
}
pub fn set(&mut self, at: usize) {
assert!(at < self.len);
self.data[Self::index(at)].set_bit(at & 63);
}
pub fn unset(&mut self, at: usize) {
assert!(at < self.len);
self.data[Self::index(at)].unset_bit(at & 63);
}
pub fn change(&mut self, at: usize, value: bool) {
if value {
self.set(at);
} else {
self.unset(at);
}
}
pub fn flip(&mut self, at: usize) {
self.change(at, !self[at]);
}
#[allow(clippy::len_without_is_empty)]
pub fn len(&self) -> usize {
self.len
}
pub fn fill(&mut self, value: bool) {
self.data.legacy_fill(if value { std::u64::MAX } else { 0 });
if value {
self.fix_last();
}
}
pub fn is_superset(&self, other: &Self) -> bool {
assert_eq!(self.len, other.len);
for (we, them) in self.data.copy_zip(&other.data) {
if (we & them) != them {
return false;
}
}
true
}
pub fn is_subset(&self, other: &Self) -> bool {
other.is_superset(self)
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.into_iter()
}
fn index(at: usize) -> usize {
at >> 6
}
pub fn count_ones(&self) -> usize {
self.data.iter().map(|x| x.count_ones() as usize).sum()
}
fn fix_last(&mut self) {
if self.len & 63 != 0 {
let mask = (1 << (self.len & 63)) - 1;
*self.data.last_mut().unwrap() &= mask;
}
}
}
pub struct BitSetIter<'s> {
at: usize,
inside: usize,
set: &'s BitSet,
}
impl<'s> Iterator for BitSetIter<'s> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
while self.at < self.set.data.len()
&& (self.inside == 64 || (self.set.data[self.at] >> self.inside) == 0)
{
self.at += 1;
self.inside = 0;
}
if self.at == self.set.data.len() {
None
} else {
while !self.set.data[self.at].is_set(self.inside) {
self.inside += 1;
}
let res = self.at * 64 + self.inside;
if res < self.set.len {
self.inside += 1;
Some(res)
} else {
None
}
}
}
}
impl<'a> IntoIterator for &'a BitSet {
type Item = usize;
type IntoIter = BitSetIter<'a>;
fn into_iter(self) -> Self::IntoIter {
BitSetIter {
at: 0,
inside: 0,
set: self,
}
}
}
impl BitOrAssign<&BitSet> for BitSet {
fn bitor_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i |= j;
}
}
}
impl BitAndAssign<&BitSet> for BitSet {
fn bitand_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i &= j;
}
}
}
impl BitXorAssign<&BitSet> for BitSet {
fn bitxor_assign(&mut self, rhs: &BitSet) {
assert_eq!(self.len, rhs.len);
for (i, &j) in self.data.iter_mut().zip(rhs.data.iter()) {
*i ^= j;
}
}
}
impl ShlAssign<usize> for BitSet {
fn shl_assign(&mut self, rhs: usize) {
if rhs == 0 {
return;
}
if rhs >= self.len {
self.fill(false);
return;
}
let small_shift = rhs & 63;
if small_shift != 0 {
let mut carry = 0;
for data in self.data.iter_mut() {
let new_carry = (*data) >> (64 - small_shift);
*data <<= small_shift;
*data |= carry;
carry = new_carry;
}
}
let big_shift = rhs >> 6;
if big_shift != 0 {
self.data.rotate_right(big_shift);
self.data[..big_shift].fill(0);
}
self.fix_last();
}
}
impl ShrAssign<usize> for BitSet {
fn shr_assign(&mut self, rhs: usize) {
if rhs == 0 {
return;
}
if rhs >= self.len {
self.fill(false);
return;
}
let small_shift = rhs & 63;
if small_shift != 0 {
let mut carry = 0;
for data in self.data.iter_mut().rev() {
let new_carry = (*data) << (64 - small_shift);
*data >>= small_shift;
*data |= carry;
carry = new_carry;
}
}
let big_shift = rhs >> 6;
if big_shift != 0 {
self.data.rotate_left(big_shift);
let from = self.data.len() - big_shift;
self.data[from..].fill(0);
}
}
}
impl Index<usize> for BitSet {
type Output = bool;
fn index(&self, at: usize) -> &Self::Output {
assert!(at < self.len);
if self.data[Self::index(at)].is_set(at & 63) { &TRUE } else { &FALSE }
}
}
impl From<Vec<bool>> for BitSet {
fn from(data: Vec<bool>) -> Self {
let mut res = Self::new(data.len());
for (i, &value) in data.iter().enumerate() {
res.change(i, value);
}
res
}
}
}
pub mod bounds {
use std::ops::RangeBounds;
pub fn clamp(range: impl RangeBounds<usize>, n: usize) -> (usize, usize) {
let start = match range.start_bound() {
std::ops::Bound::Included(&x) => x,
std::ops::Bound::Excluded(&x) => x + 1,
std::ops::Bound::Unbounded => 0,
};
let end = match range.end_bound() {
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
std::ops::Bound::Unbounded => n,
};
(start, end.min(n))
}
}
pub mod fx_hash_map {
use std::cell::Cell;
use std::convert::TryInto;
use std::time::SystemTime;
use std::{
collections::{HashMap, HashSet},
hash::{BuildHasherDefault, Hasher},
mem::size_of, ops::BitXor,
};
pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
#[derive(Default)]
pub struct FxHasher {
hash: usize,
}
thread_local! {
static K : Cell < usize > = Cell::new(((SystemTime::UNIX_EPOCH.elapsed().unwrap()
.as_nanos().wrapping_mul(2) + 1) & 0xFFFFFFFFFFFFFFFF) as usize);
}
impl FxHasher {
#[inline]
fn add_to_hash(&mut self, i: usize) {
self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K.with(|k| k.get()));
}
}
impl Hasher for FxHasher {
#[inline]
fn write(&mut self, mut bytes: &[u8]) {
let read_usize = |bytes: &[u8]| u64::from_ne_bytes(
bytes[..8].try_into().unwrap(),
);
let mut hash = FxHasher { hash: self.hash };
while bytes.len() >= size_of::<usize>() {
hash.add_to_hash(read_usize(bytes) as usize);
bytes = &bytes[size_of::<usize>()..];
}
if (size_of::<usize>() > 4) && (bytes.len() >= 4) {
hash.add_to_hash(
u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as usize,
);
bytes = &bytes[4..];
}
if (size_of::<usize>() > 2) && bytes.len() >= 2 {
hash.add_to_hash(
u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as usize,
);
bytes = &bytes[2..];
}
if (size_of::<usize>() > 1) && !bytes.is_empty() {
hash.add_to_hash(bytes[0] as usize);
}
self.hash = hash.hash;
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u16(&mut self, i: u16) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.add_to_hash(i as usize);
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.add_to_hash(i);
}
#[inline]
fn finish(&self) -> u64 {
self.hash as u64
}
}
}
pub mod iter_ext {
pub mod iter_copied {
use std::iter::{
Chain, Copied, Enumerate, Filter, Map, Rev, Skip, StepBy, Sum, Take, Zip,
};
pub trait ItersCopied<'a, T: 'a + Copy>: Sized + 'a
where
&'a Self: IntoIterator<Item = &'a T>,
{
fn copy_iter(&'a self) -> Copied<<&'a Self as IntoIterator>::IntoIter> {
self.into_iter().copied()
}
fn copy_enumerate(
&'a self,
) -> Enumerate<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().enumerate()
}
fn copy_rev(&'a self) -> Rev<Copied<<&'a Self as IntoIterator>::IntoIter>>
where
Copied<<&'a Self as IntoIterator>::IntoIter>: DoubleEndedIterator,
{
self.copy_iter().rev()
}
fn copy_skip(
&'a self,
n: usize,
) -> Skip<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().skip(n)
}
fn copy_take(
&'a self,
n: usize,
) -> Take<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().take(n)
}
fn copy_chain<V>(
&'a self,
chained: &'a V,
) -> Chain<
Copied<<&'a Self as IntoIterator>::IntoIter>,
Copied<<&'a V as IntoIterator>::IntoIter>,
>
where
&'a V: IntoIterator<Item = &'a T>,
{
self.copy_iter().chain(chained.into_iter().copied())
}
fn copy_zip<V>(
&'a self,
other: &'a V,
) -> Zip<
Copied<<&'a Self as IntoIterator>::IntoIter>,
Copied<<&'a V as IntoIterator>::IntoIter>,
>
where
&'a V: IntoIterator<Item = &'a T>,
{
self.copy_iter().zip(other.into_iter().copied())
}
fn copy_max(&'a self) -> T
where
T: Ord,
{
self.copy_iter().max().unwrap()
}
fn copy_max_by_key<B, F>(&'a self, f: F) -> T
where
F: FnMut(&T) -> B,
B: Ord,
{
self.copy_iter().max_by_key(f).unwrap()
}
fn copy_min(&'a self) -> T
where
T: Ord,
{
self.copy_iter().min().unwrap()
}
fn copy_min_by_key<B, F>(&'a self, f: F) -> T
where
F: FnMut(&T) -> B,
B: Ord,
{
self.copy_iter().min_by_key(f).unwrap()
}
fn copy_sum(&'a self) -> T
where
T: Sum<T>,
{
self.copy_iter().sum()
}
fn copy_map<F, U>(
&'a self,
f: F,
) -> Map<Copied<<&'a Self as IntoIterator>::IntoIter>, F>
where
F: FnMut(T) -> U,
{
self.copy_iter().map(f)
}
fn copy_all(&'a self, f: impl FnMut(T) -> bool) -> bool {
self.copy_iter().all(f)
}
fn copy_any(&'a self, f: impl FnMut(T) -> bool) -> bool {
self.copy_iter().any(f)
}
fn copy_step_by(
&'a self,
step: usize,
) -> StepBy<Copied<<&'a Self as IntoIterator>::IntoIter>> {
self.copy_iter().step_by(step)
}
fn copy_filter<F: FnMut(&T) -> bool>(
&'a self,
f: F,
) -> Filter<Copied<<&'a Self as IntoIterator>::IntoIter>, F> {
self.copy_iter().filter(f)
}
fn copy_fold<Acc, F>(&'a self, init: Acc, f: F) -> Acc
where
F: FnMut(Acc, T) -> Acc,
{
self.copy_iter().fold(init, f)
}
fn copy_reduce<F>(&'a self, f: F) -> Option<T>
where
F: FnMut(T, T) -> T,
{
self.copy_iter().reduce(f)
}
fn copy_position<P>(&'a self, predicate: P) -> Option<usize>
where
P: FnMut(T) -> bool,
{
self.copy_iter().position(predicate)
}
fn copy_find(&'a self, val: T) -> Option<usize>
where
T: PartialEq,
{
self.copy_iter().position(|x| x == val)
}
fn copy_count(&'a self, val: T) -> usize
where
T: PartialEq,
{
self.copy_iter().filter(|&x| x == val).count()
}
}
impl<'a, U: 'a, T: 'a + Copy> ItersCopied<'a, T> for U
where
&'a U: IntoIterator<Item = &'a T>,
{}
}
}
pub mod segment_tree {
use crate::algo_lib::collections::bounds::clamp;
use crate::algo_lib::misc::direction::Direction;
use crate::when;
use std::marker::PhantomData;
use std::ops::RangeBounds;
#[allow(unused_variables)]
pub trait SegmentTreeNode {
fn new(left: usize, right: usize) -> Self;
fn join(&mut self, left_val: &Self, right_val: &Self) {}
fn accumulate(&mut self, value: &Self) {}
fn reset_delta(&mut self) {}
}
pub trait Pushable<T>: SegmentTreeNode {
fn push(&mut self, delta: T);
}
impl<T: SegmentTreeNode> Pushable<&T> for T {
fn push(&mut self, delta: &T) {
self.accumulate(delta);
}
}
impl<T: SegmentTreeNode> Pushable<T> for T {
fn push(&mut self, delta: T) {
*self = delta;
}
}
pub trait QueryResult<Result, Args>: SegmentTreeNode {
fn empty_result(args: &Args) -> Result;
fn result(&self, args: &Args) -> Result;
fn join_results(
left_res: Result,
right_res: Result,
args: &Args,
left: usize,
mid: usize,
right: usize,
) -> Result;
}
impl<T: SegmentTreeNode + Clone> QueryResult<T, ()> for T {
fn empty_result(_: &()) -> T {
Self::new(0, 0)
}
fn result(&self, _: &()) -> T {
self.clone()
}
fn join_results(
left_res: T,
right_res: T,
_: &(),
left: usize,
mid: usize,
right: usize,
) -> T {
when! {
left == mid => right_res, right == mid => left_res, else => { let mut res =
Self::new(left, right); res.join(& left_res, & right_res); res },
}
}
}
#[derive(Clone)]
pub struct SegmentTree<Node> {
n: usize,
nodes: Vec<Node>,
}
impl<Node: SegmentTreeNode> SegmentTree<Node> {
pub fn new(n: usize) -> Self {
Self::gen(n, |left| Node::new(left, left + 1))
}
pub fn from_array(arr: Vec<Node>) -> Self {
let n = arr.len();
let mut iter = arr.into_iter();
Self::gen(n, |_| iter.next().unwrap())
}
pub fn gen<F>(n: usize, gen: F) -> Self
where
F: FnMut(usize) -> Node,
{
if n == 0 {
return Self {
n,
nodes: vec![Node::new(0, 0)],
};
}
let mut res = Self {
n,
nodes: Vec::with_capacity(2 * n - 1),
};
res.init(gen);
res
}
fn init<F>(&mut self, mut f: F)
where
F: FnMut(usize) -> Node,
{
self.init_impl(2 * self.n - 2, 0, self.n, &mut f);
}
fn init_impl<F>(&mut self, root: usize, left: usize, right: usize, f: &mut F)
where
F: FnMut(usize) -> Node,
{
if left + 1 == right {
self.nodes.push(f(left));
} else {
let mid = left + ((right - left) >> 1);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
self.init_impl(left_child, left, mid, f);
self.init_impl(right_child, mid, right, f);
let mut node = Node::new(left, right);
node.join(&self.nodes[left_child], &self.nodes[right_child]);
self.nodes.push(node);
}
}
pub fn point_query(&mut self, at: usize) -> &Node {
assert!(at < self.n);
self.do_point_query(self.nodes.len() - 1, 0, self.n, at)
}
fn do_point_query(
&mut self,
root: usize,
left: usize,
right: usize,
at: usize,
) -> &Node {
if left + 1 == right {
&self.nodes[root]
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
if at < mid {
self.do_point_query(left_child, left, mid, at)
} else {
self.do_point_query(right_child, mid, right, at)
}
}
}
pub fn point_update<T>(&mut self, at: usize, val: T)
where
Node: Pushable<T>,
{
assert!(at < self.n);
self.do_point_update(self.nodes.len() - 1, 0, self.n, at, val);
}
fn do_point_update<T>(
&mut self,
root: usize,
left: usize,
right: usize,
at: usize,
val: T,
)
where
Node: Pushable<T>,
{
if left + 1 == right {
self.nodes[root].push(val);
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
if at < mid {
self.do_point_update(left_child, left, mid, at, val);
} else {
self.do_point_update(right_child, mid, right, at, val);
}
self.join(root, mid, right);
}
}
pub fn point_through_update<'a, T>(&mut self, at: usize, val: &'a T)
where
Node: Pushable<&'a T>,
{
assert!(at < self.n);
self.do_point_through_update(self.nodes.len() - 1, 0, self.n, at, val);
}
fn do_point_through_update<'a, T>(
&mut self,
root: usize,
left: usize,
right: usize,
at: usize,
val: &'a T,
)
where
Node: Pushable<&'a T>,
{
self.nodes[root].push(val);
if left + 1 != right {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
if at < mid {
self.do_point_through_update(left_child, left, mid, at, val);
} else {
self.do_point_through_update(right_child, mid, right, at, val);
}
}
}
pub fn point_operation<Args, Res>(
&mut self,
op: &mut dyn PointOperation<Node, Args, Res>,
args: Args,
) -> Res {
assert_ne!(self.n, 0);
self.do_point_operation(op, self.nodes.len() - 1, 0, self.n, args)
}
fn do_point_operation<Args, Res>(
&mut self,
op: &mut dyn PointOperation<Node, Args, Res>,
root: usize,
left: usize,
right: usize,
args: Args,
) -> Res {
if left + 1 == right {
op.adjust_leaf(&mut self.nodes[root], left, args)
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let (l, r) = self.nodes.split_at_mut(root);
let (l, m) = l.split_at_mut(right_child);
let direction = op
.select_branch(
&mut r[0],
&mut l[left_child],
&mut m[0],
&args,
left,
mid,
right,
);
let res = match direction {
Direction::Left => {
self.do_point_operation(op, left_child, left, mid, args)
}
Direction::Right => {
self.do_point_operation(op, right_child, mid, right, args)
}
};
self.join(root, mid, right);
res
}
}
pub fn update<'a, T>(&mut self, range: impl RangeBounds<usize>, val: &'a T)
where
Node: Pushable<&'a T>,
{
let (from, to) = clamp(range, self.n);
self.do_update(self.nodes.len() - 1, 0, self.n, from, to, val)
}
pub fn do_update<'a, T>(
&mut self,
root: usize,
left: usize,
right: usize,
from: usize,
to: usize,
val: &'a T,
)
where
Node: Pushable<&'a T>,
{
when! {
left >= to || right <= from => {}, left >= from && right <= to => self
.nodes[root].push(val), else => { let mid = (left + right) >> 1; self
.push_down(root, mid, right); let left_child = root - 2 * (right - mid); let
right_child = root - 1; self.do_update(left_child, left, mid, from, to, val);
self.do_update(right_child, mid, right, from, to, val); self.join(root, mid,
right); },
}
}
pub fn operation<Args, Res>(
&mut self,
range: impl RangeBounds<usize>,
op: &mut dyn Operation<Node, Args, Res>,
args: &Args,
) -> Res {
let (from, to) = clamp(range, self.n);
self.do_operation(self.nodes.len() - 1, 0, self.n, from, to, op, args)
}
pub fn do_operation<Args, Res>(
&mut self,
root: usize,
left: usize,
right: usize,
from: usize,
to: usize,
op: &mut dyn Operation<Node, Args, Res>,
args: &Args,
) -> Res {
when! {
left >= to || right <= from => op.empty_result(left, right, args), left >=
from && right <= to => op.process_result(& mut self.nodes[root], args), else
=> { let mid = (left + right) >> 1; self.push_down(root, mid, right); let
left_child = root - 2 * (right - mid); let right_child = root - 1; let
left_result = self.do_operation(left_child, left, mid, from, to, op, args);
let right_result = self.do_operation(right_child, mid, right, from, to, op,
args); self.join(root, mid, right); op.join_results(left_result,
right_result, args) },
}
}
pub fn binary_search<Res>(
&mut self,
wh: impl FnMut(&Node, &Node) -> Direction,
calc: impl FnMut(&Node, usize) -> Res,
) -> Res {
self.do_binary_search(self.nodes.len() - 1, 0, self.n, wh, calc)
}
fn do_binary_search<Res>(
&mut self,
root: usize,
left: usize,
right: usize,
mut wh: impl FnMut(&Node, &Node) -> Direction,
mut calc: impl FnMut(&Node, usize) -> Res,
) -> Res {
if left + 1 == right {
calc(&self.nodes[root], left)
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let direction = wh(&self.nodes[left_child], &self.nodes[right_child]);
match direction {
Direction::Left => self.do_binary_search(left_child, left, mid, wh, calc),
Direction::Right => {
self.do_binary_search(right_child, mid, right, wh, calc)
}
}
}
}
fn join(&mut self, root: usize, mid: usize, right: usize) {
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
let (left_node, right_node) = self.nodes.split_at_mut(root);
right_node[0].join(&left_node[left_child], &left_node[right_child]);
}
fn do_push_down(&mut self, parent: usize, to: usize) {
let (left_nodes, right_nodes) = self.nodes.split_at_mut(parent);
left_nodes[to].accumulate(&right_nodes[0]);
}
fn push_down(&mut self, root: usize, mid: usize, right: usize) {
self.do_push_down(root, root - 2 * (right - mid));
self.do_push_down(root, root - 1);
self.nodes[root].reset_delta();
}
pub fn query<T>(&mut self, range: impl RangeBounds<usize>) -> T
where
Node: QueryResult<T, ()>,
{
let (from, to) = clamp(range, self.n);
if from >= to {
Node::empty_result(&())
} else {
self.do_query(self.nodes.len() - 1, 0, self.n, from, to, &())
}
}
pub fn query_with_args<T, Args>(
&mut self,
range: impl RangeBounds<usize>,
args: &Args,
) -> T
where
Node: QueryResult<T, Args>,
{
let (from, to) = clamp(range, self.n);
if from >= to {
Node::empty_result(args)
} else {
self.do_query(self.nodes.len() - 1, 0, self.n, from, to, args)
}
}
fn do_query<T, Args>(
&mut self,
root: usize,
left: usize,
right: usize,
from: usize,
to: usize,
args: &Args,
) -> T
where
Node: QueryResult<T, Args>,
{
if left >= from && right <= to {
self.nodes[root].result(args)
} else {
let mid = (left + right) >> 1;
self.push_down(root, mid, right);
let left_child = root - 2 * (right - mid);
let right_child = root - 1;
when! {
to <= mid => self.do_query(left_child, left, mid, from, to, args), from
>= mid => self.do_query(right_child, mid, right, from, to, args), else =>
{ let left_result = self.do_query(left_child, left, mid, from, to, args);
let right_result = self.do_query(right_child, mid, right, from, to,
args); Node::join_results(left_result, right_result, args, left, mid,
right) },
}
}
}
}
pub trait PointOperation<Node: SegmentTreeNode, Args, Res = Node> {
fn adjust_leaf(&mut self, leaf: &mut Node, at: usize, args: Args) -> Res;
fn select_branch(
&mut self,
root: &mut Node,
left_child: &mut Node,
right_child: &mut Node,
args: &Args,
left: usize,
mid: usize,
right: usize,
) -> Direction;
}
pub struct PointOperationClosure<'s, Node: SegmentTreeNode, Args, Res = Node> {
adjust_leaf: Box<dyn FnMut(&mut Node, usize, Args) -> Res + 's>,
select_branch: Box<
dyn FnMut(
&mut Node,
&mut Node,
&mut Node,
&Args,
usize,
usize,
usize,
) -> Direction + 's,
>,
phantom_node: PhantomData<Node>,
phantom_args: PhantomData<Args>,
phantom_res: PhantomData<Res>,
}
impl<'s, Node: SegmentTreeNode, Args, Res> PointOperationClosure<'s, Node, Args, Res> {
pub fn new<F1, F2>(adjust_leaf: F1, select_branch: F2) -> Self
where
F1: FnMut(&mut Node, usize, Args) -> Res + 's,
F2: FnMut(
&mut Node,
&mut Node,
&mut Node,
&Args,
usize,
usize,
usize,
) -> Direction + 's,
{
Self {
adjust_leaf: Box::new(adjust_leaf),
select_branch: Box::new(select_branch),
phantom_node: Default::default(),
phantom_args: Default::default(),
phantom_res: Default::default(),
}
}
}
impl<'s, Node: SegmentTreeNode, Args, Res> PointOperation<Node, Args, Res>
for PointOperationClosure<'s, Node, Args, Res> {
fn adjust_leaf(&mut self, leaf: &mut Node, at: usize, args: Args) -> Res {
(self.adjust_leaf)(leaf, at, args)
}
fn select_branch(
&mut self,
root: &mut Node,
left_child: &mut Node,
right_child: &mut Node,
args: &Args,
left: usize,
mid: usize,
right: usize,
) -> Direction {
(self.select_branch)(root, left_child, right_child, args, left, mid, right)
}
}
pub trait Operation<Node: SegmentTreeNode, Args, Res = Node> {
fn process_result(&mut self, node: &mut Node, args: &Args) -> Res;
fn join_results(&mut self, left_res: Res, right_res: Res, args: &Args) -> Res;
fn empty_result(&mut self, left: usize, right: usize, args: &Args) -> Res;
}
pub struct OperationClosure<'s, Node: SegmentTreeNode, Args, Res = Node> {
process_result: Box<dyn FnMut(&mut Node, &Args) -> Res + 's>,
join_results: Box<dyn FnMut(Res, Res, &Args) -> Res + 's>,
empty_result: Box<dyn FnMut(usize, usize, &Args) -> Res + 's>,
phantom_node: PhantomData<Node>,
phantom_args: PhantomData<Args>,
phantom_res: PhantomData<Res>,
}
impl<'s, Node: SegmentTreeNode, Args, Res> OperationClosure<'s, Node, Args, Res> {
pub fn new<F1, F2, F3>(
process_result: F1,
join_results: F2,
empty_result: F3,
) -> Self
where
F1: FnMut(&mut Node, &Args) -> Res + 's,
F2: FnMut(Res, Res, &Args) -> Res + 's,
F3: FnMut(usize, usize, &Args) -> Res + 's,
{
Self {
process_result: Box::new(process_result),
join_results: Box::new(join_results),
empty_result: Box::new(empty_result),
phantom_node: Default::default(),
phantom_args: Default::default(),
phantom_res: Default::default(),
}
}
}
impl<'s, Node: SegmentTreeNode, Args, Res> Operation<Node, Args, Res>
for OperationClosure<'s, Node, Args, Res> {
fn process_result(&mut self, node: &mut Node, args: &Args) -> Res {
(self.process_result)(node, args)
}
fn join_results(&mut self, left_res: Res, right_res: Res, args: &Args) -> Res {
(self.join_results)(left_res, right_res, args)
}
fn empty_result(&mut self, left: usize, right: usize, args: &Args) -> Res {
(self.empty_result)(left, right, args)
}
}
}
pub mod slice_ext {
pub mod indices {
use std::ops::Range;
pub trait Indices {
fn indices(&self) -> Range<usize>;
}
impl<T> Indices for [T] {
fn indices(&self) -> Range<usize> {
0..self.len()
}
}
}
pub mod legacy_fill {
pub trait LegacyFill<T> {
fn legacy_fill(&mut self, val: T);
}
impl<T: Clone> LegacyFill<T> for [T] {
fn legacy_fill(&mut self, val: T) {
for el in self.iter_mut() {
*el = val.clone();
}
}
}
}
}
pub mod vec_ext {
pub mod default {
pub fn default_vec<T: Default>(len: usize) -> Vec<T> {
let mut v = Vec::with_capacity(len);
for _ in 0..len {
v.push(T::default());
}
v
}
}
pub mod sorted {
pub trait Sorted {
fn sorted(self) -> Self;
}
impl<T: Ord> Sorted for Vec<T> {
fn sorted(mut self) -> Self {
self.sort();
self
}
}
}
}
}
pub mod io {
pub mod input {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::io::Read;
use std::mem::MaybeUninit;
pub struct Input<'s> {
input: &'s mut (dyn Read + Send),
buf: Vec<u8>,
at: usize,
buf_read: usize,
eol: bool,
}
macro_rules! read_impl {
($t:ty, $read_name:ident, $read_vec_name:ident) => {
pub fn $read_name (& mut self) -> $t { self.read() } pub fn $read_vec_name (& mut
self, len : usize) -> Vec <$t > { self.read_vec(len) }
};
($t:ty, $read_name:ident, $read_vec_name:ident, $read_pair_vec_name:ident) => {
read_impl!($t, $read_name, $read_vec_name); pub fn $read_pair_vec_name (& mut
self, len : usize) -> Vec < ($t, $t) > { self.read_vec(len) }
};
}
impl<'s> Input<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(input: &'s mut (dyn Read + Send)) -> Self {
Self {
input,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn new_with_size(input: &'s mut (dyn Read + Send), buf_size: usize) -> Self {
Self {
input,
buf: default_vec(buf_size),
at: 0,
buf_read: 0,
eol: true,
}
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
if res == b'\r' {
self.eol = true;
if self.refill_buffer() && self.buf[self.at] == b'\n' {
self.at += 1;
}
return Some(b'\n');
}
self.eol = res == b'\n';
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
Some(if res == b'\r' { b'\n' } else { res })
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !b.is_ascii_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if c.is_ascii_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() { None } else { Some(res) }
}
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn is_empty(&mut self) -> bool {
self.skip_whitespace();
self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn read_vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0..size {
res.push(self.read());
}
res
}
pub fn read_char(&mut self) -> u8 {
self.skip_whitespace();
self.get().unwrap()
}
read_impl!(u32, read_unsigned, read_unsigned_vec);
read_impl!(u64, read_u64, read_u64_vec);
read_impl!(usize, read_size, read_size_vec, read_size_pair_vec);
read_impl!(i32, read_int, read_int_vec, read_int_pair_vec);
read_impl!(i64, read_long, read_long_vec, read_long_pair_vec);
read_impl!(i128, read_i128, read_i128_vec);
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
pub fn is_eol(&self) -> bool {
self.eol
}
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for u8 {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.read_vec(size)
}
}
impl<T: Readable, const SIZE: usize> Readable for [T; SIZE] {
fn read(input: &mut Input) -> Self {
unsafe {
let mut res = MaybeUninit::<[T; SIZE]>::uninit();
for i in 0..SIZE {
let ptr: *mut T = (*res.as_mut_ptr()).as_mut_ptr();
ptr.add(i).write(input.read::<T>());
}
res.assume_init()
}
}
}
macro_rules! read_integer {
($($t:ident)+) => {
$(impl Readable for $t { fn read(input : & mut Input) -> Self { input
.skip_whitespace(); let mut c = input.get().unwrap(); let sgn = match c { b'-' =>
{ c = input.get().unwrap(); true } b'+' => { c = input.get().unwrap(); false } _
=> false, }; let mut res = 0; loop { assert!(c.is_ascii_digit()); res *= 10; let
d = (c - b'0') as $t; if sgn { res -= d; } else { res += d; } match input.get() {
None => break, Some(ch) => { if ch.is_ascii_whitespace() { break; } else { c =
ch; } } } } res } })+
};
}
read_integer!(i8 i16 i32 i64 i128 isize u16 u32 u64 u128 usize);
macro_rules! tuple_readable {
($($name:ident)+) => {
impl <$($name : Readable),+> Readable for ($($name,)+) { fn read(input : & mut
Input) -> Self { ($($name ::read(input),)+) } }
};
}
tuple_readable! {
T
}
tuple_readable! {
T U
}
tuple_readable! {
T U V
}
tuple_readable! {
T U V X
}
tuple_readable! {
T U V X Y
}
tuple_readable! {
T U V X Y Z
}
tuple_readable! {
T U V X Y Z A
}
tuple_readable! {
T U V X Y Z A B
}
tuple_readable! {
T U V X Y Z A B C
}
tuple_readable! {
T U V X Y Z A B C D
}
tuple_readable! {
T U V X Y Z A B C D E
}
tuple_readable! {
T U V X Y Z A B C D E F
}
impl Read for Input<'_> {
fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
if self.at == self.buf_read {
self.input.read(buf)
} else {
let mut i = 0;
while i < buf.len() && self.at < self.buf_read {
buf[i] = self.buf[self.at];
i += 1;
self.at += 1;
}
Ok(i)
}
}
}
}
pub mod output {
use crate::algo_lib::collections::vec_ext::default::default_vec;
use std::cmp::Reverse;
use std::io::{stderr, Stderr, Write};
#[derive(Copy, Clone)]
pub enum BoolOutput {
YesNo,
YesNoCaps,
PossibleImpossible,
Custom(&'static str, &'static str),
}
impl BoolOutput {
pub fn output(&self, output: &mut Output, val: bool) {
(if val { self.yes() } else { self.no() }).write(output);
}
fn yes(&self) -> &str {
match self {
BoolOutput::YesNo => "Yes",
BoolOutput::YesNoCaps => "YES",
BoolOutput::PossibleImpossible => "Possible",
BoolOutput::Custom(yes, _) => yes,
}
}
fn no(&self) -> &str {
match self {
BoolOutput::YesNo => "No",
BoolOutput::YesNoCaps => "NO",
BoolOutput::PossibleImpossible => "Impossible",
BoolOutput::Custom(_, no) => no,
}
}
}
pub struct Output<'s> {
output: &'s mut dyn Write,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
bool_output: BoolOutput,
precision: Option<usize>,
separator: u8,
}
impl<'s> Output<'s> {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: false,
bool_output: BoolOutput::YesNoCaps,
precision: None,
separator: b' ',
}
}
pub fn new_with_auto_flush(output: &'s mut dyn Write) -> Self {
Self {
output,
buf: default_vec(Self::DEFAULT_BUF_SIZE),
at: 0,
auto_flush: true,
bool_output: BoolOutput::YesNoCaps,
precision: None,
separator: b' ',
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.output.flush().unwrap();
self.at = 0;
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
self.maybe_flush();
}
pub fn print_line<T: Writable>(&mut self, s: T) {
self.print(s);
self.put(b'\n');
self.maybe_flush();
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
self.print_per_line_iter(arg.iter());
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(self.separator);
}
e.write(self);
}
}
pub fn print_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
self.print_iter(iter);
self.put(b'\n');
}
pub fn print_per_line_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
for e in iter {
e.write(self);
self.put(b'\n');
}
}
pub fn set_bool_output(&mut self, bool_output: BoolOutput) {
self.bool_output = bool_output;
}
pub fn set_precision(&mut self, precision: usize) {
self.precision = Some(precision);
}
pub fn reset_precision(&mut self) {
self.precision = None;
}
pub fn get_precision(&self) -> Option<usize> {
self.precision
}
pub fn separator(&self) -> u8 {
self.separator
}
pub fn set_separator(&mut self, separator: u8) {
self.separator = separator;
}
}
impl Write for Output<'_> {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
self.maybe_flush();
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl Writable for u8 {
fn write(&self, output: &mut Output) {
output.put(*self);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable, const N: usize> Writable for [T; N] {
fn write(&self, output: &mut Output) {
output.print_iter(self.iter());
}
}
impl<T: Writable + ?Sized> Writable for &T {
fn write(&self, output: &mut Output) {
T::write(self, output)
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self.as_slice().write(output);
}
}
impl Writable for () {
fn write(&self, _output: &mut Output) {}
}
macro_rules! write_to_string {
($($t:ident)+) => {
$(impl Writable for $t { fn write(& self, output : & mut Output) { self
.to_string().write(output); } })+
};
}
write_to_string!(u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
macro_rules! tuple_writable {
($name0:ident $($name:ident : $id:tt)*) => {
impl <$name0 : Writable, $($name : Writable,)*> Writable for ($name0, $($name,)*)
{ fn write(& self, out : & mut Output) { self.0.write(out); $(out.put(out
.separator); self.$id .write(out);)* } }
};
}
tuple_writable! {
T
}
tuple_writable! {
T U : 1
}
tuple_writable! {
T U : 1 V : 2
}
tuple_writable! {
T U : 1 V : 2 X : 3
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6 B : 7
}
tuple_writable! {
T U : 1 V : 2 X : 3 Y : 4 Z : 5 A : 6 B : 7 C : 8
}
impl<T: Writable> Writable for Option<T> {
fn write(&self, output: &mut Output) {
match self {
None => (-1).write(output),
Some(t) => t.write(output),
}
}
}
impl Writable for bool {
fn write(&self, output: &mut Output) {
let bool_output = output.bool_output;
bool_output.output(output, *self)
}
}
impl<T: Writable> Writable for Reverse<T> {
fn write(&self, output: &mut Output) {
self.0.write(output);
}
}
static mut ERR: Option<Stderr> = None;
pub fn err() -> Output<'static> {
unsafe {
if ERR.is_none() {
ERR = Some(stderr());
}
Output::new_with_auto_flush(ERR.as_mut().unwrap())
}
}
}
}
pub mod misc {
pub mod direction {
#[derive(Copy, Clone)]
pub enum Direction {
Left,
Right,
}
}
pub mod random {
use crate::algo_lib::collections::slice_ext::indices::Indices;
use crate::algo_lib::misc::value_ref::ValueRef;
use crate::algo_lib::numbers::num_traits::algebra::IntegerSemiRingWithSub;
use crate::algo_lib::numbers::num_traits::ord::MinMax;
use crate::algo_lib::numbers::num_traits::primitive::Primitive;
use crate::value_ref;
use std::ops::{RangeBounds, Rem};
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self { mt: [0u64; NN], index: NN };
res.mt[0] = seed;
for i in 1..NN {
res.mt[i] = F
.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62))
.wrapping_add(i as u64);
}
res
}
fn gen_impl(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn gen<T>(&mut self) -> T
where
u64: Primitive<T>,
{
self.gen_impl().to()
}
pub fn gen_u128(&mut self) -> u128 {
(self.gen_impl() as u128) << 64 | self.gen_impl() as u128
}
pub fn gen_i128(&mut self) -> i128 {
self.gen_u128() as i128
}
pub fn gen_bool(&mut self) -> bool {
(self.gen_impl() & 1) == 1
}
pub fn gen_bound<T: Rem<Output = T> + Primitive<u64>>(&mut self, n: T) -> T
where
u64: Primitive<T>,
{
(self.gen_impl() % n.to()).to()
}
pub fn gen_range<T: IntegerSemiRingWithSub + Primitive<u64> + MinMax>(
&mut self,
range: impl RangeBounds<T>,
) -> T
where
u64: Primitive<T>,
{
let f = match range.start_bound() {
std::ops::Bound::Included(&s) => s,
std::ops::Bound::Excluded(&s) => s + T::one(),
std::ops::Bound::Unbounded => T::min_val(),
};
let t = match range.end_bound() {
std::ops::Bound::Included(&e) => e,
std::ops::Bound::Excluded(&e) => e - T::one(),
std::ops::Bound::Unbounded => T::max_val(),
};
if f == T::min_val() && t == T::max_val() {
self.gen()
} else {
f + self.gen_bound(t - f + T::one())
}
}
}
value_ref!(Rand : Random);
pub fn random() -> &'static mut Random {
if !Rand::is_init() {
Rand::set_val(
Random::new(
(SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos()
& 0xFFFFFFFFFFFFFFFF) as u64,
),
);
}
Rand::val_mut()
}
pub trait Shuffle {
fn shuffle(&mut self);
}
impl<T> Shuffle for [T] {
fn shuffle(&mut self) {
for i in self.indices() {
let at = random().gen_bound(i + 1);
self.swap(i, at);
}
}
}
}
pub mod recursive_function {
use std::marker::PhantomData;
macro_rules! recursive_function {
($name:ident, $trait:ident, ($($type:ident $arg:ident,)*)) => {
pub trait $trait <$($type,)* Output > { fn call(& mut self, $($arg : $type,)*) ->
Output; } pub struct $name < F, $($type,)* Output > where F : FnMut(& mut dyn
$trait <$($type,)* Output >, $($type,)*) -> Output, { f : std::cell::UnsafeCell <
F >, $($arg : PhantomData <$type >,)* phantom_output : PhantomData < Output >, }
impl < F, $($type,)* Output > $name < F, $($type,)* Output > where F : FnMut(&
mut dyn $trait <$($type,)* Output >, $($type,)*) -> Output, { pub fn new(f : F)
-> Self { Self { f : std::cell::UnsafeCell::new(f), $($arg :
Default::default(),)* phantom_output : Default::default(), } } } impl < F,
$($type,)* Output > $trait <$($type,)* Output > for $name < F, $($type,)* Output
> where F : FnMut(& mut dyn $trait <$($type,)* Output >, $($type,)*) -> Output, {
fn call(& mut self, $($arg : $type,)*) -> Output { unsafe { (* self.f.get())
(self, $($arg,)*) } } }
};
}
recursive_function!(RecursiveFunction0, Callable0, ());
recursive_function!(RecursiveFunction, Callable, (Arg arg,));
recursive_function!(RecursiveFunction2, Callable2, (Arg1 arg1, Arg2 arg2,));
recursive_function!(RecursiveFunction3, Callable3, (Arg1 arg1, Arg2 arg2, Arg3 arg3,));
recursive_function!(
RecursiveFunction4, Callable4, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4,)
);
recursive_function!(
RecursiveFunction5, Callable5, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5,)
);
recursive_function!(
RecursiveFunction6, Callable6, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6,)
);
recursive_function!(
RecursiveFunction7, Callable7, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6, Arg7 arg7,)
);
recursive_function!(
RecursiveFunction8, Callable8, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8,)
);
recursive_function!(
RecursiveFunction9, Callable9, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5
arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8, Arg9 arg9,)
);
}
pub mod test_type {
pub enum TestType {
Single,
MultiNumber,
MultiEof,
}
pub enum TaskType {
Classic,
Interactive,
}
}
pub mod value {
use std::hash::Hash;
pub trait Value<T>: Copy + Eq + Hash {
fn val() -> T;
}
pub trait ConstValue<T>: Value<T> {
const VAL: T;
}
impl<T, V: ConstValue<T>> Value<T> for V {
fn val() -> T {
Self::VAL
}
}
#[macro_export]
macro_rules! value {
($name:ident : $t:ty = $val:expr) => {
#[derive(Copy, Clone, Eq, PartialEq, Hash, Ord, PartialOrd, Default)] pub struct
$name {} impl $crate ::algo_lib::misc::value::ConstValue <$t > for $name { const
VAL : $t = $val; }
};
}
pub trait DynamicValue<T>: Value<T> {
fn set_val(t: T);
}
#[macro_export]
macro_rules! dynamic_value {
($name:ident : $t:ty) => {
#[allow(non_upper_case_globals)] static mut $name : Option <$t > = None;
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)] struct $name {} impl $crate
::algo_lib::misc::value::DynamicValue <$t > for $name { fn set_val(t : $t) {
unsafe { $name = Some(t); } } } impl $crate ::algo_lib::misc::value::Value <$t >
for $name { fn val() -> $t { unsafe { $name .unwrap() } } }
};
($name:ident : $t:ty = $val:expr) => {
dynamic_value!($name : $t); <$name as $crate
::algo_lib::misc::value::DynamicValue <$t >>::set_val($val);
};
}
}
pub mod value_ref {
pub trait ConstValueRef<T: ?Sized + 'static> {
fn val() -> &'static T;
}
pub trait ValueRef<T: 'static> {
fn val() -> &'static T;
fn set_val(t: T);
fn val_mut() -> &'static mut T;
fn is_init() -> bool;
}
#[macro_export]
macro_rules! const_value_ref {
($name:ident : $int_t:ty as $ext_t:ty = $base:expr) => {
#[allow(non_upper_case_globals)] const $name : $int_t = $base; #[derive(Copy,
Clone, Eq, PartialEq, Hash)] pub struct $name {} impl $crate
::algo_lib::misc::value_ref::ConstValueRef <$ext_t > for $name { fn val() ->
&'static $ext_t { &$name } }
};
($name:ident : $int_t:ty = $base:expr) => {
const_value_ref!($name : $int_t as $int_t = $base);
};
}
#[macro_export]
macro_rules! value_ref {
($name:ident : $t:ty) => {
#[allow(non_upper_case_globals)] static mut $name : Option <$t > = None;
#[derive(Copy, Clone, Eq, PartialEq, Hash)] struct $name {} impl $crate
::algo_lib::misc::value_ref::ValueRef <$t > for $name { fn val() -> &'static $t {
unsafe { $name .as_ref().unwrap() } } fn set_val(t : $t) { unsafe { $name =
Some(t); } } fn val_mut() -> &'static mut $t { unsafe { $name .as_mut().unwrap()
} } fn is_init() -> bool { unsafe { $name .is_some() } } }
};
($name:ident : $t:ty = $init_val:expr) => {
value_ref!($name : $t); <$name as $crate ::algo_lib::misc::value_ref::ValueRef
<$t >>::set_val($init_val);
};
}
}
pub mod when {
#[macro_export]
macro_rules! when {
{$($cond:expr => $then:expr,)*} => {
match () { $(_ if $cond => $then,)* _ => unreachable!(), }
};
{$($cond:expr => $then:expr,)* else $(=>)? $else:expr $(,)?} => {
match () { $(_ if $cond => $then,)* _ => $else, }
};
}
}
}
pub mod numbers {
pub mod gcd {
use crate::algo_lib::numbers::num_traits::algebra::{
IntegerMultiplicationMonoid, IntegerSemiRingWithSub, Zero,
};
use std::mem::swap;
pub fn extended_gcd<T: IntegerSemiRingWithSub + Copy>(a: T, b: T) -> (T, T, T) {
if a == T::zero() {
(b, T::zero(), T::one())
} else {
let (d, y, mut x) = extended_gcd(b % a, a);
x -= b / a * y;
(d, x, y)
}
}
pub fn gcd<T: Copy + Zero + IntegerMultiplicationMonoid>(mut a: T, mut b: T) -> T {
while b != T::zero() {
a %= b;
swap(&mut a, &mut b);
}
a
}
pub fn lcm<T: Copy + Zero + IntegerMultiplicationMonoid>(a: T, b: T) -> T {
(a / gcd(a, b)) * b
}
pub fn remainder<T: IntegerSemiRingWithSub + Copy>(
a1: T,
n1: T,
a2: T,
n2: T,
) -> Option<T> {
let (d, m1, m2) = extended_gcd(n1, n2);
if (a2 - a1) % d != T::zero() {
return None;
}
let m = lcm(n1, n2);
Some(((a1 * m2) % n1 * n2 + (a2 * m1) % n2 * n1) % m)
}
}
pub mod mod_int {
use crate::algo_lib::collections::fx_hash_map::FxHashMap;
use crate::algo_lib::io::input::{Input, Readable};
use crate::algo_lib::io::output::{Output, Writable};
use crate::algo_lib::misc::value::Value;
use crate::algo_lib::numbers::gcd::extended_gcd;
use crate::algo_lib::numbers::num_traits::algebra::{Field, One, Zero};
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use crate::{value, when};
use std::fmt::{Display, Formatter};
use std::hash::Hash;
use std::marker::PhantomData;
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
pub trait BaseModInt<T>: Field + Copy {
fn from(v: T) -> Self;
fn module() -> T;
fn value(&self) -> T;
}
macro_rules! mod_int {
($name:ident, $t:ty, $s:ty, $w:ty) => {
#[derive(Copy, Clone, Eq, PartialEq, Hash, Default)] pub struct $name < V : Value
<$t >> { n : $t, phantom : PhantomData < V >, } impl < V : Value <$t >> $name < V
> { unsafe fn unchecked_new(n : $t) -> Self { debug_assert!(n < V::val()); Self {
n, phantom : Default::default(), } } unsafe fn maybe_subtract_mod(mut n : $t) ->
$t { debug_assert!(n < 2 * V::val()); if n >= V::val() { n -= V::val(); } n } }
impl < V : Value <$t >> $name < V > { pub fn new(n : $t) -> Self { unsafe {
Self::unchecked_new(n % (V::val())) } } pub fn new_signed(n : $s) -> Self {
unsafe { Self::unchecked_new(Self::maybe_subtract_mod((n % (V::val() as $s) +
V::val() as $s) as $t,)) } } pub fn val(& self) -> $t { self.n } } impl < V :
Value <$t >> $name < V > { pub fn log(& self, alpha : Self) -> $t { let mut base
= FxHashMap::default(); let mut exp = 0; let mut pow = Self::one(); let mut inv =
* self; let alpha_inv = alpha.inv().unwrap(); while exp * exp < Self::module() {
if inv == Self::one() { return exp; } base.insert(inv, exp); exp += 1; pow *=
alpha; inv *= alpha_inv; } let step = pow; let mut i = 1; loop { if let Some(b) =
base.get(& pow) { break exp * i + * b; } pow *= step; i += 1; } } } impl < V :
Value <$t >> $name < V > { pub fn new_from_wide(n : $w) -> Self { unsafe {
Self::unchecked_new(Self::maybe_subtract_mod((n % V::val() as $w + V::val() as
$w) as $t,)) } } } impl < V : Value <$t >> Invertible for $name < V > { type
Output = Self; fn inv(& self) -> Option < Self > { let (g, x, _) =
extended_gcd(self.n as $w, V::val() as $w); if g != 1 { None } else {
Some(Self::new_from_wide(x)) } } } impl < V : Value <$t >> BaseModInt <$t > for
$name < V > { fn from(v : $t) -> Self { Self::new(v) } fn module() -> $t {
V::val() } fn value(& self) -> $t { self.n } } impl < V : Value <$t >> From <$t >
for $name < V > { fn from(n : $t) -> Self { Self::new(n) } } impl < V : Value <$t
>> AddAssign for $name < V > { fn add_assign(& mut self, rhs : Self) { self.n =
unsafe { Self::maybe_subtract_mod(self.n + rhs.n) }; } } impl < V : Value <$t >>
Add for $name < V > { type Output = Self; fn add(mut self, rhs : Self) ->
Self::Output { self += rhs; self } } impl < V : Value <$t >> SubAssign for $name
< V > { fn sub_assign(& mut self, rhs : Self) { self.n = unsafe {
Self::maybe_subtract_mod(self.n + V::val() - rhs.n) }; } } impl < V : Value <$t
>> Sub for $name < V > { type Output = Self; fn sub(mut self, rhs : Self) ->
Self::Output { self -= rhs; self } } impl < V : Value <$t >> MulAssign for $name
< V > { fn mul_assign(& mut self, rhs : Self) { self.n = ((self.n as $w) * (rhs.n
as $w) % (V::val() as $w)) as $t; } } impl < V : Value <$t >> Mul for $name < V >
{ type Output = Self; fn mul(mut self, rhs : Self) -> Self::Output { self *= rhs;
self } } impl < V : Value <$t >> DivAssign for $name < V > {
#[allow(clippy::suspicious_op_assign_impl)] fn div_assign(& mut self, rhs : Self)
{ * self *= rhs.inv().unwrap(); } } impl < V : Value <$t >> Div for $name < V > {
type Output = Self; fn div(mut self, rhs : Self) -> Self::Output { self /= rhs;
self } } impl < V : Value <$t >> Neg for $name < V > { type Output = Self; fn
neg(mut self) -> Self::Output { if self.n != 0 { self.n = V::val() - self.n; }
self } } impl < V : Value <$t >> Display for $name < V > { fn fmt(& self, f : &
mut Formatter <'_ >) -> std::fmt::Result { <$t as Display >::fmt(& self.n, f) } }
impl < V : Value <$t >> Readable for $name < V > { fn read(input : & mut Input)
-> Self { Self::new(input.read()) } } impl < V : Value <$t >> Writable for $name
< V > { fn write(& self, output : & mut Output) { self.n.write(output); } } impl
< V : Value <$t >> Zero for $name < V > { fn zero() -> Self { unsafe {
Self::unchecked_new(0) } } } impl < V : Value <$t >> One for $name < V > { fn
one() -> Self { Self::new(1) } } impl < V : Value <$t >> std::fmt::Debug for
$name < V > { fn fmt(& self, f : & mut Formatter) -> std::fmt::Result { let max =
100; when! { self.n <= max => write!(f, "{}", self.n), self.n >= V::val() - max
=> write!(f, "-{}", V::val() - self.n), else => { for denominator in 1..max { for
num in 1..max { if Self::new(num) / Self::new(denominator) == * self { return
write!(f, "{}/{}", num, denominator); } if - Self::new(num) /
Self::new(denominator) == * self { return write!(f, "-{}/{}", num, denominator);
} } } write!(f, "(?? {} ??)", self.n) }, } } } impl < V : Value <$t >> AsIndex
for $name < V > { fn from_index(idx : usize) -> Self { let v = idx as $w; if v >=
V::val() as $w { Self::new_from_wide(v) } else { unsafe { Self::unchecked_new(v
as $t) } } } fn to_index(self) -> usize { self.n.to_index() } }
};
}
mod_int!(ModInt, u32, i32, i64);
mod_int!(ModInt64, u64, i64, i128);
value!(Val7 : u32 = 1_000_000_007);
pub type ModInt7 = ModInt<Val7>;
value!(Val9 : u32 = 1_000_000_009);
pub type ModInt9 = ModInt<Val9>;
value!(ValF : u32 = 998_244_353);
pub type ModIntF = ModInt<ValF>;
}
pub mod num_traits {
pub mod algebra {
use crate::algo_lib::numbers::num_traits::invertible::Invertible;
use std::ops::{
Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Rem, RemAssign, Sub, SubAssign,
};
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
pub trait AdditionMonoid: Add<Output = Self> + AddAssign + Zero + Eq + Sized {}
impl<T: Add<Output = Self> + AddAssign + Zero + Eq> AdditionMonoid for T {}
pub trait AdditionMonoidWithSub: AdditionMonoid + Sub<Output = Self> + SubAssign {}
impl<T: AdditionMonoid + Sub<Output = Self> + SubAssign> AdditionMonoidWithSub for T {}
pub trait AdditionGroup: AdditionMonoidWithSub + Neg<Output = Self> {}
impl<T: AdditionMonoidWithSub + Neg<Output = Self>> AdditionGroup for T {}
pub trait MultiplicationMonoid: Mul<Output = Self> + MulAssign + One + Eq + Sized {}
impl<T: Mul<Output = Self> + MulAssign + One + Eq> MultiplicationMonoid for T {}
pub trait IntegerMultiplicationMonoid: MultiplicationMonoid + Div<
Output = Self,
> + Rem<Output = Self> + DivAssign + RemAssign {}
impl<
T: MultiplicationMonoid + Div<Output = Self> + Rem<Output = Self> + DivAssign
+ RemAssign,
> IntegerMultiplicationMonoid for T {}
pub trait MultiplicationGroup: MultiplicationMonoid + Div<
Output = Self,
> + DivAssign + Invertible<Output = Self> {}
impl<
T: MultiplicationMonoid + Div<Output = Self> + DivAssign + Invertible<Output = Self>,
> MultiplicationGroup for T {}
pub trait SemiRing: AdditionMonoid + MultiplicationMonoid {}
impl<T: AdditionMonoid + MultiplicationMonoid> SemiRing for T {}
pub trait SemiRingWithSub: AdditionMonoidWithSub + SemiRing {}
impl<T: AdditionMonoidWithSub + SemiRing> SemiRingWithSub for T {}
pub trait Ring: SemiRing + AdditionGroup {}
impl<T: SemiRing + AdditionGroup> Ring for T {}
pub trait IntegerSemiRing: SemiRing + IntegerMultiplicationMonoid {}
impl<T: SemiRing + IntegerMultiplicationMonoid> IntegerSemiRing for T {}
pub trait IntegerSemiRingWithSub: SemiRingWithSub + IntegerSemiRing {}
impl<T: SemiRingWithSub + IntegerSemiRing> IntegerSemiRingWithSub for T {}
pub trait IntegerRing: IntegerSemiRing + Ring {}
impl<T: IntegerSemiRing + Ring> IntegerRing for T {}
pub trait Field: Ring + MultiplicationGroup {}
impl<T: Ring + MultiplicationGroup> Field for T {}
macro_rules! zero_one_integer_impl {
($($t:ident)+) => {
$(impl Zero for $t { fn zero() -> Self { 0 } } impl One for $t { fn one() -> Self
{ 1 } })+
};
}
zero_one_integer_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod as_index {
pub trait AsIndex {
fn from_index(idx: usize) -> Self;
fn to_index(self) -> usize;
}
macro_rules! from_index_impl {
($($t:ident)+) => {
$(impl AsIndex for $t { fn from_index(idx : usize) -> Self { idx as $t } fn
to_index(self) -> usize { self as usize } })+
};
}
from_index_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod bit_ops {
use crate::algo_lib::numbers::num_traits::algebra::{One, Zero};
use std::ops::{
BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, RangeInclusive,
Shl, Sub,
};
use std::ops::{ShlAssign, Shr, ShrAssign};
pub trait BitOps: Copy + BitAnd<
Output = Self,
> + BitAndAssign + BitOr<
Output = Self,
> + BitOrAssign + BitXor<
Output = Self,
> + BitXorAssign + Not<
Output = Self,
> + Shl<
usize,
Output = Self,
> + ShlAssign<
usize,
> + Shr<usize, Output = Self> + ShrAssign<usize> + Zero + One + PartialEq {
#[inline]
fn bit(at: usize) -> Self {
Self::one() << at
}
#[inline]
fn is_set(&self, at: usize) -> bool {
(*self >> at & Self::one()) == Self::one()
}
#[inline]
fn set_bit(&mut self, at: usize) {
*self |= Self::bit(at);
}
#[inline]
fn unset_bit(&mut self, at: usize) {
*self &= !Self::bit(at);
}
#[must_use]
#[inline]
fn with_bit(mut self, at: usize) -> Self {
self.set_bit(at);
self
}
#[must_use]
#[inline]
fn without_bit(mut self, at: usize) -> Self {
self.unset_bit(at);
self
}
#[inline]
fn flip_bit(&mut self, at: usize) {
*self ^= Self::bit(at);
}
#[must_use]
#[inline]
fn flipped_bit(mut self, at: usize) -> Self {
self.flip_bit(at);
self
}
fn all_bits(n: usize) -> Self {
let mut res = Self::zero();
for i in 0..n {
res.set_bit(i);
}
res
}
fn iter_all(n: usize) -> RangeInclusive<Self> {
Self::zero()..=Self::all_bits(n)
}
}
pub struct BitIter<T> {
cur: T,
all: T,
ended: bool,
}
impl<T: Copy> BitIter<T> {
pub fn new(all: T) -> Self {
Self {
cur: all,
all,
ended: false,
}
}
}
impl<T: BitOps + Sub<Output = T>> Iterator for BitIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.ended {
return None;
}
let res = self.cur;
if self.cur == T::zero() {
self.ended = true;
} else {
self.cur = (self.cur - T::one()) & self.all;
}
Some(res)
}
}
impl<
T: Copy + BitAnd<Output = Self> + BitAndAssign + BitOr<Output = Self> + BitOrAssign
+ BitXor<Output = Self> + BitXorAssign + Not<Output = Self>
+ Shl<usize, Output = Self> + ShlAssign<usize> + Shr<usize, Output = Self>
+ ShrAssign<usize> + One + Zero + PartialEq,
> BitOps for T {}
pub trait Bits: BitOps {
fn bits() -> u32;
}
macro_rules! bits_integer_impl {
($($t:ident $bits:expr),+) => {
$(impl Bits for $t { fn bits() -> u32 { $bits } })+
};
}
bits_integer_impl!(
i128 128, i64 64, i32 32, i16 16, i8 8, isize 64, u128 128, u64 64, u32 32, u16 16,
u8 8, usize 64
);
}
pub mod invertible {
pub trait Invertible {
type Output;
fn inv(&self) -> Option<Self::Output>;
}
}
pub mod ord {
pub trait MinMax: PartialOrd {
fn min_val() -> Self;
fn max_val() -> Self;
}
macro_rules! min_max_integer_impl {
($($t:ident)+) => {
$(impl MinMax for $t { fn min_val() -> Self { std::$t ::MIN } fn max_val() ->
Self { std::$t ::MAX } })+
};
}
min_max_integer_impl!(i128 i64 i32 i16 i8 isize u128 u64 u32 u16 u8 usize);
}
pub mod primitive {
pub trait Primitive<T>: Copy {
fn to(self) -> T;
fn from(t: T) -> Self;
}
macro_rules! primitive_one {
($t:ident, $($u:ident)+) => {
$(impl Primitive <$u > for $t { fn to(self) -> $u { self as $u } fn from(t : $u)
-> Self { t as $t } })+
};
}
macro_rules! primitive {
($($t:ident)+) => {
$(primitive_one!($t, u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);)+
};
}
primitive!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
}
}
pub mod number_ext {
use crate::algo_lib::numbers::num_traits::algebra::{
IntegerSemiRing, MultiplicationMonoid,
};
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use std::ops::Mul;
pub trait Power {
#[must_use]
fn power<T: IntegerSemiRing + Copy>(&self, exp: T) -> Self;
}
impl<S: MultiplicationMonoid + Copy> Power for S {
fn power<T: IntegerSemiRing + Copy>(&self, exp: T) -> Self {
if exp == T::zero() {
S::one()
} else {
let mut res = self.power(exp / (T::one() + T::one()));
res *= res;
if exp % (T::one() + T::one()) == T::one() {
res *= *self;
}
res
}
}
}
pub fn num_digs<S: IntegerSemiRing + AsIndex + Copy>(mut copy: S) -> usize {
let ten = S::from_index(10);
let mut res = 0;
while copy != S::zero() {
copy /= ten;
res += 1;
}
res
}
pub fn sum_digs<S: IntegerSemiRing + AsIndex + Copy>(mut copy: S) -> S {
let ten = S::from_index(10);
let mut res = S::zero();
while copy != S::zero() {
res += copy % ten;
copy /= ten;
}
res
}
pub fn digits<S: IntegerSemiRing + AsIndex + Copy>(
mut copy: S,
) -> impl Iterator<Item = S> {
let ten = S::from_index(10);
std::iter::from_fn(move || {
if copy == S::zero() {
None
} else {
let res = copy % ten;
copy /= ten;
Some(res)
}
})
}
pub trait Square {
fn square(self) -> Self;
}
impl<T: Mul<Output = T> + Copy> Square for T {
fn square(self) -> Self {
self * self
}
}
}
pub mod primes {
pub mod factorize {
use crate::algo_lib::collections::vec_ext::sorted::Sorted;
use crate::algo_lib::misc::recursive_function::{Callable2, RecursiveFunction2};
use crate::algo_lib::numbers::num_traits::algebra::MultiplicationMonoid;
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
use crate::algo_lib::numbers::num_traits::primitive::Primitive;
use crate::algo_lib::numbers::primes::prime::find_divisor;
use crate::algo_lib::numbers::primes::sieve::divisor_table;
use std::cmp::Ordering;
pub trait Factorize {
fn prime_divisors(self) -> Vec<(u64, usize)>;
fn divisors(self) -> Vec<u64>;
fn max_power(self, p: Self) -> usize;
}
impl<T: Primitive<u64>> Factorize for T {
fn prime_divisors(self) -> Vec<(u64, usize)> {
let n = self.to();
assert!(n >= 1);
if n == 1 {
return Vec::new();
}
let d = if n > 100 {
find_divisor(n)
} else {
let mut res = n;
let mut i = 2;
while i * i <= n {
if n % i == 0 {
res = i;
break;
}
i += 1;
}
res
};
if d == n {
return vec![(d, 1)];
}
let left = d.prime_divisors();
let right = (n / d).prime_divisors();
let mut res = Vec::new();
let mut i = 0;
let mut j = 0;
while i < left.len() && j < right.len() {
match left[i].0.cmp(&right[j].0) {
Ordering::Less => {
res.push(left[i]);
i += 1;
}
Ordering::Equal => {
res.push((left[i].0, left[i].1 + right[j].1));
i += 1;
j += 1;
}
Ordering::Greater => {
res.push(right[j]);
j += 1;
}
}
}
res.extend_from_slice(&left[i..]);
res.extend_from_slice(&right[j..]);
res
}
fn divisors(self) -> Vec<u64> {
let pd = self.prime_divisors();
let mut res = Vec::new();
let mut rec = RecursiveFunction2::new(|f, mut d: u64, step: usize| {
if step == pd.len() {
res.push(d);
} else {
let (p, e) = pd[step];
for i in 0..=e {
f.call(d, step + 1);
if i < e {
d *= p;
}
}
}
});
rec.call(1, 0);
res.sorted()
}
fn max_power(self, p: Self) -> usize {
let mut res = 0;
let mut cur = self.to();
assert!(cur >= 1);
let p = p.to();
assert!(p >= 2);
while cur % p == 0 {
cur /= p;
res += 1;
}
res
}
}
pub fn all_divisors<T: AsIndex + PartialEq + Copy + MultiplicationMonoid + Ord>(
n: usize,
sorted: bool,
) -> Vec<Vec<T>> {
let d: Vec<T> = divisor_table(n);
let mut res = Vec::with_capacity(n);
if n > 0 {
res.push(Vec::new());
}
if n > 1 {
res.push(vec![T::from_index(1)]);
}
for (i, p) in d.into_iter().enumerate().skip(2) {
let mut q = 0;
let mut c = i;
while c % p.to_index() == 0 {
c /= p.to_index();
q += 1;
}
let mut cur = Vec::with_capacity(res[c].len() * (q + 1));
let mut by = T::from_index(1);
for j in 0..=q {
cur.extend(res[c].iter().map(|&x| x * by));
if j != q {
by *= p;
}
}
if sorted {
cur.sort();
}
res.push(cur);
}
res
}
}
pub mod prime {
use crate::algo_lib::misc::random::random;
use crate::algo_lib::numbers::gcd::gcd;
use crate::algo_lib::numbers::mod_int::ModInt64;
use crate::algo_lib::numbers::num_traits::algebra::{One, Zero};
use crate::algo_lib::numbers::num_traits::primitive::Primitive;
use crate::algo_lib::numbers::number_ext::Power;
use crate::{dynamic_value, when};
pub fn is_prime(n: impl Primitive<u64>) -> bool {
let n = n.to();
if n <= 1 {
return false;
}
let mut s = 0;
let mut d = n - 1;
while d % 2 == 0 {
s += 1;
d >>= 1;
}
if s == 0 {
return n == 2;
}
dynamic_value!(IsPrimeModule : u64 = n);
type Mod = ModInt64<IsPrimeModule>;
for _ in 0..20 {
let a = Mod::new(random().gen_bound(n));
if a == Mod::zero() {
continue;
}
if a.power(d) == Mod::one() {
continue;
}
let mut dd = d;
let mut good = true;
for _ in 0..s {
if a.power(dd) == -Mod::one() {
good = false;
break;
}
dd *= 2;
}
if good {
return false;
}
}
true
}
pub fn next_prime(mut n: u64) -> u64 {
if n <= 2 {
return 2;
}
n += 1 - (n & 1);
while !is_prime(n) {
n += 2;
}
n
}
fn brent(n: u64, x0: u64, c: u64) -> u64 {
dynamic_value!(ModVal : u64 = n);
type Mod = ModInt64<ModVal>;
let mut x = Mod::new(x0);
let c = Mod::new(c);
let mut g = 1;
let mut q = Mod::one();
let mut xs = Mod::zero();
let mut y = Mod::zero();
let m = 128i64;
let mut l = 1;
while g == 1 {
y = x;
for _ in 1..l {
x = x * x + c;
}
let mut k = 0;
while k < l && g == 1 {
xs = x;
for _ in 0..m.min(l - k) {
x = x * x + c;
q *= y - x;
}
g = gcd(q.val(), n);
k += m;
}
l *= 2;
}
if g == n {
loop {
xs = xs * xs + c;
g = gcd((xs - y).val(), n);
if g != 1 {
break;
}
}
}
g
}
pub fn find_divisor(n: u64) -> u64 {
when! {
n == 1 => 1, n % 2 == 0 => 2, is_prime(n) => n, else => { loop { let res =
brent(n, random().gen_range(2..n), random().gen_range(1..n),); if res != n {
return res; } } },
}
}
}
pub mod sieve {
use crate::algo_lib::collections::bit_set::BitSet;
use crate::algo_lib::numbers::num_traits::as_index::AsIndex;
pub fn primality_table(n: usize) -> BitSet {
let mut res = BitSet::new(n);
res.fill(true);
if n > 0 {
res.unset(0);
}
if n > 1 {
res.unset(1);
}
let mut i = 2;
while i * i < n {
if res[i] {
for j in ((i * i)..n).step_by(i) {
res.unset(j);
}
}
i += 1;
}
res
}
pub fn primes<T: AsIndex>(n: usize) -> Vec<T> {
primality_table(n).into_iter().map(|i| T::from_index(i)).collect()
}
pub fn divisor_table<T: AsIndex + PartialEq>(n: usize) -> Vec<T> {
let mut res: Vec<_> = (0..n).map(|i| T::from_index(i)).collect();
let mut i = 2;
while i * i < n {
if res[i] == T::from_index(i) {
for j in ((i * i)..n).step_by(i) {
res[j] = T::from_index(i);
}
}
i += 1;
}
res
}
}
}
}
pub mod string {
pub mod str {
use crate::algo_lib::io::input::{Input, Readable};
use crate::algo_lib::io::output::{Output, Writable};
use std::fmt::Display;
use std::io::Write;
use std::iter::FromIterator;
use std::ops::{AddAssign, Deref, DerefMut};
use std::str::from_utf8_unchecked;
use std::vec::IntoIter;
#[derive(Eq, PartialEq, Hash, PartialOrd, Ord, Clone, Default)]
pub struct Str(Vec<u8>);
impl Str {
pub fn new() -> Self {
Self(Vec::new())
}
pub fn unwrap(self) -> Vec<u8> {
self.0
}
}
impl From<Vec<u8>> for Str {
fn from(v: Vec<u8>) -> Self {
Self(v)
}
}
impl From<&[u8]> for Str {
fn from(v: &[u8]) -> Self {
Self(v.to_vec())
}
}
impl<const N: usize> From<&[u8; N]> for Str {
fn from(v: &[u8; N]) -> Self {
Self(v.to_vec())
}
}
impl Readable for Str {
fn read(input: &mut Input) -> Self {
let mut res = Vec::new();
input.skip_whitespace();
while let Some(c) = input.get() {
if c.is_ascii_whitespace() {
break;
}
res.push(c);
}
Self(res)
}
}
impl Writable for Str {
fn write(&self, output: &mut Output) {
output.write_all(&self.0).unwrap()
}
}
impl Deref for Str {
type Target = Vec<u8>;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl DerefMut for Str {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl IntoIterator for Str {
type Item = u8;
type IntoIter = IntoIter<u8>;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
}
impl<'a> IntoIterator for &'a Str {
type Item = &'a u8;
type IntoIter = std::slice::Iter<'a, u8>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a> IntoIterator for &'a mut Str {
type Item = &'a mut u8;
type IntoIter = std::slice::IterMut<'a, u8>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl FromIterator<u8> for Str {
fn from_iter<T: IntoIterator<Item = u8>>(iter: T) -> Self {
Self(iter.into_iter().collect())
}
}
impl AsRef<[u8]> for Str {
fn as_ref(&self) -> &[u8] {
&self.0
}
}
impl AddAssign<&[u8]> for Str {
fn add_assign(&mut self, rhs: &[u8]) {
self.0.extend_from_slice(rhs)
}
}
impl Display for Str {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
unsafe { f.write_str(from_utf8_unchecked(&self.0)) }
}
}
pub trait StrReader {
fn read_str(&mut self) -> Str;
fn read_str_vec(&mut self, n: usize) -> Vec<Str>;
fn read_line(&mut self) -> Str;
fn read_line_vec(&mut self, n: usize) -> Vec<Str>;
fn read_lines(&mut self) -> Vec<Str>;
}
impl StrReader for Input<'_> {
fn read_str(&mut self) -> Str {
self.read()
}
fn read_str_vec(&mut self, n: usize) -> Vec<Str> {
self.read_vec(n)
}
fn read_line(&mut self) -> Str {
let mut res = Str::new();
while let Some(c) = self.get() {
if self.is_eol() {
break;
}
res.push(c);
}
res
}
fn read_line_vec(&mut self, n: usize) -> Vec<Str> {
let mut res = Vec::with_capacity(n);
for _ in 0..n {
res.push(self.read_line());
}
res
}
fn read_lines(&mut self) -> Vec<Str> {
let mut res = Vec::new();
while !self.is_exhausted() {
res.push(self.read_line());
}
if let Some(s) = res.last() {
if s.is_empty() {
res.pop();
}
}
res
}
}
}
}
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2308kb
input:
2 5 aa ab ab ac d 1 aaaaa
output:
2 6 1 9 8 5
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 2264kb
input:
10 10 bba bbaaaabbbaaabaabbbaaaaaababaababbb b baaabbaab babbb bbbbbaaaaababbabbabbb bbaaaabbabb b aaaaabab abbbabbabab 10 abb ab bbaaaba bbabbabba bbbabbbababaaaab b aaaa babababbb ab a 2 aaaaabbaabbbbbababbbbbaabababbbaaababbbaaaaabbbaabaabababbaababbabbabbaababbbbbabbbabaaabbbabab abbaaaaaaaabbaa...
output:
3 35 35 32 60 75 76 67 75 120 3 1 8 31 41 40 43 55 58 54 95 146 32 38 39 41 51 79 79 70 70 112 3 22 47 90 91 117 129 146 157 40 53 62 63 12 46 51 51 83 111 99 113 126 106 10 45 48 49 89 12 22 28 37 61 67 70 123 102 118 50
result:
ok 71 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 2600kb
input:
100 6 baaaab aadabdbdadabbbbcda ccbc b dccaddba da 7 aad dababba addbdbbbbdabdaadacbabadabdcccbdccabadbbddddaaaddbdbcaa abcddd c bddcc ca 9 daadbbcaa bacbdbaab bcbaba acbcbd ac b bddcddcdccacdcbbccaccdbc dabbdccabb accbbbc 12 bcbdabba ac b cdbbaa cdaa bddac bbacbcaacbbbbbaa b dadcbd bcc bbbdbcdacbbb...
output:
6 24 28 31 39 35 3 10 66 71 70 77 73 9 18 26 28 38 36 54 72 75 8 10 9 19 19 31 37 33 59 57 73 82 9 23 33 39 70 68 15 81 19 182 241 252 262 306 321 352 14 26 24 37 33 38 51 48 57 105 112 116 40 1 0 22 54 126 64 120 125 17 28 51 66 103 104 131 1 13 19 29 31 47 47 45 62 61 71 69 226 10 21 20 51 52 60 6...
result:
ok 698 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 2448kb
input:
100 1 aaabbbbaaabbabbaabbababababab 12 abb a bbab b aaabbabaaabbbba bb baba bb a aba abaabb bb 7 aa aaabaabbaabbaabaaaaaaabbabbaabbb bbaaabaaaaaababbababbbaabbbbabbbaabbaabaaabbbaaababaaaaaabbabaaaabbaab aaabbbaaaabaaabababbaabaaabbbbbbbaabaabbbaabbbbbbaaabb abababbbabbabaaabaabbbbbbaaa ababaaababab...
output:
29 3 6 10 13 31 26 20 32 47 35 49 32 2 38 108 144 178 248 253 12 28 40 84 125 107 134 143 174 230 211 221 1 0 7 9 12 13 10 14 19 20 38 42 1 5 11 10 10 7 19 23 11 16 18 29 85 112 97 233 1 4 7 4 0 25 31 39 50 57 56 56 3 7 11 11 13 0 26 27 7 8 6 54 40 72 108 136 151 159 157 153 200 246 201 197 208 5 9 ...
result:
ok 711 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 2576kb
input:
100 5 bababccabcacccb ccaabaa ccbaacbabbacc bcbcbccbcababbcccccabc baaaac 8 c abcabbbcc cacbcbbbbaabbabacb cbb a c acccbaacabbccbca aa 1 baccaababccabbaaaaccbacaabbababbabcbcbcbbccaccbccbcabbababcbbccacccccbacaccaaabbaaaacbccbcaaacbaaccccbaccbcbabbbcccaababbaabbcbcacacacaaacbcccaaaabaccccb 7 abacacb...
output:
15 22 39 63 52 1 10 30 30 39 32 53 53 153 24 36 58 94 91 116 127 12 53 112 137 226 301 4 6 12 20 17 16 41 43 63 32 32 32 3 1 3 1 2 22 32 38 37 33 52 209 6 9 43 46 43 55 61 82 90 111 114 117 150 225 267 279 3 7 14 29 28 54 52 75 82 98 125 143 1 4 7 3 15 1 1 5 7 9 13 20 18 17 31 35 40 56 19 58 4 24 56...
result:
ok 686 numbers
Test #6:
score: 0
Accepted
time: 448ms
memory: 842504kb
input:
1 10 cabaabaabbcabaaaacabbcbabaababaccaccacaacccaaaababccbbcaaccaabcbccccccccbbcbbccbccbbbbccabbbcccbcaabbbbbacabcccbbaaabaaabbcabaaacacaaabbcaacacaabcccbccacababbbacbbacabccbcaabccabaccabbbbaaacacabcbbcacabcabcbaccbacbbbabbabcaaaaccbbacccaccaaccaabccacbbcbbacccacbabbccaacccbcaabacbcaccaacccccaccbab...
output:
111956 186203 269128 465829 642491 700512 757152 903532 903751 1000006
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 416ms
memory: 892840kb
input:
1 1 bccbaaaabcccbbabccbabaccbbbabcabaaaacacbcccacbcbccbcbabbabaacbaacaccbcbacccaaaaacbbbbacbcbabaccbbccbcabbababacaaabacbbcaacccababbcacaacbbaabacabcababaabacabbacabbcbbcabbbcbccaaaabccaaaacccaccbaaccabbccbabbcbbabcacaaacbbcabcbccacbcaabcccaabbcbbabbbbbcabbccaacbabbcccbbcaaacbacabbabacaacacabcbaaccc...
output:
1000000
result:
ok 1 number(s): "1000000"
Test #8:
score: 0
Accepted
time: 348ms
memory: 23180kb
input:
100 2666 g sn lat e h ktpo j pckf e ovn qe naudp ysm munzjl usb zcwgny eyaafhgtey kunpaieisjlh cvorcc q se s rgg isby rlod f cyiuczytnk vgc vg fkuk e hqg n o du cdz kouhklg fgfhaj tzu j x k ju t m qw v h f y bhi y yx rem oo b h dljurs gxalmvnt ckjqwc gupriva k k tosk mtdn iyuc s o en sf fxygl cpq ui...
output:
1 3 6 7 8 12 13 17 16 23 21 30 29 39 42 44 57 67 77 78 70 64 95 91 85 86 110 109 127 121 120 101 104 107 109 111 109 148 153 158 157 146 137 180 183 174 160 162 167 164 169 173 189 135 188 191 190 182 176 184 176 182 186 193 216 214 219 228 233 242 238 236 236 210 174 175 173 179 188 177 164 161 166...
result:
ok 500000 numbers
Test #9:
score: 0
Accepted
time: 321ms
memory: 39644kb
input:
100 313 jybrvzxmxx wbeszgdzcuvyaxybiradklnjflfwrvucidrimtkbslbktydammrlrhnvbtpxqnobugenqtiuojgehrbsauxeoootfpycll hknzullaxnsueunohbzcegxkqremeqmircnkgubfdjdgprekbbudukasholtnvkfvcqgwemopmiqrgjkvgrlsfqrbmqmtzbkbcahoxikkkznobtozeekrtgvezteegflqhpmrdwcewftemdimviryq muwwzhqalmjaryahqsh gv ykmsxddeddhu...
output:
10 104 254 273 275 296 368 411 473 516 530 590 597 611 617 637 658 675 721 744 737 829 832 891 889 901 956 1020 993 1048 1046 1096 1122 1277 1269 1305 1335 1375 1420 1468 1575 1542 1617 1600 1717 1685 1691 1673 1790 1745 1841 1800 1813 1811 1913 1958 2044 1988 2078 2183 2224 2181 2302 2268 2250 2317...
result:
ok 10000 numbers
Test #10:
score: 0
Accepted
time: 439ms
memory: 19164kb
input:
100 7218 a a bca a c cab cc a b bc c acb a a cb ac c b ab bcbb b ab b cb a cc b c a b a a a a c b c a a aba a c b cc a c b a cc c a b c b c cc b c ca b bcb cb bbc c a c cb ac bc a c b b b b ca b b b a ca c a b a a c bca a b b a c b ab a c c a b cc b ab bca b cba b cba b b b a aaa bab b bb caab a b a...
output:
1 0 7 7 6 13 14 9 4 23 28 28 28 24 25 11 5 28 10 52 40 59 49 38 44 14 11 18 20 35 49 57 61 42 50 6 24 8 49 44 4 38 18 102 78 84 104 118 117 74 82 110 94 12 41 1 53 13 70 69 41 3 28 34 40 6 90 107 127 121 35 57 33 57 81 75 121 6 112 8 113 109 9 117 81 43 113 4 28 112 10 77 147 241 202 154 249 139 171...
result:
ok 500000 numbers
Test #11:
score: 0
Accepted
time: 472ms
memory: 6436kb
input:
1 10000 ixmutxgrmqaslccwrrnjlgucmqplaxwlzcqijgxsvxfiqffnlfqcjdbeyw ixmutxgrmqaslccwrrnjlguc fivqhrcivctlqjsthgwarppzvufxmaasdibagfrapsmghhkftyqpagvwhxhqnnhiyhyvhvyptny fivqhrcivctlqjsthgwarppzvufxmaasdibagfrapsmghhkftyqpagvwhxhqnnhiyhyvhvyptnyxbzvphukkyfruzlabxdhiugbhsxdgdyunlqehyybgxknfkgnvdruszxom...
output:
58 98 173 368 312 867 586 214 374 1003 1019 1601 395 203 891 1398 1148 1282 451 461 57 3727 2087 3014 978 128 315 986 801 585 814 3842 3132 3924 2248 654 3731 3302 3310 2195 2767 7827 3836 676 6983 4203 7256 7234 3353 2974 3272 2968 413 1990 1656 6285 3696 3370 3767 3449 3137 6205 5763 5027 4643 570...
result:
ok 10000 numbers
Test #12:
score: 0
Accepted
time: 1473ms
memory: 112392kb
input:
1 500000 a abb a ab a b abbba bba abbb b ab b b bbaab a a bb bb abb b a b abb ab bb bbaa bbaabbb bb bb abb ab bb ab bb abb bba ab bba abbba b bbaa bb ab a b abbb b a b bba b a bb bb b a ab bbaabbba abbbaa b bba b bb ab ab a a a ab bbaabb a b a abb ab abbb bba a b ab ab ab bb a a a a a abb b bb b a b...
output:
1 6 4 6 12 13 10 19 5 5 10 17 23 11 58 44 42 0 27 4 0 28 8 25 59 14 42 27 118 95 40 53 17 41 124 85 125 83 9 55 126 72 108 30 8 87 113 31 0 62 84 113 17 6 38 4 84 184 62 3 17 47 239 191 15 47 154 238 202 170 242 214 181 43 117 219 125 121 49 100 210 96 32 58 14 12 36 26 215 173 230 156 161 83 119 11...
result:
ok 500000 numbers
Test #13:
score: 0
Accepted
time: 1548ms
memory: 109736kb
input:
1 500000 w wyh w wyh w w w w w w w w w w w wyh w w w w wy wyh wyh w wy w w w w w w wyh wyhsqdu w w w wyh wyh w wy wyh wyhs wyh w wyh w wy w w wy w w w w wy w wy wyh wyh wy w w wyhsqduyu w w w wyhsqd w w wy w wyh wyhs wyh wy w wyh wyhsq w wyhsqd w w w wyh w wyhsq wyh wyh wyh w w w w wy wyh wyh wyhs w...
output:
1 6 4 7 3 1 7 2 5 1 11 13 1 7 15 2 18 5 23 15 10 15 19 17 58 50 36 28 0 58 36 12 45 33 29 50 37 46 58 92 100 63 47 65 110 96 92 70 9 31 69 69 113 19 41 83 23 47 41 5 55 47 63 52 92 92 104 96 58 90 226 138 92 44 20 236 226 6 74 129 228 192 146 106 220 250 79 87 215 219 183 97 31 25 89 137 130 62 6 14...
result:
ok 500000 numbers
Test #14:
score: 0
Accepted
time: 898ms
memory: 211668kb
input:
1 500000 ek zir qh wot yy tif lbxj kfj phv dca sbgzzi auhtj l y w f y hu zwbz j oxcl ny ogg oq whv n g y q t mjrw zr bh gnd qff gtcy x t j t qx g tg b pkievl f z sb ebx f i po cg wi w nq qiu c mrr yqr uoxjvh e s xj q ez u a inr ef mo c qorkbp i c g n mqrc pw n by b acvjb z eco is pwiiui k m nebfzp u...
output:
2 5 7 10 12 15 19 22 25 28 34 39 42 45 44 45 41 43 57 56 60 50 53 50 66 71 70 71 88 89 85 86 84 77 75 90 91 95 92 89 93 70 125 124 72 75 74 64 65 83 82 83 85 93 93 90 88 89 184 166 168 150 148 148 150 142 131 128 131 128 143 137 180 170 149 149 238 236 236 214 215 200 214 220 218 222 167 164 184 183...
result:
ok 500000 numbers
Test #15:
score: 0
Accepted
time: 1525ms
memory: 110768kb
input:
1 500000 a aaaaaa a aaaaaaa aa a a a a aa a a aaa aaa aaaaa aa aaa a a aaaa aa aa aa a aa a a aa a aaa a a aa aa a a aaaaaaa a a aaaa a aaa a a aa a a a aa aa aa aa aaaaa aa aa aa a a aaaa aa aaaa aa aa a a aaaa a a a a a aaa aa aa aa a aaaaa aaa aaa a aa aa a a a aaaa a a aaa aa a aaa a aaa a a aa ...
output:
1 5 9 6 24 12 10 11 6 1 5 19 3 28 46 24 43 52 38 35 7 29 27 17 16 52 16 36 56 122 100 37 57 54 24 39 48 16 38 40 2 104 64 48 6 20 58 100 55 2 15 27 37 99 67 119 63 107 82 1 108 188 128 61 69 124 60 154 194 160 228 30 50 42 234 164 96 77 139 51 14 204 158 202 90 126 22 118 186 154 246 227 157 122 34 ...
result:
ok 500000 numbers
Test #16:
score: 0
Accepted
time: 1365ms
memory: 112900kb
input:
1 500000 bb b aab baaaaab a b a aa bbb aaa ba b ababa aab bb ba b b a bb aa bbb bbb a ab bab b b bb b ab aa bbab b a b b a aa abba b a a babbba abaabb a a a babbaba ba a b a a b a ba aabbaaabba b a a b ab a b a a a ab a bb a aa ba b ba aba a ba ba a abab aaba a bbb b ab a a a a bba a abb a a a bb aa...
output:
2 1 4 12 9 14 20 22 18 31 2 4 52 62 63 62 60 54 47 12 11 22 50 36 57 63 32 54 51 33 101 123 70 102 126 90 76 80 119 42 14 3 55 56 14 70 118 72 126 110 32 124 79 125 99 75 0 24 248 222 242 209 233 248 254 228 212 232 227 199 174 150 217 154 255 235 206 230 242 144 18 207 145 215 2 120 48 0 124 87 26 ...
result:
ok 500000 numbers
Test #17:
score: 0
Accepted
time: 1262ms
memory: 116228kb
input:
1 500000 a cacbc a abb c caac ca c c ab c a a cbc c cacb b ba b bc b cbc b ab ba bacb bcc ba b a ab b acc bba bb cb cbb c bc aaab cc a baa c b c caba cba bc cbbb a b b a bb a bcb c bcb c ca a acb a aaa aaa a bcccc c cb b b cbb aaccb aba b c bb a aaab c c bcaa a a ac ba c ba cb a bbbbb cb abb acac c ...
output:
1 6 5 11 12 15 20 18 18 28 24 22 14 3 16 55 54 50 50 54 44 22 2 14 21 22 53 40 52 29 17 31 109 99 110 118 114 32 10 33 60 52 16 33 49 1 50 27 71 11 57 13 95 99 97 85 82 98 99 67 49 62 44 47 193 211 251 150 216 201 236 224 171 143 238 250 162 71 69 46 112 106 71 53 79 5 83 255 245 216 178 34 95 204 2...
result:
ok 500000 numbers
Test #18:
score: 0
Accepted
time: 1092ms
memory: 136320kb
input:
1 500000 g dbg cd f c agd gb e ga daf be e fgcf dbc a gd c ec d cc dd g c e de e b cbf d eg b g g d f a gg d dd abgaa c d e agbd d gdea be fgbgcba a geefb ba ecdffggg a e ac bg eag c d g fcb a a e e b ea cag bdacdc ddd fdbcb fcag eggb g g af ed f f g bcd ffbegb eg cf a bbg ggb dd cc f f fce e d g ag...
output:
1 4 6 7 10 9 9 10 23 22 16 29 19 23 22 50 60 59 50 50 57 55 49 46 35 59 56 52 50 47 33 23 17 30 24 38 50 61 72 75 83 89 95 90 108 120 122 115 77 83 90 34 28 15 43 62 48 53 57 39 55 14 62 14 4 14 229 234 226 243 147 156 137 193 253 246 253 204 213 167 172 199 188 181 207 185 179 152 159 235 235 198 1...
result:
ok 500000 numbers
Test #19:
score: 0
Accepted
time: 508ms
memory: 545084kb
input:
1 50000 bbaaabccccaccccabaaacbcaaacbaabcacaaacababbacbab ccbcccac baacacbccccabcaabaacbcca bbcbac b aacbaabaaaacbcbacacababcb cbacbcaa aabacaaabcbcacacaababbcbccabcacccbcccacccb caccaababbbaacccccabbbbcabaccbbcaabaabbba bcccaacaccaacacbabababcccb cabaab baaabbabb bcbcabcbcb bbbccbaacaacaaacccbaaacc ...
output:
48 56 82 81 86 113 119 169 197 238 240 224 227 256 263 297 359 343 443 423 388 420 439 436 517 572 608 707 758 663 874 769 798 775 820 854 889 908 951 955 945 905 946 995 1067 1118 1277 1027 1131 1083 1061 1085 1504 1412 1467 1420 1530 1290 1324 1332 1313 1315 1442 1526 1288 1399 1359 1351 1706 1711...
result:
ok 50000 numbers
Test #20:
score: 0
Accepted
time: 423ms
memory: 826312kb
input:
1 1000 acaabbaacbabaaaabbaabccacbaccbccabbabcaccbbcccccbcccaabaccacacabccaccbcbcbabcbbccabbcaccabaccacbccbcabacaabacbbaccabcacaaaacaccacbaacbbcccbaccaabbcacbcbaabbabcccbccaabbcabaacabcaabbbbacabcaabcbacbcabbccbabaacbbabcbcacbcbccaaaacbbbacabaabacbcbbbabbbaacbccacbcbacacbbcccaaaabcbbccabacbbcacacbcba...
output:
832 1182 2257 3299 3986 4154 4436 5137 5562 7648 10623 11237 12834 13880 14875 15656 16734 18761 19205 19264 21555 22987 23301 26164 27008 27305 27305 27430 28630 29004 29727 29728 32370 34301 36150 37383 39875 44249 44418 44485 45131 47396 48601 49171 49926 50205 50858 56027 56519 56932 57597 58278...
result:
ok 1000 numbers
Test #21:
score: 0
Accepted
time: 433ms
memory: 832808kb
input:
1 100 aabaaabaccbbcbbbbccaccbacabcbcacacaaaacabacbccbbbbbcbacacccbacacaaacbcaacaacaaaabbacacabcbbcbcaacccacbbababbbacabbaabbbaccbcacbccbbacccbaacaabaacabccaaabbcccbabbabbbacaaaaabbaccabbccaabccbcbcabbbcbcccccbbbacabbbabcacbacacbbaaacbbcaccbaccabbacacabcacbbbccabaaaabaaabaaacaacbacbbabaabaccbabbbabab...
output:
10907 24690 24925 27831 29645 30516 32060 38841 42360 59515 74170 87061 89952 104051 104949 114934 116678 138432 143457 157476 163562 186507 192288 213365 214992 219153 234223 234339 236150 236757 242704 251475 274891 297117 297170 327086 331542 332174 335011 340475 355194 366067 384977 385910 38900...
result:
ok 100 numbers
Test #22:
score: 0
Accepted
time: 302ms
memory: 4516kb
input:
1000 119 a chuuiwmegwxqbfa jn o s g ou qc x f g fohs ydra lqkgvy wbktjw x d sp npzie wb r y scq t fh dr gty g dt csgnspxd r b vrhv n dbxnb on r grxcy f a wu qxfv xlfr hlf st wk lfnbr p cd cb nkjxmrf ocd ofpx gbma yq pcp w hka y c ueyhzkc e b pthy i awyj cpe d lq tuonk q z d zg myf vytrymoc v yrlwht ...
output:
1 16 18 19 20 21 21 27 24 25 24 38 34 44 54 57 58 62 51 53 50 45 83 82 85 81 83 80 87 77 68 69 73 72 71 122 100 100 109 82 87 81 64 69 81 85 94 161 160 168 162 165 182 137 130 159 157 156 153 131 138 139 138 141 140 157 155 151 134 135 133 250 226 158 155 145 159 130 133 136 130 130 251 249 243 248 ...
result:
ok 500000 numbers
Test #23:
score: 0
Accepted
time: 362ms
memory: 671192kb
input:
1 10 cbccaabccccbcacabcbabccbbcabccababcacbcccbbbcaaacbbabacbaccbaacaaacaacbbbcccbaabaacaaaabbccbaaabbaccabaabbccbccbbccccaacccabaaaacbcacbbbcabaaacbcacccabaaaacbbabaabbbcbcabccbacacccacacabcbcaacbacaaacaabbcbbbaccbacaccaabcaccbcaccacbabbaaacbcbababacbbbbaacccccabbbccbcabacacbbcbcbccccaaccacacacbcbb...
output:
175567 375672 398651 458361 523768 615270 740617 713810 892506 609528
result:
ok 10 numbers
Test #24:
score: 0
Accepted
time: 146ms
memory: 45900kb
input:
1 1000 ekbrqzyvkquppdhstpqrhezgjgxmgszbvyhrqsrtotakdofkovvaiipdmcrhnnytxqmnvqfjuyubjpfkrpqvksoeaactawjuvjvkubqpdshxqhiitlstbspynsgldqsgjowudethlerlqmjkxkltvbknkigfmdkialccodgbwlheqvbfeyjolrbjnvguhnfblamjopkanswupimwbguqoadghddehjhhtmiroevhtnewknamqfdyggntnarscjpakbazfjccxytmgfwgextfyldbrlfsfmldbdmvg...
output:
1021 1145 1862 2097 2165 3240 3396 5650 5572 9175 9418 8650 12182 11638 9105 15001 9180 11210 23039 26541 26641 26185 26097 25721 24913 32483 32751 24998 27791 20975 20627 23374 23510 18923 24300 19445 11146 8510 52760 49584 55126 52783 52874 63119 41866 45451 48127 39290 40842 34254 34118 26407 105...
result:
ok 1000 numbers
Test #25:
score: 0
Accepted
time: 367ms
memory: 848808kb
input:
1 3 dlpgdecvbohsqgkcpeqsrpdrvsmxljufrwbvlkkgriqtihflgisjzlzuqhblxbvqxolkfuhxynbuyucdzjiabzairhomlqvjykvubjmnwkbxavvuushgzocodubbizwzufgyafrjnevutwxzyincfpbwyrekcbkexyosehyltraojjksyzbbztpnjkxfkwqwtzjozctiefmwueexzcesqqvggjcflcdrmibwuorgbdahabyqsryocxdgfdeoeadrbhqgsoxiubyoexmtjmgbhyfougpubuagzeeifwzy...
output:
29089 952718 930596
result:
ok 3 number(s): "29089 952718 930596"
Test #26:
score: 0
Accepted
time: 207ms
memory: 241240kb
input:
1 1000 yepqmqsvgaszygxrmambahgxmgjceccpyjdrjibaxymoewupdvgdbkrzcejduvrsujuxzfdinirntgednelohbvnwtdjnjmgyiftlvdjphguowyvyahzdgnlfqdjdpllxoqyaqajybpsdgwjurkwogfklfvnmjphuoypxddtxwtedhxkhtwiisrktgvkkqyopiykewbxmlbmeixymjmgkxtjalmmkpqsjehwfeahsahoeeewrllnfhvhocynpbihrsgeqknbsffwxxluqdwoplqjhtltjtrtdkval...
output:
383 920 4022 5103 7328 7466 8645 10597 11005 15853 14421 14726 14049 14190 13557 12369 20061 19394 23753 22939 22564 18987 20379 19479 17122 16527 16714 32738 32239 30663 30022 27079 26536 24679 40622 38310 38359 38110 38428 37602 36242 35261 47759 33358 33500 35551 35369 35298 40485 38510 61006 602...
result:
ok 1000 numbers
Test #27:
score: 0
Accepted
time: 333ms
memory: 2220kb
input:
100000 2 q xf 5 u y m w sff 1 wpfit 1 zocnzcloxsfa 6 s l ry d f jy 5 f g kd r t 6 gx b f h x w 1 ysob 6 djj k b p j r 7 hp bsk rd f p pieulmra vvh 9 sd r n l luj ku r az ja 9 x t k d l qz o x x 2 u fbn 3 rslm i n 6 sm l c n a i 1 pycv 1 flklcr 2 eg mztdy 12 t m t z c t y pk q i r t 12 v z hn eo u tz...
output:
1 3 1 2 3 4 7 5 12 1 2 4 5 6 8 1 2 4 5 6 2 3 4 5 6 7 4 3 4 5 6 7 8 2 5 7 8 9 19 22 2 3 4 5 10 8 15 9 11 1 2 3 4 5 7 8 11 11 1 4 4 5 6 2 3 4 5 6 7 4 6 2 7 1 2 1 6 7 7 6 8 11 10 13 14 1 2 4 6 7 11 15 12 19 17 18 31 2 3 4 2 5 1 3 4 6 7 9 3 5 6 7 8 9 10 1 3 4 6 8 1 2 3 5 2 3 4 2 4 5 3 6 7 4 10 11 8 13 1...
result:
ok 500000 numbers
Extra Test:
score: 0
Extra Test Passed