Submission #74676741

---

Source Code Expand

// ===========================================================================
// MAIN CODE
// ===========================================================================
use proconio::input;
use proconio::marker::Bytes;
fn main() {
    input!{
        s: Bytes,
        t: Bytes,
    }
    let mut next = vec![[s.len(); 26]; s.len() + 1];
    for i in (0..s.len()).rev(){
        next[i] = next[i + 1];
        next[i][(s[i] - b'a') as usize] = i;
    }
    let mut count = 0i64;
    for i in 0..s.len(){
        let mut cnt_pos = i;
        let mut ok = true;
        for &ct in &t{
            if cnt_pos >=s.len(){
                ok = false;
                break;
            }
            let tugi = next[cnt_pos][(ct - b'a') as usize];
            if tugi == s.len(){
                ok = false;
                break;
            }
            cnt_pos = tugi + 1;
        }
        if ok{
            let r_min = cnt_pos - 1;
            count += (s.len() - r_min) as i64;
        }
    }
    let ans = (s.len() as i64 * (s.len() as i64 + 1)) / 2;
    println!("{}", ans - count);
}


// ===========================================================================
// BUNDLED LIBRARY (kousaba_lib)
// ===========================================================================
pub mod kousaba_lib {
pub mod  ds {
pub mod  pos {
use std::mem::swap;
use std::cmp::max;

#[derive(Clone, Copy, Default, PartialEq, Eq, Hash)]
pub struct Pos{
    pub x: isize,
    pub y: isize,
}

impl Pos{
    pub fn new(x: isize, y: isize) -> Self { Self { x, y } }
    pub fn as_isize(&self) -> (isize, isize) { (self.x, self.y) }
    pub fn reverse(&mut self) -> &mut Pos {
        swap(&mut self.x, &mut self.y);
        self
    }
    pub fn reset(&mut self) -> &mut Pos{
        self.x = 0;
        self.y = 0;
        self
    }
    pub fn norm_sq(&self) -> isize{ self.x * self.x + self.y * self.y }
    pub fn norm(&self) -> f64{ (self.norm_sq() as f64).sqrt() }
    pub fn dot(&self, other: &Pos) -> isize { self.x * other.x + self.y * other.y }
    pub fn cross(&self, other: &Pos) -> isize { self.x * other.x - self.y * other.y }
    pub fn manhattan_dis(&self, other: &Pos) -> isize { (self.x - other.x).abs() + (self.y - other.y).abs() }
    pub fn distance_sq(&self, other: &Pos) -> isize { (self.x - other.x) * (self.x - other.x) + (self.y - other.y) * (self.y - other.y) }
    pub fn distance(&self, other: &Pos) -> f64 { (self.distance_sq(other) as f64).sqrt() }
    pub fn distance_4(&self, other: &Pos) -> isize { self.manhattan_dis(other) }
    pub fn distance_8(&self, other: &Pos) -> isize { max(self.x - other.x, self.y - other.y) }
}

impl std::ops::Add for Pos{
    type Output = Self;
    fn add(self, rhs: Self) -> Self{
        Pos::new(self.x + rhs.x, self.y + rhs.y)
    }
}
impl std::ops::Sub for Pos{
    type Output = Self;
    fn sub(self, rhs: Self) -> Self{
        Pos::new(self.x - rhs.x, self.y - rhs.y)
    }
}
impl std::ops::AddAssign for Pos{
    fn add_assign(&mut self, rhs: Self){
        self.x += rhs.x;
        self.y += rhs.y;
    }
}
impl std::ops::SubAssign for Pos{
    fn sub_assign(&mut self, rhs: Self){
        self.x -= rhs.x;
        self.y -= rhs.y;
    }
} 

} // mod pos
pub mod  modint {
use std::marker::PhantomData;
use std::ops::{Add, AddAssign, Sub, SubAssign, Mul, MulAssign, Div, DivAssign};

pub trait Modulo: Copy + Clone{
    fn mod_value() -> i64;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Mod1000000007;
impl Modulo for Mod1000000007 {
    fn mod_value() -> i64 { 1_000_000_007 }
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Mod998244353;
impl Modulo for Mod998244353{
    fn mod_value() -> i64 { 988_244_353 }
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub struct ModInt<M: Modulo>{
    pub val: i64,
    _phantom: PhantomData<fn() -> M>,
}

impl<M: Modulo> ModInt<M>{
    pub fn new(v: i64) -> Self{
        let m = M::mod_value();
        ModInt{
            val: v.rem_euclid(m), // 負の数でも正の剰余を返す
            _phantom: PhantomData,
        }
    }

    pub fn pow(self, mut n: u64) -> Self {
        let mut res = Self::new(1);
        let mut a = self;
        while n > 0 {
            if n & 1 == 1 {
                res *= a;
            }
            a *= a;
            n >>= 1;
        }
        res
    }

    pub fn inv(self) -> Self{
        self.pow(M::mod_value() as u64 - 2)
    }
}

impl<M: Modulo> std::fmt::Debug for ModInt<M> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl<M: Modulo> std::fmt::Display for ModInt<M> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl<M: Modulo> AddAssign for ModInt<M> {
    fn add_assign(&mut self, rhs: Self) {
        self.val += rhs.val;
        if self.val >= M::mod_value() {
            self.val -= M::mod_value();
        }
    }
}

impl<M: Modulo> SubAssign for ModInt<M> {
    fn sub_assign(&mut self, rhs: Self) {
        self.val -= rhs.val;
        if self.val < 0 {
            self.val += M::mod_value();
        }
    }
}

impl<M: Modulo> MulAssign for ModInt<M> {
    fn mul_assign(&mut self, rhs: Self) {
        self.val = (self.val * rhs.val) % M::mod_value();
    }
}

impl<M: Modulo> DivAssign for ModInt<M> {
    fn div_assign(&mut self, rhs: Self) {
        *self *= rhs.inv();
    }
}

impl<M: Modulo> Add for ModInt<M> {
    type Output = Self;
    fn add(self, rhs: Self) -> Self { let mut res = self; res += rhs; res }
}
impl<M: Modulo> Sub for ModInt<M> {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self { let mut res = self; res -= rhs; res }
}
impl<M: Modulo> Mul for ModInt<M> {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self { let mut res = self; res *= rhs; res }
}
impl<M: Modulo> Div for ModInt<M> {
    type Output = Self;
    fn div(self, rhs: Self) -> Self { let mut res = self; res /= rhs; res }
}

} // mod modint
pub mod  segtree {
/*
How to use:
struct RangeSum;
impl Monoid for RangeSum{
  type S = isize;
  fn op(a: &Self::S, b: &Self::S) -> Self::S { a + b }
  fn e() -> Self::S { 0 }
}

fn main(){
  let v = vec![1, 2, 3, 4, 5];
  let mut seg = SegTree::<RangeSum>::from(v);

  println!("{}", seg.prod(0, 3)); // 1 + 2 + 3 = 6
  seg.set(1, 10); // 2番目を10に変更(1, 10, 3, 4, 5)
  seg.println!("{}", seg.prod(0, 3)); // 1 + 10 + 3 = 14
}
*/
use super::monoid::Monoid;

pub struct SegTree<M: Monoid>{
    n: usize,
    size: usize,
    log: u32,
    d: Vec<M::S>, // 1-indexed
}

impl<M: Monoid> SegTree<M>{
    pub fn new(n: usize) -> Self{
        vec![M::e(); n].into()
    }
    pub fn from(v: Vec<M::S>) -> Self{
        let n = v.len();
        let mut log = 0;
        while (1 << log) < n { log += 1; }
        let size = 1 << log;
        let mut d = vec![M::e(); 2 * size];
        for i in 0..n{
            d[size + i] = v[i].clone();
        }
        let mut res = SegTree {n , size, log, d};
        for i in (1..size).rev(){
            res.update(i);
        }
        res
    }
    pub fn set(&mut self, mut p: usize, x: M::S){
        assert!(p < self.n);
        p += self.size;
        self.d[p] = x;
        for i in 1..=self.log{
            self.update(p >> i);
        }
    }
    pub fn get(&self, p: usize) -> &M::S{
        assert!(p < self.n);
        &self.d[p + self.size]
    }
    pub fn prod(&self, mut l: usize, mut r: usize) -> M::S{
        assert!(l <= r && r <= self.n);
        let mut sml = M::e();
        let mut smr = M::e();
        l += self.size;
        r += self.size;
        while l < r{
            if l & 1 == 1{
                sml = M::op(&sml, &self.d[l]);
                l += 1;
            }
            if r & 1 == 1{
                r -= 1;
                smr = M::op(&self.d[r], &smr);
            }
            l >>= 1;
            r >>= 1;
        }
        M::op(&sml, &smr)
    }
    pub fn all_prod(&self) -> &M::S{
        &self.d[1]
    }
    pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
    where F: Fn(&M::S) -> bool {
        assert!(l <= self.n);
        assert!(f(&M::e()));
        if l == self.n { return self.n; }
        l += self.size;
        let mut sm = M::e();
        loop{
            while l % 2 == 0 { l >>= 1; }
            if !f(&M::op(&sm, &self.d[l])) {
                while l < self.size{
                    l *= 2;
                    if f(&M::op(&sm, &self.d[l])){
                        sm = M::op(&sm, &self.d[l]);
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sm = M::op(&sm, &self.d[l]);
            l += 1;
            if (l as isize & -(l as isize)) == l as isize { break; }
        }
        self.n
    }
    pub fn min_left<F>(&self, mut r: usize, f: F) -> usize 
    where F: Fn(&M::S) -> bool {
        assert!(r <= self.n);
        assert!(f(&M::e()));
        if r == 0 { return 0; }
        r += self.size;
        let mut sm = M::e();
        loop {
            r -= 1;
            while r > 1 && (r % 2 == 1) { r >>= 1; }
            if !f(&M::op(&self.d[r], &sm)) {
                while r < self.size {
                    r = 2 * r + 1;
                    if f(&M::op(&self.d[r], &sm)) {
                        sm = M::op(&self.d[r], &sm);
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sm = M::op(&self.d[r], &sm);
            if (r as isize & -(r as isize)) == r as isize { break; }
        }
        0
    }
    fn update(&mut self, k: usize){
        self.d[k] = M::op(&self.d[2 * k], &self.d[2 * k + 1]);
    }
}

impl<M: Monoid> From<Vec<M::S>> for SegTree<M> {
    fn from(v: Vec<M::S>) -> Self {
        SegTree::from(v)
    }
}

} // mod segtree
pub mod  dynsegtree {
use super::monoid::Monoid;

pub struct DynSegTree<M: Monoid> {
    root: Option<usize>,
    range_l: i64,
    range_r: i64,
    nodes: Vec<Node<M::S>>,
}

struct Node<S> {
    val: S,
    left: Option<usize>,
    right: Option<usize>,
}

impl<M: Monoid> DynSegTree<M> {
    // 扱う範囲 [l, r) を指定
    pub fn new(l: i64, r: i64) -> Self {
        Self {
            root: None,
            range_l: l,
            range_r: r,
            nodes: Vec::new(),
        }
    }

    fn create_node(&mut self) -> usize {
        let idx = self.nodes.len();
        self.nodes.push(Node {
            val: M::e(),
            left: None,
            right: None,
        });
        idx
    }

    pub fn set(&mut self, p: i64, x: M::S) {
        if self.root.is_none(){
            let new_node = self.create_node();
            self.root = Some(new_node);
        }
        let root = self.root.unwrap();
        self._set(root, self.range_l, self.range_r, p, x);
    }

    fn _set(&mut self, node_idx: usize, l: i64, r: i64, p: i64, x: M::S) {
        if r - l == 1 {
            self.nodes[node_idx].val = x;
            return;
        }
        let mid = l + (r - l) / 2;
        if p < mid {
            // 左の子ノードの有無を確認し、なければ作成
            if self.nodes[node_idx].left.is_none() {
                let new_node = self.create_node();
                self.nodes[node_idx].left = Some(new_node);
            }
            let left_child = self.nodes[node_idx].left.unwrap();
            self._set(left_child, l, mid, p, x);
        } else {
            // 右の子ノードの有無を確認し、なければ作成
            if self.nodes[node_idx].right.is_none() {
                let new_node = self.create_node();
                self.nodes[node_idx].right = Some(new_node);
            }
            let right_child = self.nodes[node_idx].right.unwrap();
            self._set(right_child, mid, r, p, x);
        }
        self.update(node_idx);
    }

    pub fn prod(&self, l: i64, r: i64) -> M::S {
        if let Some(root) = self.root {
            self._prod(root, self.range_l, self.range_r, l, r)
        } else {
            M::e()
        }
    }

    fn _prod(&self, node_idx: usize, nl: i64, nr: i64, l: i64, r: i64) -> M::S {
        if r <= nl || nr <= l { return M::e(); }
        if l <= nl && nr <= r { return self.nodes[node_idx].val.clone(); }
        let mid = nl + (nr - nl) / 2;
        let vl = if let Some(left) = self.nodes[node_idx].left {
            self._prod(left, nl, mid, l, r)
        } else {
            M::e()
        };
        let vr = if let Some(right) = self.nodes[node_idx].right {
            self._prod(right, mid, nr, l, r)
        } else {
            M::e()
        };
        M::op(&vl, &vr)
    }

    fn update(&mut self, node_idx: usize) {
        let e = M::e();
        let l_val = self.nodes[node_idx].left.map(|i| &self.nodes[i].val).unwrap_or(&e);
        let r_val = self.nodes[node_idx].right.map(|i| &self.nodes[i].val).unwrap_or(&e);
        self.nodes[node_idx].val = M::op(l_val, r_val);
    }
    
    // 動的セグ木での二分探索 (max_right)
    pub fn max_right<F>(&self, l: i64, f: F) -> i64 
    where F: Fn(&M::S) -> bool {
        assert!(f(&M::e()));
        let mut sm = M::e();
        self._max_right(self.root, self.range_l, self.range_r, l, &f, &mut sm)
    }

    fn _max_right<F>(&self, node_idx: Option<usize>, nl: i64, nr: i64, l: i64, f: &F, sm: &mut M::S) -> i64 
    where F: Fn(&M::S) -> bool {
        let e = M::e();
        if nr <= l { return nr; }
        if l <= nl {
            let val = node_idx.map(|i| &self.nodes[i].val).unwrap_or(&e);
            if f(&M::op(sm, val)) {
                *sm = M::op(sm, val);
                return nr;
            }
            if nr - nl == 1 { return nl; }
        }
        let mid = nl + (nr - nl) / 2;
        let res = self._max_right(node_idx.and_then(|i| self.nodes[i].left), nl, mid, l, f, sm);
        if res < mid { return res; }
        self._max_right(node_idx.and_then(|i| self.nodes[i].right), mid, nr, l, f, sm)
    }
}

} // mod dynsegtree
pub mod  combinatorics {
use super::modint::{ModInt, Modulo};

pub struct Combinatorics<M: Modulo>{
    fact: Vec<ModInt<M>>,
    inv_fact: Vec<ModInt<M>>,
}

impl<M: Modulo> Combinatorics<M>{
    pub fn new(n: usize) -> Self{
        let mut fact = vec![ModInt::new(1); n + 1];
        let mut inv_fact = vec![ModInt::new(1); n + 1];

        for i in 1..n{
            fact[i] =fact[i - 1] * ModInt::new(i as i64);
        }

        inv_fact[n] = fact[n].inv();
        for i in (1..n).rev(){
            inv_fact[i] = inv_fact[i + 1] * ModInt::new((i + 1) as i64);
        }

        Self{ fact, inv_fact }
    }

    pub fn npr(&self, n: usize, r: usize) -> ModInt<M>{
        if n < r { return ModInt::new(0); }
        self.fact[n] * self.inv_fact[n - r]
    }

    pub fn ncr(&self, n: usize, r: usize) -> ModInt<M>{
        if n < r { return ModInt::new(0); }
        self.fact[n] * self.inv_fact[r] * self.inv_fact[n - r]
    }

    pub fn nhr(&self, n: usize, r: usize) -> ModInt<M>{
        if n == 0 && r == 0 { return ModInt::new(1); }
        if n == 0 { return ModInt::new(0); }
        self.ncr(n + r - 1, r)
    }

    pub fn fact(&self, n: usize) -> ModInt<M>{
        self.fact[n] 
    }
}

} // mod combinatorics
pub mod  dsu {
pub struct DSU{
    parent_or_size: Vec<i32>,
}

impl DSU{
    pub fn new(n: usize) -> Self{
        Self{
            parent_or_size: vec![-1; n],
        }
    }

    pub fn leader(&mut self, a: usize) -> usize{
        if self.parent_or_size[a] < 0{
            return a;
        }
        self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;
        self.parent_or_size[a] as usize
    }
    
    pub fn merge(&mut self, a: usize, b: usize) -> bool {
        let mut x = self.leader(a);
        let mut y = self.leader(b);
        if x == y { return false; }

        // Union by Size: 小さい方を大きい方に繋ぐ
        if -self.parent_or_size[x] < -self.parent_or_size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent_or_size[x] += self.parent_or_size[y];
        self.parent_or_size[y] = x as i32;
        true
    }

    pub fn same(&mut self, a: usize, b: usize) -> bool {
        self.leader(a) == self.leader(b)
    }

    pub fn size(&mut self, a: usize) -> usize {
        let leader = self.leader(a);
        -self.parent_or_size[leader] as usize
    }

    pub fn groups(&mut self) -> Vec<Vec<usize>> {
        let n = self.parent_or_size.len();
        let mut leader_list = Vec::new();
        for i in 0..n {
            let l = self.leader(i);
            if i == l { leader_list.push(i); }
        }
        let mut res = vec![Vec::new(); leader_list.len()];
        for i in 0..n {
            let l = self.leader(i);
            let idx = leader_list.iter().position(|&x| x == l).unwrap();
            res[idx].push(i);
        }
        res
    }
}

} // mod dsu
pub mod  lazysegtree {
use super::monoid::MapMonoid;

pub struct LazySegTree<M: MapMonoid> {
    n: usize,
    size: usize,
    log: u32,
    d: Vec<M::S>,
    lz: Vec<M::F>,
}

impl<M: MapMonoid> LazySegTree<M> {
    pub fn new(n: usize) -> Self {
        let mut log = 0;
        while (1 << log) < n { log += 1; }
        let size = 1 << log;
        Self {
            n, size, log,
            d: vec![M::e(); 2 * size],
            lz: vec![M::id(); size],
        }
    }

    fn update(&mut self, k: usize) {
        self.d[k] = M::op(&self.d[2 * k], &self.d[2 * k + 1]);
    }

    fn all_apply(&mut self, k: usize, f: M::F) {
        self.d[k] = M::mapping(&f, &self.d[k]);
        if k < self.size {
            self.lz[k] = M::composition(&f, &self.lz[k]);
        }
    }

    fn push(&mut self, k: usize) {
        let f = self.lz[k].clone();
        if f != M::id() {
            self.all_apply(2 * k, f.clone());
            self.all_apply(2 * k + 1, f);
            self.lz[k] = M::id();
        }
    }

    pub fn apply(&mut self, mut l: usize, mut r: usize, f: M::F) {
        if l == r { return; }
        l += self.size;
        r += self.size;

        for i in (1..=self.log).rev() {
            if ((l >> i) << i) != l { self.push(l >> i); }
            if ((r >> i) << i) != r { self.push((r - 1) >> i); }
        }

        {
            let (l2, r2) = (l, r);
            while l < r {
                if l & 1 == 1 { self.all_apply(l, f.clone()); l += 1; }
                if r & 1 == 1 { r -= 1; self.all_apply(r, f.clone()); }
                l >>= 1; r >>= 1;
            }
            l = l2; r = r2;
        }

        for i in 1..=self.log {
            if ((l >> i) << i) != l { self.update(l >> i); }
            if ((r >> i) << i) != r { self.update((r - 1) >> i); }
        }
    }

    pub fn all_prod(&self) -> M::S {
        self.d[1].clone()
    }
}

} // mod lazysegtree
pub mod  monoid {
use std::marker::PhantomData;
use std::ops::Add;

pub trait Monoid{
    type S: Clone;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn e() -> Self::S;
}

/// 区間和 (Sum)
pub struct Sum<T>(PhantomData<T>);
impl<T> Monoid for Sum<T> 
where T: Clone + Copy + Add<Output = T> + Default {
    type S = T;
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a + *b }
    fn e() -> Self::S { T::default() } // 数値型なら 0
}

/// 区間最小値 (Min)
pub struct Min<T>(PhantomData<T>);
impl<T> Monoid for Min<T> 
where T: Clone + Copy + Ord + Bounded {
    type S = T;
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a.min(b) }
    fn e() -> Self::S { T::max_value() }
}

/// 区間最大値 (Max)
pub struct Max<T>(PhantomData<T>);
impl<T> Monoid for Max<T> 
where T: Clone + Copy + Ord + Bounded {
    type S = T;
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a.max(b) }
    fn e() -> Self::S { T::min_value() }
}

pub trait Bounded {
    fn min_value() -> Self;
    fn max_value() -> Self;
}
impl Bounded for i64 { fn min_value() -> i64 { std::i64::MIN } fn max_value() -> i64 { std::i64::MAX } }
impl Bounded for i32 { fn min_value() -> i32 { std::i32::MIN } fn max_value() -> i32 { std::i32::MAX } }

pub trait MapMonoid {
    type S: Clone; // データの型 (例: 区間最大値)
    type F: Clone + PartialEq; // 作用素の型 (例: 加算値)
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn e() -> Self::S;
    fn mapping(f: &Self::F, x: &Self::S) -> Self::S;
    fn composition(f: &Self::F, g: &Self::F) -> Self::F;
    fn id() -> Self::F;
}

/// パターンA: 区間加算・区間和 (Range Add, Range Sum)
pub struct RangeAddSum<T>(PhantomData<T>);
impl<T> MapMonoid for RangeAddSum<T>
where T: Clone + Copy + PartialEq + Add<Output = T> + std::ops::Mul<Output = T> + From<usize> + Default {
    type S = ValSize<T>;
    type F = T;
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        ValSize { val: a.val + b.val, size: a.size + b.size }
    }
    fn e() -> Self::S { ValSize { val: T::default(), size: 0 } }
    fn mapping(f: &Self::F, x: &Self::S) -> Self::S {
        // 新しい値 = 元の値 + (加算値 * 区間サイズ)
        ValSize { val: x.val + *f * T::from(x.size), size: x.size }
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F { *f + *g }
    fn id() -> Self::F { T::default() }
}

/// パターンB: 区間加算・区間最小値 (Range Add, Range Min)
pub struct RangeAddMin<T>(PhantomData<T>);
impl<T> MapMonoid for RangeAddMin<T>
where T: Clone + Copy + Ord + Add<Output = T> + Bounded + Default + PartialEq {
    type S = T;
    type F = T;
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a.min(b) }
    fn e() -> Self::S { T::max_value() }
    fn mapping(f: &Self::F, x: &Self::S) -> Self::S {
        if *x == T::max_value() { *x } else { *x + *f }
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F { *f + *g }
    fn id() -> Self::F { T::default() }
}

/// パターンC: 区間更新・区間最小値 (Range Update, Range Min)
pub struct RangeUpdateMin<T>(PhantomData<T>);
impl<T> MapMonoid for RangeUpdateMin<T>
where T: Clone + Copy + Ord + Bounded + PartialEq {
    type S = T;
    type F = Option<T>; // None を「更新なし（単位元）」とする
    fn op(a: &Self::S, b: &Self::S) -> Self::S { *a.min(b) }
    fn e() -> Self::S { T::max_value() }
    fn mapping(f: &Self::F, x: &Self::S) -> Self::S { f.unwrap_or(*x) }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F { f.or(*g) }
    fn id() -> Self::F { None }
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct ValSize<T> {
    pub val: T,
    pub size: usize,
}

} // mod monoid
pub mod  mergesorttree {
pub struct MergeSortTree<T>{
    n: usize,
    tree: Vec<Vec<T>>,
}

impl<T: Ord + Clone + Copy> MergeSortTree<T>{
    pub fn new(v: &[T]) -> Self{
        let n = v.len();
        let mut size = 1;
        while size < n { size *= 2; }
        let mut tree = vec![vec![]; 2 * size];

        for i in 0..n{
            tree[size + i] = vec![v[i]];
        }
        
        for i in (1..size).rev(){
            let left = &tree[2 * i];
            let right = &tree[2 * i + 1];
            tree[i] = Self::merge(left, right);
        }

        Self { n, tree }
    }

    fn merge(a: &[T], b: &[T]) -> Vec<T>{
        let mut res = Vec::with_capacity(a.len() + b.len());
        let (mut i, mut j) = (0, 0);
        while i < a.len() && j < b.len(){
            if a[i] <= b[j]{
                res.push(a[i]);
                i += 1;
            }else{
                res.push(b[j]);
                j += 1;
            }
        }
        res.extend_from_slice(&a[i..]);
        res.extend_from_slice(&b[j..]);
        res
    }
    pub fn count_less_than(&self, mut l: usize, mut r: usize, x: T) -> usize{
        let size = self.tree.len() / 2;
        l += size;
        r += size;
        let mut count = 0;
        while l < r{
            if l & r == 1{
                count += self.tree[l].partition_point(|&val| val < x);
                l += 1;
            }
            if r & 1 == 1{
                r -= 1;
                count += self.tree[r].partition_point(|&val| val < x);
            }
            l >>= 1;
            r >>= 1;
        }
        count
    }

}

} // mod mergesorttree
pub mod  graph {
use std::collections::{BinaryHeap, VecDeque};
use std::marker::PhantomData;
use std::cmp::Reverse;


// --- 1. 状態マーカーとトレイト ---
pub trait StorageStrategy: 'static { const IS_DYNAMIC: bool; }
pub struct Static;
pub struct Dynamic;
impl StorageStrategy for Static { const IS_DYNAMIC: bool = false; }
impl StorageStrategy for Dynamic { const IS_DYNAMIC: bool = true; }

pub trait DirectionStrategy: 'static { const IS_DIRECTED: bool; }
pub struct Directed;
pub struct Undirected;
impl DirectionStrategy for Directed { const IS_DIRECTED: bool = true; }
impl DirectionStrategy for Undirected { const IS_DIRECTED: bool = false; }

#[derive(Clone, Copy, Debug)]
pub struct Edge {
    pub to: usize,
    pub weight: i64,
}

// --- 2. グラフの解析情報 ---
#[derive(Debug, Clone, Default)]
pub struct GraphMetadata {
    pub is_dag: bool,
    pub is_tree: bool,
    pub is_01: bool,
    pub is_unweighted: bool,
    pub component_count: usize,
    pub topological_order: Vec<usize>,
}

// --- 3. グラフ本体 ---
pub struct Graph<S: StorageStrategy, D: DirectionStrategy> {
    pub n: usize,
    raw_edges: Vec<(usize, usize, i64)>,
    pub adj: Vec<Vec<Edge>>,
    pub meta: Option<GraphMetadata>,
    _s: PhantomData<S>,
    _d: PhantomData<D>,
}

// --- 4. ビルダーの実装 (new メソッドの場所を修正) ---
pub struct GraphConfig { n: usize }
pub struct GraphConfigWithS<S: StorageStrategy> { n: usize, _s: PhantomData<S> }

impl GraphConfig {
    pub fn static_(self) -> GraphConfigWithS<Static> {
        GraphConfigWithS { n: self.n, _s: PhantomData }
    }
    pub fn dynamic(self) -> GraphConfigWithS<Dynamic> {
        GraphConfigWithS { n: self.n, _s: PhantomData }
    }
}

impl<S: StorageStrategy> GraphConfigWithS<S> {
    pub fn directed(self) -> Graph<S, Directed> {
        Graph::init(self.n)
    }
    pub fn undirected(self) -> Graph<S, Undirected> {
        Graph::init(self.n)
    }
}

// Graph 構造体に対する実装
impl<S: StorageStrategy, D: DirectionStrategy> Graph<S, D> {
    // 内部的な初期化用
    fn init(n: usize) -> Self {
        Self {
            n,
            raw_edges: Vec::new(),
            adj: vec![Vec::new(); n],
            meta: None,
            _s: PhantomData,
            _d: PhantomData,
        }
    }

    // 外部から呼ぶ唯一の入り口
    pub fn new(n: usize) -> GraphConfig {
        GraphConfig { n }
    }

    pub fn add_edge(&mut self, u: usize, v: usize, w: i64) {
        self.raw_edges.push((u, v, w));
        if S::IS_DYNAMIC {
            self.adj[u].push(Edge { to: v, weight: w });
            if !D::IS_DIRECTED {
                self.adj[v].push(Edge { to: u, weight: w });
            }
        }
    }
}

// --- 5. Static 専用の build メソッド ---
impl<D: DirectionStrategy> Graph<Static, D> {
    pub fn build(&mut self) {
        let mut meta = GraphMetadata::default();
        let mut in_degree = vec![0; self.n];
        let mut is_01 = true;
        let mut is_unweighted = true;

        // 隣接リスト構築
        for a in &mut self.adj { a.clear(); }
        for &(u, v, w) in &self.raw_edges {
            self.adj[u].push(Edge { to: v, weight: w });
            if D::IS_DIRECTED {
                in_degree[v] += 1;
            } else {
                self.adj[v].push(Edge { to: u, weight: w });
            }
            if w != 0 && w != 1 { is_01 = false; }
            if w != 1 { is_unweighted = false; }
        }
        meta.is_01 = is_01;
        meta.is_unweighted = is_unweighted;

        // DAG判定 (有向のみ)
        if D::IS_DIRECTED {
            let mut queue = VecDeque::new();
            let mut temp_in_degree = in_degree.clone();
            for i in 0..self.n {
                if temp_in_degree[i] == 0 { queue.push_back(i); }
            }
            while let Some(u) = queue.pop_front() {
                meta.topological_order.push(u);
                for e in &self.adj[u] {
                    temp_in_degree[e.to] -= 1;
                    if temp_in_degree[e.to] == 0 { queue.push_back(e.to); }
                }
            }
            meta.is_dag = meta.topological_order.len() == self.n;
        } else {
            meta.is_dag = false; // 無向グラフは通常DAGとは呼ばない
        }

        // 連結成分数カウント
        let mut visited = vec![false; self.n];
        let mut component_count = 0;
        for i in 0..self.n {
            if !visited[i] {
                component_count += 1;
                let mut q = VecDeque::new();
                q.push_back(i);
                visited[i] = true;
                while let Some(u) = q.pop_front() {
                    for e in &self.adj[u] {
                        if !visited[e.to] {
                            visited[e.to] = true;
                            q.push_back(e.to);
                        }
                    }
                }
            }
        }
        meta.component_count = component_count;

        // 木判定
        // 無向: 連結かつ辺が N-1 / 有向: 弱連結かつ辺が N-1 かつ DAG
        let edge_count = self.raw_edges.len();
        if !D::IS_DIRECTED {
            meta.is_tree = component_count == 1 && edge_count == self.n - 1;
        } else {
            meta.is_tree = meta.is_dag && component_count == 1 && edge_count == self.n - 1;
        }

        self.meta = Some(meta);
    }
}

impl<S: StorageStrategy, D: DirectionStrategy> Graph<S, D> {
    
    /// 隣接頂点の一覧を返す
    pub fn neighbors(&self, u: usize) -> &[Edge] {
        &self.adj[u]
    }

    /// 重みをすべて1とみなした時の最短距離 (通常のBFS)
    pub fn bfs(&self, start: usize) -> Vec<Option<i64>> {
        let mut dist = vec![None; self.n];
        let mut que = VecDeque::new();

        dist[start] = Some(0);
        que.push_back(start);

        while let Some(u) = que.pop_front() {
            let d = dist[u].unwrap();
            for e in &self.adj[u] {
                if dist[e.to].is_none() {
                    dist[e.to] = Some(d + 1);
                    que.push_back(e.to);
                }
            }
        }
        dist
    }

    /// 最短経路 (SSSP): meta情報を元に最適化
    pub fn dist_from(&self, start: usize) -> Vec<Option<i64>> {
        if let Some(ref m) = self.meta {
            if m.is_dag {
                return self.dist_dag(start);
            }
            if m.is_unweighted {
                return self.bfs(start);
            }
            if m.is_01 {
                return self.bfs_01(start);
            }
        }
        self.dijkstra(start)
    }

    /// 01-BFS: 重みが 0 または 1 の場合のみ使用可能
    fn bfs_01(&self, start: usize) -> Vec<Option<i64>> {
        let mut dist = vec![None; self.n];
        let mut que = VecDeque::new();
        dist[start] = Some(0);
        que.push_back(start);

        while let Some(u) = que.pop_front() {
            let d = dist[u].unwrap();
            for e in &self.adj[u] {
                let next_d = d + e.weight;
                if dist[e.to].is_none() || next_d < dist[e.to].unwrap() {
                    dist[e.to] = Some(next_d);
                    if e.weight == 0 {
                        que.push_front(e.to);
                    } else {
                        que.push_back(e.to);
                    }
                }
            }
        }
        dist
    }

    /// DAG上の最短経路 (トポロジカルソート順DP)
    fn dist_dag(&self, start: usize) -> Vec<Option<i64>> {
        let mut dist = vec![None; self.n];
        dist[start] = Some(0);
        
        let order = &self.meta.as_ref().unwrap().topological_order;
        // トポロジカル順に更新
        for &u in order {
            if let Some(d) = dist[u] {
                for e in &self.adj[u] {
                    if dist[e.to].is_none() || d + e.weight < dist[e.to].unwrap() {
                        dist[e.to] = Some(d + e.weight);
                    }
                }
            }
        }
        dist
    }

    /// ダイクストラ法: 一般的な非負重みグラフ用
    pub fn dijkstra(&self, start: usize) -> Vec<Option<i64>> {
        let mut dist = vec![None; self.n];
        let mut pq = BinaryHeap::new();

        dist[start] = Some(0);
        pq.push(Reverse((0, start)));

        while let Some(Reverse((d, u))) = pq.pop() {
            if Some(d) > dist[u] { continue; }
            for e in &self.adj[u] {
                let next_d = d + e.weight;
                if dist[e.to].is_none() || next_d < dist[e.to].unwrap() {
                    dist[e.to] = Some(next_d);
                    pq.push(Reverse((next_d, e.to)));
                }
            }
        }
        dist
    }

    /// 全点対間最短距離 (APSP)
    pub fn dist_all(&self) -> Vec<Vec<Option<i64>>> {
        // 頂点数が少なければ ワーシャルフロイド
        if self.n <= 400 {
            self.warshall_floyd()
        } else {
            // 頂点数が多ければ 各点からダイクストラ
            (0..self.n).map(|i| self.dist_from(i)).collect()
        }
    }

    fn warshall_floyd(&self) -> Vec<Vec<Option<i64>>> {
        let mut dist = vec![vec![None; self.n]; self.n];
        for i in 0..self.n { dist[i][i] = Some(0); }
        for u in 0..self.n {
            for e in &self.adj[u] {
                let d = Some(e.weight);
                if dist[u][e.to].is_none() || d < dist[u][e.to] {
                    dist[u][e.to] = d;
                }
            }
        }
        for k in 0..self.n {
            for i in 0..self.n {
                for j in 0..self.n {
                    if let (Some(ik), Some(kj)) = (dist[i][k], dist[k][j]) {
                        if dist[i][j].is_none() || ik + kj < dist[i][j].unwrap() {
                            dist[i][j] = Some(ik + kj);
                        }
                    }
                }
            }
        }
        dist
    }
}

} // mod graph
pub mod  rangeset {
use std::collections::BTreeSet;
use std::cmp::{max, min};
use std::ops::RangeFrom;

#[derive(Debug, Clone, Default)]
pub struct RangeSet {
    // [l, r] の閉区間を保持。l を基準にソートされる
    set: BTreeSet<(i64, i64)>,
    total_len: i64,
}

impl RangeSet {
    pub fn new() -> Self {
        Self {
            set: BTreeSet::new(),
            total_len: 0,
        }
    }

    /// [l, r] を追加する O(log N)
    pub fn insert(&mut self, mut l: i64, mut r: i64) {
        if l > r { return; }
        let overlaps = self.drain_overlaps(l - 1, r + 1);
        for (sl, sr) in overlaps {
            l = min(l, sl);
            r = max(r, sr);
        }
        self.set.insert((l, r));
        self.total_len += r - l + 1;
    }

    /// [l, r] を削除する O(log N)
    pub fn erase(&mut self, l: i64, r: i64) {
        if l > r { return; }
        let overlaps = self.drain_overlaps(l, r);
        for (sl, sr) in overlaps {
            if sl < l {
                self.set.insert((sl, l - 1));
                self.total_len += (l - 1) - sl + 1;
            }
            if r < sr {
                self.set.insert((r + 1, sr));
                self.total_len += sr - (r + 1) + 1;
            }
        }
    }

    /// x 以上で含まれていない最小の整数 O(log N)
    pub fn mex(&self, x: i64) -> i64 {
        if let Some((_, sr)) = self.span(x) {
            sr + 1
        } else {
            x
        }
    }

    pub fn min(&self) -> Option<i64> {
        self.set.first().map(|&(l, _)| l)
    }

    pub fn max(&self) -> Option<i64> {
        self.set.last().map(|&(_, r)| r)
    }

    /// 小さい方から k 番目(0-indexed)の値を返す O(区間数)
    pub fn kth(&self, mut k: i64) -> Option<i64> {
        if k < 0 || k >= self.total_len { return None; }
        for &(l, r) in &self.set {
            let len = r - l + 1;
            if k < len { return Some(l + k); }
            k -= len;
        }
        None
    }

    /// 区間 [l, r] のうち、集合に含まれている整数の個数 O(log N)
    pub fn count_in(&self, l: i64, r: i64) -> i64 {
        if l > r { return 0; }
        let mut count = 0;
        for &(sl, sr) in self.set.range(self.range_from(l)) {
            if r < sl { break; }
            let il = max(l, sl);
            let ir = min(r, sr);
            if il <= ir { count += ir - il + 1; }
        }
        count
    }

    /// [l, r] 内の「隙間」を返す O(log N)
    pub fn find_gap(&self, l: i64, r: i64) -> Vec<(i64, i64)> {
        let mut gaps = Vec::new();
        let mut curr = l;
        for &(sl, sr) in self.set.range(self.range_from(l)) {
            if r < curr { break; }
            if curr < sl {
                gaps.push((curr, min(r, sl - 1)));
            }
            curr = max(curr, sr + 1);
        }
        if curr <= r { gaps.push((curr, r)); }
        gaps
    }

    pub fn span(&self, x: i64) -> Option<(i64, i64)> {
        if let Some(&(sl, sr)) = self.set.range(self.range_from(x)).next() {
            if sl <= x && x <= sr { return Some((sl, sr)); }
        }
        None
    }

    pub fn contains(&self, x: i64) -> bool { self.span(x).is_some() }
    pub fn len(&self) -> i64 { self.total_len }

    // --- 内部ヘルパー ---

    /// 指定範囲 [l, r] と重なる区間を削除して返す
    fn drain_overlaps(&mut self, l: i64, r: i64) -> Vec<(i64, i64)> {
        let mut removed = Vec::new();
        // ここが修正ポイント：range_fromの結果をそのまま使う
        let it = self.set.range(self.range_from(l)).cloned().collect::<Vec<_>>();
        for (sl, sr) in it {
            if r < sl { break; }
            if max(l, sl) <= min(r, sr) {
                self.total_len -= sr - sl + 1;
                self.set.remove(&(sl, sr));
                removed.push((sl, sr));
            }
        }
        removed
    }

    /// x を含む可能性がある「最も左の区間」を起点とする範囲オブジェクトを返す
    fn range_from(&self, x: i64) -> RangeFrom<(i64, i64)> {
        // x 以下の start を持つ最大の区間を探す
        if let Some(&prev) = self.set.range(..(x, std::i64::MAX)).next_back() {
            prev..
        } else {
            (std::i64::MIN, std::i64::MIN)..
        }
    }
}

} // mod rangeset
pub mod  potentialdsu {
/*
fn main() {
    let mut dsu = PotentialDSU::new(5);

    // V[1] = V[0] + 5  (1は0より5大きい)
    dsu.merge(0, 1, 5);
    // V[2] = V[1] + 3  (2は1より3大きい)
    dsu.merge(1, 2, 3);

    // 0 から見た 2 の差は？
    if let Some(d) = dsu.diff(0, 2) {
        println!("V[2] - V[0] = {}", d); // 8
    }

    // 矛盾する情報を入れようとすると false が返る
    let success = dsu.merge(0, 2, 10); // 実際は 8 なので矛盾
    println!("Merge success: {}", success); // false
}
*/

pub struct PotentialDSU{
    parent_or_size: Vec<i32>,
    diff_weight: Vec<i64>,
}

impl PotentialDSU{
    pub fn new(n: usize) -> Self{
        Self{
            parent_or_size: vec![-1; n],
            diff_weight: vec![0; n],
        }
    }
    
    /// 根を探す。同時に経路圧縮を行い、ポテンシャルを「根からの差」に更新する
    pub fn leader(&mut self, a: usize) -> usize {
        if self.parent_or_size[a] < 0 {
            return a;
        }
        let root = self.leader(self.parent_or_size[a] as usize);
        // 親がさらに上の親（最終的に根）に繋ぎ変わるので、重みも累積させる
        self.diff_weight[a] += self.diff_weight[self.parent_or_size[a] as usize];
        self.parent_or_size[a] = root as i32;
        root
    }

    /// a から見た b のポテンシャル（V[b] - V[a]）を返す
    /// 同じグループにいない場合は None
    pub fn diff(&mut self, a: usize, b: usize) -> Option<i64> {
        if self.leader(a) != self.leader(b) {
            return None;
        }
        // V[b] - V[root] - (V[a] - V[root]) = V[b] - V[a]
        Some(self.diff_weight[b] - self.diff_weight[a])
    }

    /// V[b] = V[a] + w となるように関係性を登録する
    /// すでに同じグループにいて、矛盾が発生する場合は false を返す
    pub fn merge(&mut self, a: usize, b: usize, mut w: i64) -> bool {
        let mut root_a = self.leader(a);
        let mut root_b = self.leader(b);

        if root_a == root_b {
            // すでに同じグループなら、既存の差と矛盾しないかチェック
            return self.diff(a, b) == Some(w);
        }

        // V[b] = V[a] + w
        // V[b] = V[root_b] + dw[b]
        // V[a] = V[root_a] + dw[a]
        // => V[root_b] + dw[b] = V[root_a] + dw[a] + w
        // => V[root_b] = V[root_a] + (w + dw[a] - dw[b])
        w += self.diff_weight[a];
        w -= self.diff_weight[b];

        // Union by size
        if -self.parent_or_size[root_a] < -self.parent_or_size[root_b] {
            std::mem::swap(&mut root_a, &mut root_b);
            w = -w;
        }

        self.parent_or_size[root_a] += self.parent_or_size[root_b];
        self.parent_or_size[root_b] = root_a as i32;
        self.diff_weight[root_b] = w;
        true
    }

    pub fn same(&mut self, a: usize, b: usize) -> bool {
        self.leader(a) == self.leader(b)
    }

    pub fn size(&mut self, a: usize) -> usize {
        let leader = self.leader(a);
        -self.parent_or_size[leader] as usize
    }
}

} // mod potentialdsu
pub mod  treap {
/*
fn main() {
    let mut tr = Treap::new();
    tr.insert(0, 10);
    tr.insert(1, 20);
    tr.insert(2, 30); // [10, 20, 30]

    tr.reverse(0, 2);  // [20, 10, 30]
    
    println!("sum(0..2): {}", tr.range_sum(0, 2)); // 20 + 10 = 30
    println!("val at 0: {}", tr.range_sum(0, 1)); // 20
}
*/

use std::time::{SystemTime, UNIX_EPOCH};

// シンプルな乱数生成器
#[derive(Debug)]
struct Random(u64);
impl Random {
    fn new() -> Self {
        let s = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_nanos() as u64;
        Self(s)
    }
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

#[derive(Clone, Debug)]
struct Node {
    val: i64,
    sum: i64,      // 区間和（セグ木機能）
    priority: u64,
    size: usize,
    left: Option<usize>,
    right: Option<usize>,
    rev: bool,     // 反転フラグ
}

#[derive(Debug)]
pub struct Treap {
    nodes: Vec<Node>,
    root: Option<usize>,
    rng: Random,
}

impl Treap {
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            root: None,
            rng: Random::new(),
        }
    }

    fn create_node(&mut self, val: i64) -> usize {
        let idx = self.nodes.len();
        self.nodes.push(Node {
            val,
            sum: val,
            priority: self.rng.next(),
            size: 1,
            left: None,
            right: None,
            rev: false,
        });
        idx
    }

    fn get_size(&self, idx: Option<usize>) -> usize {
        idx.map_or(0, |i| self.nodes[i].size)
    }

    fn get_sum(&self, idx: Option<usize>) -> i64 {
        idx.map_or(0, |i| self.nodes[i].sum)
    }

    // 子の情報から自分の size と sum を更新
    fn update(&mut self, idx: usize) {
        // 1. まず、子のインデックスをコピーして取得する
        // これにより self.nodes[idx] への借用をすぐに終わらせる
        let left_idx = self.nodes[idx].left;
        let right_idx = self.nodes[idx].right;

        // 2. 子の情報を計算する (self.get_size や self.get_sum を安全に呼べる)
        let left_size = self.get_size(left_idx);
        let right_size = self.get_size(right_idx);
        let left_sum = self.get_sum(left_idx);
        let right_sum = self.get_sum(right_idx);

        // 3. 最後に自分自身のノードを取得して値を書き換える
        let node = &mut self.nodes[idx];
        node.size = 1 + left_size + right_size;
        node.sum = node.val + left_sum + right_sum;
    }
    
    // 遅延フラグを下ろす（反転処理）
    fn push(&mut self, idx: Option<usize>) {
        if let Some(i) = idx {
        // 1. まず反転フラグが立っているかチェック
            if self.nodes[i].rev {
                // フラグを倒す
                self.nodes[i].rev = false;

                // 2. 子のインデックスを「値」としてコピーして取り出す
                // これで self.nodes[i] への参照は不要になる
                let l_idx = self.nodes[i].left;
                let r_idx = self.nodes[i].right;

                // 3. 左右を入れ替える
                self.nodes[i].left = r_idx;
                self.nodes[i].right = l_idx;

                // 4. 子にフラグを伝搬させる
                // 参照ではなくインデックス（usize）を使っているので、
                // 別々にアクセスしても借用エラーにならない
                if let Some(li) = self.nodes[i].left {
                    self.nodes[li].rev ^= true;
                }
                if let Some(ri) = self.nodes[i].right {
                    self.nodes[ri].rev ^= true;
                }
            }
        }
    }

    // 分割: [0, k) と [k, n) に分ける
    fn split(&mut self, node: Option<usize>, k: usize) -> (Option<usize>, Option<usize>) {
        if node.is_none() { return (None, None); }
        let idx = node.unwrap();
        self.push(Some(idx));
        
        let left_size = self.get_size(self.nodes[idx].left);
        if k <= left_size {
            // 左側をさらに分割
            let left_child = self.nodes[idx].left;
            let (l, r) = self.split(left_child, k);
            self.nodes[idx].left = r;
            self.update(idx);
            (l, Some(idx))
        } else {
            // 右側をさらに分割
            let right_child = self.nodes[idx].right;
            let (l, r) = self.split(right_child, k - left_size - 1);
            self.nodes[idx].right = l;
            self.update(idx);
            (Some(idx), r)
        }
    }

    // マージ: 2つの木を合体させる
    fn merge(&mut self, l: Option<usize>, r: Option<usize>) -> Option<usize> {
        self.push(l);
        self.push(r);
        match (l, r) {
            (None, r) => r,
            (l, None) => l,
            (Some(li), Some(ri)) => {
                if self.nodes[li].priority > self.nodes[ri].priority {
                    let right_child = self.nodes[li].right;
                    self.nodes[li].right = self.merge(right_child, Some(ri));
                    self.update(li);
                    Some(li)
                } else {
                    let left_child = self.nodes[ri].left;
                    self.nodes[ri].left = self.merge(Some(li), left_child);
                    self.update(ri);
                    Some(ri)
                }
            }
        }
    }

    // --- 公開メソッド（ボロチェッカー対策済み） ---

    pub fn insert(&mut self, i: usize, val: i64) {
        let (l, r) = self.split(self.root, i);
        let mid = Some(self.create_node(val));
        let tmp = self.merge(l, mid); // ネストせず一旦変数に置く
        self.root = self.merge(tmp, r);
    }

    pub fn erase(&mut self, i: usize) {
        let (l, mid_r) = self.split(self.root, i);
        let (_mid, r) = self.split(mid_r, 1);
        self.root = self.merge(l, r);
    }

    pub fn reverse(&mut self, l: usize, r: usize) {
        let (left, mid_right) = self.split(self.root, l);
        let (mid, right) = self.split(mid_right, r - l);
        if let Some(m) = mid {
            self.nodes[m].rev ^= true;
        }
        let tmp = self.merge(left, mid);
        self.root = self.merge(tmp, right);
    }

    pub fn range_sum(&mut self, l: usize, r: usize) -> i64 {
        let (left, mid_right) = self.split(self.root, l);
        let (mid, right) = self.split(mid_right, r - l);
        let res = self.get_sum(mid);
        let tmp = self.merge(left, mid);
        self.root = self.merge(tmp, right);
        res
    }

    pub fn len(&self) -> usize {
        self.get_size(self.root)
    }
}

} // mod treap

} // mod ds
pub mod  prelude {
pub trait ChangeMinMax{
    fn chmin(&mut self, val: Self) -> bool;
    fn chmax(&mut self, val: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, val: Self) -> bool {
        if *self > val { *self = val; true } else { false }
    }
    fn chmax(&mut self, val: Self) -> bool {
        if *self < val { *self = val; true } else { false }
    }
}

pub mod math {
    /// 最大公約数
    pub fn gcd(a: u64, b: u64) -> u64 {
        if b == 0 { a } else { gcd(b, a % b) }
    }

    /// 最小公倍数
    pub fn lcm(a: u64, b: u64) -> u64 {
        if a == 0 || b == 0 { 0 } else { (a / gcd(a, b)) * b }
    }

    /// 繰り返し二乗法 (a^n % m)
    pub fn pow_mod(mut a: u64, mut n: u64, m: u64) -> u64 {
        let mut res = 1 % m;
        a %= m;
        while n > 0 {
            if n % 2 == 1 { res = res * a % m; }
            a = a * a % m;
            n /= 2;
        }
        res
    }

    /// エラトステネスの篩 (n以下の素数判定テーブル)
    pub fn sieve(n: usize) -> Vec<bool> {
        let mut is_prime = vec![true; n + 1];
        is_prime[0] = false; is_prime[1] = false;
        for i in 2..=((n as f64).sqrt() as usize) {
            if is_prime[i] {
                for j in (i * i..=n).step_by(i) { is_prime[j] = false; }
            }
        }
        is_prime
    }
}


pub fn compress<T: Ord + Clone>(a: &[T]) -> Vec<usize> {
    let mut vals = a.to_vec();
    vals.sort_unstable();
    vals.dedup();
    a.iter().map(|x| vals.binary_search(x).unwrap()).collect()
}



} // mod prelude
pub mod  math {

} // mod math

}

Submission Info

Compile Error

warning: field `n` is never read
   --> src/main.rs:606:5
    |
605 | pub struct LazySegTree<M: MapMonoid> {
    |            ----------- field in this struct
606 |     n: usize,
    |     ^
    |
    = note: `#[warn(dead_code)]` on by default

warning: field `n` is never read
   --> src/main.rs:786:5
    |
785 | pub struct MergeSortTree<T>{
    |            ------------- field in this struct
786 |     n: usize,
    |     ^

Judge Result