// https://contest.ucup.ac/contest/1894/problem/9986
pub mod solution {
//{"name":"L. Shiori","group":"Universal Cup - The 3rd Universal Cup. Stage 26: China","url":"https://contest.ucup.ac/contest/1894/problem/9986","interactive":false,"timeLimit":1000,"tests":[{"input":"5 8\n0 7 2 1 0\n1 2 4 0\n2 1 3\n2 3 4\n3 1 3\n1 2 3 4\n3 1 4\n2 1 5\n3 2 5\n","output":"5\n11\n22\n"}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"LShiori"}}}

use std::time::Instant;

use crate::algo_lib::collections::bit_set::BitSet;
use crate::algo_lib::collections::sqrt_decomposition::Part;
use crate::algo_lib::collections::sqrt_decomposition::SqrtDecomposition;
use crate::algo_lib::collections::sqrt_decomposition::SqrtNode;
#[allow(unused)]
use crate::dbg;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
use crate::algo_lib::misc::rand::Random;

const MX: usize = 500_210;

#[derive(Clone)]
struct Block {
    bitset: BitSet,
    sum: i64,
    n: i64,
    set_to_value: Option<i64>,
    add_to_every: i64,
}

impl Block {
    pub fn new() -> Self {
        Self {
            bitset: BitSet::new(MX),
            sum: 0,
            n: 0,
            set_to_value: None,
            add_to_every: 0,
        }
    }
}

impl SqrtNode for Block {
    type Value = i64;

    fn relax(&mut self, raw_values: &mut [Self::Value]) {
        if let Some(v) = self.set_to_value {
            for x in raw_values.iter_mut() {
                *x = v;
            }
        } else if self.add_to_every != 0 {
            for x in raw_values.iter_mut() {
                *x += self.add_to_every;
            }
        }
        self.set_to_value = None;
        self.add_to_every = 0;
    }

    fn rebuild(&mut self, raw_values: &[Self::Value]) {
        self.bitset.clear();
        for &x in raw_values.iter() {
            if x < MX as i64 {
                self.bitset.set(x as usize, true);
            }
        }
        self.add_to_every = 0;
        self.set_to_value = None;
        self.sum = raw_values.iter().sum();
        self.n = raw_values.len() as i64;
    }
}

struct Solver {
    sqrt: SqrtDecomposition<Block>,
    query_bitset: BitSet,
    block_size: usize,
}

impl Solver {
    pub fn new(a: Vec<i64>, block_size: usize) -> Self {
        let block_size = block_size.min(a.len());
        let sqrt = SqrtDecomposition::new(a, block_size, Block::new());
        Self {
            sqrt,
            query_bitset: BitSet::new(MX),
            block_size,
        }
    }

    fn set(&mut self, l: usize, r: usize, v: i64) {
        self.sqrt.iter_mut(
            l..r,
            |block| match block {
                Part::Full(block) => {
                    block.set_to_value = Some(v);
                    block.add_to_every = 0;
                    block.sum = v * block.n;
                }
                Part::Single(_block, single) => {
                    *single = v;
                }
            },
            true,
        );
    }

    fn add_mex(&mut self, l: usize, r: usize) {
        self.query_bitset.clear();
        self.sqrt.iter_mut(
            l..r,
            |block| match block {
                Part::Full(_block) => {
                    // NOTHING
                }
                Part::Single(_block, single) => {
                    if *single < MX as i64 {
                        self.query_bitset.set_true(*single as usize);
                    }
                }
            },
            false,
        );
        let mut mex = 0;
        for base in (0..).step_by(64) {
            let mut my = self.query_bitset.get_u64(base);
            // dbg!(self.block_size, my, l, r);
            self.sqrt.iter_mut_only_full(l..r, |block| {
                // dbg!("l..r", l, r);
                if let Some(v) = block.set_to_value {
                    if v >= base as i64 && v < (base as i64 + 64) {
                        my |= 1 << (v as usize - base);
                    }
                } else if block.add_to_every < (base + 64) as i64 {
                    if block.add_to_every <= base as i64 {
                        my |= block.bitset.get_u64(base - block.add_to_every as usize);
                        // dbg!("!!", my, base - block.add_to_every as usize);
                    } else {
                        let from0_mask = block.bitset.get_u64(0);
                        let need_first_bits = block.add_to_every as usize - base;
                        let from0_mask = from0_mask << need_first_bits;
                        my |= from0_mask;
                    }
                }
            });
            if my == u64::MAX {
                mex += 64;
            } else {
                for bit in 0..64 {
                    if (my & (1 << bit)) == 0 {
                        mex += bit;
                        break;
                    }
                }
                break;
            }
        }
        // dbg!(mex);
        // if mex != 0 {
        self.sqrt.iter_mut(
            l..r,
            |block| match block {
                Part::Full(block) => {
                    if let Some(v) = block.set_to_value {
                        block.set_to_value = Some(v + mex as i64);
                        block.sum = block.n * (v + mex as i64);
                    } else {
                        block.add_to_every += mex as i64;
                        block.sum += block.n * mex as i64;
                    }
                }
                Part::Single(_block, single) => {
                    *single += mex as i64;
                }
            },
            true,
        );
        // }
    }

    fn sum(&mut self, l: usize, r: usize) -> i64 {
        let mut res = 0;
        self.sqrt.iter_mut(
            l..r,
            |block| match block {
                Part::Full(block) => {
                    res += block.sum;
                }
                Part::Single(_block, single) => {
                    res += *single;
                }
            },
            true,
        );
        res
    }
}

fn solve(input: &mut Input, out: &mut Output, _test_case: usize) {
    let n = input.usize();
    let m = input.usize();
    let a = input.vec::<i64>(n);
    const BLOCK_SIZE: usize = 2000;
    let mut solver = Solver::new(a, BLOCK_SIZE);
    for _ in 0..m {
        let op_type = input.usize();
        let l = input.usize() - 1;
        let r = input.usize();
        if op_type == 1 {
            // set
            let v = input.i64();
            solver.set(l, r, v);
        } else if op_type == 2 {
            // calc mex and add
            solver.add_mex(l, r);
        } else if op_type == 3 {
            let res = solver.sum(l, r);
            out.println(res);
        } else {
            unreachable!();
        }
    }
}

fn stress2() {
    for it in 54.. {
        dbg!(it);
        let mut rnd = Random::new(it);
        const MAX_N: usize = 100;
        const MAX_V: i64 = 500;
        const MAX_M: usize = 100;
        let n = rnd.gen(1..MAX_N);
        let a = rnd.gen_vec(n, 0..MAX_V);
        // dbg!(a);
        let block_size1 = rnd.gen(1..MAX_N);
        let block_size2 = rnd.gen(1..MAX_N);
        // dbg!(block_size1, block_size2);
        let mut solver1 = Solver::new(a.clone(), block_size1);
        let mut solver2 = Solver::new(a.clone(), block_size2);
        for _ in 0..MAX_M {
            let op_type = rnd.gen(1..4);
            let l = rnd.gen(0..n);
            let r = rnd.gen(l + 1..n + 1);
            if op_type == 1 {
                // set
                let v = rnd.gen(0..MAX_V);
                // dbg!("set", l, r, v);
                solver1.set(l, r, v);
                solver2.set(l, r, v);
            } else if op_type == 2 {
                // calc mex and add
                // dbg!("add_mex", l, r);
                solver1.add_mex(l, r);
                solver2.add_mex(l, r);
            } else if op_type == 3 {
                // dbg!("sum", l, r);
                let res1 = solver1.sum(l, r);
                let res2 = solver2.sum(l, r);
                // dbg!(res1, res2);
                assert_eq!(res1, res2);
            } else {
                unreachable!();
            }
        }
    }
}

fn stress() {
    for it in 1.. {
        dbg!(it);
        let mut rnd = Random::new(it);
        const MAX_N: usize = 500_000;
        const MAX_V: i64 = 500_000;
        const MAX_M: usize = 500_000;
        let n = MAX_N;
        let start = Instant::now();
        let a = rnd.gen_vec(n, 0..MAX_V);
        let mut solver = Solver::new(a.clone(), 500);
        for _ in 0..MAX_M {
            let op_type = rnd.gen(1..4);
            let l = rnd.gen(0..n);
            let r = rnd.gen(l + 1..n + 1);
            if op_type == 1 {
                // set
                let v = rnd.gen(0..MAX_V);
                solver.set(l, r, v);
            } else if op_type == 2 {
                solver.add_mex(l, r);
            } else if op_type == 3 {
                solver.sum(l, r);
            } else {
                unreachable!();
            }
        }
        dbg!(start.elapsed())
    }
}

pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
    solve(&mut input, &mut output, 1);
    output.flush();
    true
}

}
pub mod algo_lib {
#![feature(test)]
#![allow(clippy::too_many_arguments)]
#![allow(clippy::type_complexity)]

pub mod collections {
pub mod bit_set {
use std::ops::BitAndAssign;
use std::ops::BitOrAssign;
use std::ops::BitXorAssign;
use std::ops::Not;

#[derive(Hash, Clone, Eq, PartialOrd, PartialEq, Debug)]
pub struct BitSet {
    values: Vec<u64>,
}

impl BitSet {
    pub fn calc_len(n: usize) -> usize {
        (n + 127) / 128 * 2
    }

    #[allow(unused)]
    pub fn new(n: usize) -> Self {
        Self {
            values: vec![0u64; BitSet::calc_len(n)],
        }
    }

    #[allow(unused)]
    pub fn get(&self, pos: usize) -> bool {
        (self.values[pos >> 6] >> (pos & 63)) & 1 == 1
    }

    pub fn get_u64(&self, from_pos: usize) -> u64 {
        if from_pos >= self.bit_len() {
            return 0;
        }
        if from_pos & 63 == 0 {
            self.values[from_pos >> 6]
        } else {
            let mut res = self.values[from_pos >> 6] >> (from_pos & 63);
            if from_pos + 64 < self.bit_len() {
                res |= self.values[(from_pos >> 6) + 1] << (64 - (from_pos & 63))
            }
            res
        }
    }

    // bit [i] becomes [i + shift]. Bits after [n] are almost dropped.
    pub fn shift_higher(&self, shift: usize) -> Self {
        let mut res = Self::new(self.bit_len());
        let whole = shift / 64;
        let offset = shift % 64;
        for i in 0..self.values.len() {
            if i + whole >= res.values.len() {
                break;
            }
            res.values[i + whole] |= self.values[i] << offset;
            if offset != 0 && i + whole + 1 < res.values.len() {
                res.values[i + whole + 1] |= self.values[i] >> (64 - offset);
            }
        }
        res
    }

    // bit [i] becomes [i - shift]. Bits before [0] are dropped.
    pub fn shift_lower(&self, shift: usize) -> Self {
        let mut res = Self::new(self.bit_len());
        let whole = shift / 64;
        let offset = shift % 64;
        for i in 0..self.values.len() {
            if i < whole {
                continue;
            }
            // TODO: test
            res.values[i - whole] |= self.values[i] >> offset;
            if offset != 0 && i - whole != 0 {
                res.values[i - whole - 1] |= self.values[i] << (64 - offset);
            }
        }
        res
    }

    #[allow(unused)]
    pub fn set(&mut self, pos: usize, val: bool) {
        if val {
            self.values[pos >> 6] |= 1u64 << (pos & 63);
        } else {
            self.values[pos >> 6] &= (1u64 << (pos & 63)).not();
        }
    }

    pub fn set_true(&mut self, pos: usize) {
        self.values[pos >> 6] |= 1u64 << (pos & 63);
    }

    #[allow(unused)]
    pub fn clear(&mut self) {
        for x in self.values.iter_mut() {
            *x = 0;
        }
    }

    fn ensure_length(&mut self, bit_len: usize) {
        let i64_len = Self::calc_len(bit_len);
        if i64_len > self.values.len() {
            self.values.resize(i64_len, 0);
        }
    }

    fn bit_len(&self) -> usize {
        self.values.len() << 6
    }

    pub fn first_not_set(&self, mut pos: usize) -> usize {
        if pos >= self.bit_len() {
            return pos;
        }
        while (pos & 63) != 0 {
            if !self.get(pos) {
                return pos;
            }
            pos += 1;
        }
        match self.values[pos >> 6..]
            .iter()
            .position(|x| *x != std::u64::MAX)
        {
            None => self.values.len() << 6,
            Some(idx) => {
                pos += idx * 64;
                while self.get(pos) {
                    pos += 1;
                }
                pos
            }
        }
    }

    pub fn first_set(&self, mut pos: usize) -> Option<usize> {
        if pos >= self.bit_len() {
            return None;
        }
        if (pos & 63) != 0 {
            let part = self.values[pos >> 6] >> (pos & 63);
            if part != 0 {
                return Some(pos + part.trailing_zeros() as usize);
            }
            pos = (pos | 63) + 1;
        }
        match self.values[pos >> 6..].iter().position(|x| *x != 0) {
            None => None,
            Some(idx) => {
                pos += idx * 64;
                pos += self.values[pos >> 6].trailing_zeros() as usize;
                assert!(self.get(pos));
                Some(pos)
            }
        }
    }

    #[target_feature(enable = "avx2")]
    unsafe fn bitor_assign_avx2(&mut self, rhs: &Self) {
        for (x, y) in self.values.iter_mut().zip(rhs.values.iter()) {
            *x |= *y;
        }
    }

    #[target_feature(enable = "ssse3")]
    unsafe fn bitor_assign_ssse3(&mut self, rhs: &Self) {
        for (x, y) in self.values.iter_mut().zip(rhs.values.iter()) {
            *x |= *y;
        }
    }

    pub fn count_ones(&self) -> usize {
        self.values.iter().map(|x| x.count_ones() as usize).sum()
    }
}

impl BitOrAssign<&BitSet> for BitSet {
    fn bitor_assign(&mut self, rhs: &Self) {
        self.ensure_length(rhs.bit_len());
        if is_x86_feature_detected!("avx2") {
            unsafe {
                self.bitor_assign_avx2(rhs);
            }
        } else if is_x86_feature_detected!("ssse3") {
            unsafe {
                self.bitor_assign_ssse3(rhs);
            }
        } else {
            for (x, y) in self.values.iter_mut().zip(rhs.values.iter()) {
                *x |= *y;
            }
        }
    }
}

impl BitAndAssign<&BitSet> for BitSet {
    fn bitand_assign(&mut self, rhs: &BitSet) {
        self.ensure_length(rhs.bit_len());
        let len = rhs.values.len();
        for (x, y) in self.values[0..len]
            .iter_mut()
            .zip(rhs.values[0..len].iter())
        {
            *x &= *y;
        }
    }
}

impl BitXorAssign<&BitSet> for BitSet {
    fn bitxor_assign(&mut self, rhs: &BitSet) {
        self.ensure_length(rhs.bit_len());
        let len = rhs.values.len();
        for (x, y) in self.values[0..len]
            .iter_mut()
            .zip(rhs.values[0..len].iter())
        {
            *x ^= *y;
        }
    }
}
}
pub mod sqrt_decomposition {
use crate::algo_lib::misc::gen_vector::gen_vec;
use crate::algo_lib::misc::range_intersect::range_intersect;
use std::cmp::min;
use std::ops::Range;

pub trait SqrtNode: Clone {
    type Value: Clone;

    fn relax(&mut self, raw_values: &mut [Self::Value]);
    fn rebuild(&mut self, raw_values: &[Self::Value]);
}

pub struct SqrtDecomposition<T>
where
    T: SqrtNode,
{
    raw_values: Vec<T::Value>,
    block_size: usize,
    blocks: Vec<T>,
}

// TODO: think about better name?
pub enum Part<'a, T>
where
    T: SqrtNode,
{
    Full(&'a mut T),
    Single(&'a mut T, &'a mut T::Value),
}

impl<T> SqrtDecomposition<T>
where
    T: SqrtNode,
{
    pub fn new(raw_values: Vec<T::Value>, block_size: usize, empty_block: T) -> Self {
        assert!(block_size > 0);
        let n = raw_values.len();
        let blocks_num = (n + block_size - 1) / block_size;
        let blocks = gen_vec(blocks_num, |id| {
            let mut block = empty_block.clone();
            block.rebuild(&raw_values[id * block_size..min((id + 1) * block_size, n)]);
            block
        });
        Self {
            raw_values,
            block_size,
            blocks,
        }
    }

    pub fn iter_mut<F>(&mut self, range: Range<usize>, mut f: F, do_rebuild: bool)
    where
        F: FnMut(Part<T>),
    {
        let first_block = range.start / self.block_size;
        let last_block = (range.end + self.block_size - 1) / self.block_size;
        let block_size = self.block_size;

        let handle_side_block =
            |id: usize, f: &mut F, block: &mut T, raw_values: &mut [T::Value]| {
                let n = raw_values.len();
                let cur_block = block_size * id..min(n, block_size * (id + 1));
                let range = range_intersect(cur_block.clone(), range.clone());
                if range == cur_block {
                    f(Part::Full(block));
                } else {
                    block.relax(&mut raw_values[cur_block.clone()]);
                    for single in raw_values[range].iter_mut() {
                        f(Part::Single(block, single));
                    }
                    if do_rebuild {
                        block.rebuild(&raw_values[cur_block]);
                    }
                }
            };

        handle_side_block(
            first_block,
            &mut f,
            &mut self.blocks[first_block],
            &mut self.raw_values,
        );
        if first_block + 1 < last_block {
            for block_id in first_block + 1..last_block - 1 {
                f(Part::Full(&mut self.blocks[block_id]))
            }
            handle_side_block(
                last_block - 1,
                &mut f,
                &mut self.blocks[last_block - 1],
                &mut self.raw_values,
            );
        }
    }

    pub fn iter_mut_only_full<F>(&mut self, range: Range<usize>, mut f: F)
    where
        F: FnMut(&mut T),
    {
        let first_block = range.start / self.block_size;
        let last_block = (range.end + self.block_size - 1) / self.block_size;
        let block_size = self.block_size;

        let handle_side_block =
            |id: usize, f: &mut F, block: &mut T, raw_values: &mut [T::Value]| {
                let n = raw_values.len();
                let cur_block = block_size * id..min(n, block_size * (id + 1));
                let range = range_intersect(cur_block.clone(), range.clone());
                if range == cur_block {
                    f(block);
                }
            };

        handle_side_block(
            first_block,
            &mut f,
            &mut self.blocks[first_block],
            &mut self.raw_values,
        );
        if first_block + 1 < last_block {
            for block_id in first_block + 1..last_block - 1 {
                f(&mut self.blocks[block_id])
            }
            handle_side_block(
                last_block - 1,
                &mut f,
                &mut self.blocks[last_block - 1],
                &mut self.raw_values,
            );
        }
    }
}
}
}
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;

pub struct Input {
    input: Box<dyn Read>,
    buf: Vec<u8>,
    at: usize,
    buf_read: usize,
}

macro_rules! read_integer_fun {
    ($t:ident) => {
        #[allow(unused)]
        pub fn $t(&mut self) -> $t {
            self.read_integer()
        }
    };
}

impl Input {
    const DEFAULT_BUF_SIZE: usize = 4096;

    ///
    /// Using with stdin:
    /// ```no_run
    /// use algo_lib::io::input::Input;
    /// let stdin = std::io::stdin();
    /// let input = Input::new(Box::new(stdin));
    /// ```
    ///
    /// For read files use ``new_file`` instead.
    ///
    ///
    pub fn new(input: Box<dyn Read>) -> Self {
        Self {
            input,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            buf_read: 0,
        }
    }

    pub fn new_stdin() -> Self {
        let stdin = std::io::stdin();
        Self::new(Box::new(stdin))
    }

    pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
        let file = std::fs::File::open(&path)
            .unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
        Self::new(Box::new(file))
    }

    pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
        Self {
            input,
            buf: vec![0; buf_size],
            at: 0,
            buf_read: 0,
        }
    }

    pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
        let file = std::fs::File::open(&path)
            .unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
        Self::new_with_size(Box::new(file), buf_size)
    }

    pub fn get(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            let res = self.buf[self.at];
            self.at += 1;
            Some(res)
        } else {
            None
        }
    }

    pub fn peek(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            Some(self.buf[self.at])
        } else {
            None
        }
    }

    pub fn skip_whitespace(&mut self) {
        while let Some(b) = self.peek() {
            if !char::from(b).is_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 char::from(c).is_whitespace() {
                break;
            }
            res.push(c);
        }
        if res.is_empty() {
            None
        } else {
            Some(res)
        }
    }

    //noinspection RsSelfConvention
    pub fn is_exhausted(&mut self) -> bool {
        self.peek().is_none()
    }

    pub fn has_more_elements(&mut self) -> bool {
        !self.is_exhausted()
    }

    pub fn read<T: Readable>(&mut self) -> T {
        T::read(self)
    }

    pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
        let mut res = Vec::with_capacity(size);
        for _ in 0usize..size {
            res.push(self.read());
        }
        res
    }

    pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
        let mut res = Vec::with_capacity(size);
        for _ in 0usize..size {
            res.push(self.string());
        }
        res
    }

    pub fn read_line(&mut self) -> String {
        let mut res = String::new();
        while let Some(c) = self.get() {
            if c == b'\n' {
                break;
            }
            if c == b'\r' {
                if self.peek() == Some(b'\n') {
                    self.get();
                }
                break;
            }
            res.push(c.into());
        }
        res
    }

    #[allow(clippy::should_implement_trait)]
    pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
        InputIterator {
            input: self,
            phantom: Default::default(),
        }
    }

    fn read_integer<T: FromStr + Debug>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let res = self.read_string();
        res.parse::<T>().unwrap()
    }

    fn read_string(&mut self) -> String {
        match self.next_token() {
            None => {
                panic!("Input exhausted");
            }
            Some(res) => unsafe { String::from_utf8_unchecked(res) },
        }
    }

    pub fn string_as_string(&mut self) -> String {
        self.read_string()
    }

    pub fn string(&mut self) -> Vec<u8> {
        self.read_string().into_bytes()
    }

    fn read_char(&mut self) -> char {
        self.skip_whitespace();
        self.get().unwrap().into()
    }

    fn read_float(&mut self) -> f64 {
        self.read_string().parse().unwrap()
    }

    pub fn f64(&mut self) -> f64 {
        self.read_float()
    }

    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
        }
    }

    read_integer_fun!(i32);
    read_integer_fun!(i64);
    read_integer_fun!(i128);
    read_integer_fun!(u32);
    read_integer_fun!(u64);
    read_integer_fun!(usize);
}

pub trait Readable {
    fn read(input: &mut Input) -> Self;
}

impl Readable for String {
    fn read(input: &mut Input) -> Self {
        input.read_string()
    }
}

impl Readable for char {
    fn read(input: &mut Input) -> Self {
        input.read_char()
    }
}

impl Readable for f64 {
    fn read(input: &mut Input) -> Self {
        input.read_string().parse().unwrap()
    }
}

impl Readable for f32 {
    fn read(input: &mut Input) -> Self {
        input.read_string().parse().unwrap()
    }
}

impl<T: Readable> Readable for Vec<T> {
    fn read(input: &mut Input) -> Self {
        let size = input.read();
        input.vec(size)
    }
}

pub struct InputIterator<T: Readable> {
    input: Input,
    phantom: PhantomData<T>,
}

impl<T: Readable> Iterator for InputIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.input.skip_whitespace();
        self.input.peek().map(|_| self.input.read())
    }
}

macro_rules! read_integer {
    ($t:ident) => {
        impl Readable for $t {
            fn read(input: &mut Input) -> Self {
                input.read_integer()
            }
        }
    };
}

read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;

pub struct Output {
    output: Box<dyn Write>,
    buf: Vec<u8>,
    at: usize,
    auto_flush: bool,
}

impl Output {
    const DEFAULT_BUF_SIZE: usize = 4096;

    pub fn new(output: Box<dyn Write>) -> Self {
        Self {
            output,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            auto_flush: false,
        }
    }

    pub fn new_stdout() -> Self {
        let stdout = std::io::stdout();
        Self::new(Box::new(stdout))
    }

    pub fn new_file(path: impl AsRef<std::path::Path>) -> Self {
        let file = std::fs::File::create(path).unwrap();
        Self::new(Box::new(file))
    }

    pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
        Self {
            output,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            auto_flush: true,
        }
    }

    pub fn flush(&mut self) {
        if self.at != 0 {
            self.output.write_all(&self.buf[..self.at]).unwrap();
            self.at = 0;
            self.output.flush().expect("Couldn't flush output");
        }
    }

    pub fn print<T: Writable>(&mut self, s: T) {
        s.write(self);
    }

    pub fn println<T: Writable>(&mut self, s: T) {
        s.write(self);
        self.put(b'\n');
    }

    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]) {
        for i in arg {
            i.write(self);
            self.put(b'\n');
        }
    }

    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(b' ');
            }
            e.write(self);
        }
    }

    pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
        let mut first = true;
        for e in iter {
            if first {
                first = false;
            } else {
                self.put(b' ');
            }
            e.write(self);
        }
    }
}

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;
        }
        if self.auto_flush {
            self.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<T: Writable> Writable for [T] {
    fn write(&self, output: &mut Output) {
        output.print_iter_ref(self.iter());
    }
}

impl<T: Writable> Writable for Vec<T> {
    fn write(&self, output: &mut Output) {
        self[..].write(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!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);

impl<T: Writable, U: Writable> Writable for (T, U) {
    fn write(&self, output: &mut Output) {
        self.0.write(output);
        output.put(b' ');
        self.1.write(output);
    }
}

impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
    fn write(&self, output: &mut Output) {
        self.0.write(output);
        output.put(b' ');
        self.1.write(output);
        output.put(b' ');
        self.2.write(output);
    }
}
}
}
pub mod misc {
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
    ($first_val:expr, $($val:expr),+ $(,)?) => {
        eprint!("[{}:{}] {} = {:?}",
                    file!(), line!(), stringify!($first_val), &$first_val);
        ($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
        eprintln!();
    };
    ($first_val:expr) => {
        eprintln!("[{}:{}] {} = {:?}",
                    file!(), line!(), stringify!($first_val), &$first_val)
    };
}
}
pub mod gen_vector {
pub fn gen_vec<T>(n: usize, f: impl FnMut(usize) -> T) -> Vec<T> {
    (0..n).map(f).collect()
}
}
pub mod num_traits {
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Sub;
use std::ops::SubAssign;

pub trait HasConstants<T> {
    const MAX: T;
    const MIN: T;
    const ZERO: T;
    const ONE: T;
    const TWO: T;
}

pub trait ConvSimple<T> {
    fn from_i32(val: i32) -> T;
    fn to_i32(self) -> i32;
    fn to_f64(self) -> f64;
}

pub trait Signum {
    fn signum(&self) -> i32;
}

pub trait Number:
    Copy
    + Add<Output = Self>
    + AddAssign
    + Sub<Output = Self>
    + SubAssign
    + Mul<Output = Self>
    + MulAssign
    + Div<Output = Self>
    + DivAssign
    + PartialOrd
    + PartialEq
    + HasConstants<Self>
    + Default
    + Debug
    + Sized
    + ConvSimple<Self>
{
}

impl<
        T: Copy
            + Add<Output = Self>
            + AddAssign
            + Sub<Output = Self>
            + SubAssign
            + Mul<Output = Self>
            + MulAssign
            + Div<Output = Self>
            + DivAssign
            + PartialOrd
            + PartialEq
            + HasConstants<Self>
            + Default
            + Debug
            + Sized
            + ConvSimple<Self>,
    > Number for T
{
}

macro_rules! has_constants_impl {
    ($t: ident) => {
        impl HasConstants<$t> for $t {
            // TODO: remove `std` for new rust version..
            const MAX: $t = std::$t::MAX;
            const MIN: $t = std::$t::MIN;
            const ZERO: $t = 0;
            const ONE: $t = 1;
            const TWO: $t = 2;
        }

        impl ConvSimple<$t> for $t {
            fn from_i32(val: i32) -> $t {
                val as $t
            }

            fn to_i32(self) -> i32 {
                self as i32
            }

            fn to_f64(self) -> f64 {
                self as f64
            }
        }
    };
}

has_constants_impl!(i32);
has_constants_impl!(i64);
has_constants_impl!(i128);
has_constants_impl!(u32);
has_constants_impl!(u64);
has_constants_impl!(u128);
has_constants_impl!(usize);
has_constants_impl!(u8);

impl ConvSimple<Self> for f64 {
    fn from_i32(val: i32) -> Self {
        val as f64
    }

    fn to_i32(self) -> i32 {
        self as i32
    }

    fn to_f64(self) -> f64 {
        self
    }
}

impl HasConstants<Self> for f64 {
    const MAX: Self = Self::MAX;
    const MIN: Self = -Self::MAX;
    const ZERO: Self = 0.0;
    const ONE: Self = 1.0;
    const TWO: Self = 2.0;
}

impl<T: Number + Ord> Signum for T {
    fn signum(&self) -> i32 {
        match self.cmp(&T::ZERO) {
            Ordering::Greater => 1,
            Ordering::Less => -1,
            Ordering::Equal => 0,
        }
    }
}
}
pub mod rand {
use crate::algo_lib::misc::gen_vector::gen_vec;
use crate::algo_lib::misc::num_traits::Number;
use std::ops::Range;
use std::time::SystemTime;
use std::time::UNIX_EPOCH;

#[allow(dead_code)]
pub struct Random {
    state: u64,
}

impl Random {
    pub fn gen_u64(&mut self) -> u64 {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        self.state = x;
        x
    }

    #[allow(dead_code)]
    pub fn next_in_range(&mut self, from: usize, to: usize) -> usize {
        assert!(from < to);
        (from as u64 + self.gen_u64() % ((to - from) as u64)) as usize
    }

    pub fn gen_index<T>(&mut self, a: &[T]) -> usize {
        self.gen(0..a.len())
    }

    #[allow(dead_code)]
    #[inline(always)]
    pub fn gen_double(&mut self) -> f64 {
        (self.gen_u64() as f64) / (std::usize::MAX as f64)
    }

    #[allow(dead_code)]
    pub fn new(seed: u64) -> Self {
        let state = if seed == 0 { 787788 } else { seed };
        Self { state }
    }

    pub fn new_time_seed() -> Self {
        let time = SystemTime::now();
        let seed = (time.duration_since(UNIX_EPOCH).unwrap().as_nanos() % 1_000_000_000) as u64;
        if seed == 0 {
            Self::new(787788)
        } else {
            Self::new(seed)
        }
    }

    #[allow(dead_code)]
    pub fn gen_permutation(&mut self, n: usize) -> Vec<usize> {
        let mut result: Vec<_> = (0..n).collect();
        for i in 0..n {
            let idx = self.next_in_range(0, i + 1);
            result.swap(i, idx);
        }
        result
    }

    pub fn shuffle<T>(&mut self, a: &mut [T]) {
        for i in 1..a.len() {
            a.swap(i, self.gen(0..i + 1));
        }
    }

    pub fn gen<T>(&mut self, range: Range<T>) -> T
    where
        T: Number,
    {
        let from = T::to_i32(range.start);
        let to = T::to_i32(range.end);
        assert!(from < to);
        let len = (to - from) as usize;
        T::from_i32(self.next_in_range(0, len) as i32 + from)
    }

    pub fn gen_vec<T>(&mut self, n: usize, range: Range<T>) -> Vec<T>
    where
        T: Number,
    {
        gen_vec(n, |_| self.gen(range.clone()))
    }

    pub fn gen_nonempty_range(&mut self, n: usize) -> Range<usize> {
        let x = self.gen(0..n);
        let y = self.gen(0..n);
        if x <= y {
            x..y + 1
        } else {
            y..x + 1
        }
    }

    pub fn gen_bool(&mut self) -> bool {
        self.gen(0..2) == 0
    }
}
}
pub mod range_intersect {
use crate::algo_lib::misc::num_traits::Number;
use std::cmp::max;
use std::cmp::min;
use std::ops::Range;

pub fn range_intersect<T>(r1: Range<T>, r2: Range<T>) -> Range<T>
where
    T: Number + Ord,
{
    max(r1.start, r2.start)..min(r1.end, r2.end)
}

pub trait Shift {
    fn shift<T>(self, delta: T) -> Self
    where
        T: Number;

    fn shift_left<T>(self, delta: T) -> Self
    where
        T: Number;
}

impl Shift for Range<usize> {
    fn shift<T>(self, delta: T) -> Self
    where
        T: Number,
    {
        let start = (self.start as i32 + delta.to_i32()) as usize;
        let end = (self.end as i32 + delta.to_i32()) as usize;
        start..end
    }

    fn shift_left<T>(self, delta: T) -> Self
    where
        T: Number,
    {
        self.shift(-delta.to_i32())
    }
}
}
}
}
fn main() {
    let input = algo_lib::io::input::Input::new_stdin();
    let mut output = algo_lib::io::output::Output::new_stdout();
    crate::solution::run(input, output);
}