#[allow(unused_imports)]
use std::{
    convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,},
    fs::File, hash::{Hash, Hasher, BuildHasherDefault}, iter::{Product, Sum}, marker::PhantomData,
    ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, 
        Neg, RangeBounds, BitAnd, BitAndAssign, BitOr, BitXor, BitXorAssign, BitOrAssign, Index, IndexMut},
    str::FromStr, sync::{atomic::{self, AtomicU32, AtomicU64}, Once},
    collections::{*, btree_set::Range, btree_map::Range as BTreeRange}, mem::{take, swap},
    cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd},
    thread::LocalKey, f64::consts::PI, time::Instant, cell::RefCell,
    io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write},
    ptr::null_mut, println, print,debug_assert,debug_assert_eq,debug_assert_ne,
    matches
};
#[allow(unused_imports)]
use core::panic;
pub mod fxhash {
    use std::hash::BuildHasherDefault;
    const K: u64 = 0x517c_c1b7_2722_0a95;
    #[derive(Default)]
    pub struct FxHasher {
        pub hash: u64,
    }
    impl FxHasher {
        #[inline(always)]
        fn mix_u64(mut h: u64, x: u64) -> u64 {
            h = h.rotate_left(5) ^ x;
            h = h.wrapping_mul(K);
            let x2 = x ^ (x >> 33) ^ (x << 11);
            h = h.rotate_left(5) ^ x2;
            h = h.wrapping_mul(K);
            h
        }

        #[inline(always)]
        fn write_u64_impl(&mut self, x: u64) {
            self.hash = Self::mix_u64(self.hash, x);
        }
    }

    impl std::hash::Hasher for FxHasher {
        #[inline(always)]
        fn finish(&self) -> u64 {
            self.hash
        }

        #[inline(always)]
        fn write(&mut self, bytes: &[u8]) {
            let mut h = self.hash;
            for &b in bytes {
                h = h.rotate_left(5) ^ (b as u64);
                h = h.wrapping_mul(K);
            }
            self.hash = h;
        }

        #[inline(always)]
        fn write_u64(&mut self, i: u64) { self.write_u64_impl(i); }
        #[inline(always)]
        fn write_u32(&mut self, i: u32) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_u16(&mut self, i: u16) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_u8 (&mut self, i: u8 ) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_usize(&mut self, i: usize) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_i64(&mut self, i: i64) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_i32(&mut self, i: i32) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_i16(&mut self, i: i16) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_i8 (&mut self, i: i8 ) { self.write_u64_impl(i as u64); }
        #[inline(always)]
        fn write_isize(&mut self, i: isize) { self.write_u64_impl(i as u64); }
    }

    pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
    pub type FxMap<K, V> = std::collections::HashMap<K, V, FxBuildHasher>;
    pub type FxSet<K> = std::collections::HashSet<K, FxBuildHasher>;
}

pub fn gcd(mut a: i64, mut b: i64)->i64{a=a.abs();b=b.abs();if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros();
a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a<b{swap(&mut a, &mut b)}a = (a-b)>>x;}a << l1.min(l2)}
pub fn gcd_i32(mut a: i32, mut b: i32)->i32{a=a.abs();b=b.abs();if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros();
a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a<b{swap(&mut a, &mut b)}a = (a-b)>>x;}a << l1.min(l2)}
pub fn factorial_i64(n: usize)->(Vec<i64>, Vec<i64>){ 
    let mut res = vec![1; n+1];let mut inv = vec![1; n+1];for i in 0..n{ res[i+1] = (res[i]*(i+1)as i64)%MOD; }
    inv[n] = mod_inverse(res[n], MOD);for i in (0..n).rev(){ inv[i] = inv[i+1]*(i+1) as i64%MOD; }(res, inv) }
pub fn floor(a:i64, b:i64)->i64{let res=(a%b+b)%b;(a-res)/b}
pub fn modulo(a: i64, b: i64)->i64{(a%b+b)%b}
pub fn extended_gcd(a:i64,b:i64)->(i64,i64,i64)
{if b==0{(a,1,0)}else{let(g,x,y)=extended_gcd(b,a%b);(g,y,x-floor(a,b)*y)}}
pub fn mod_inverse(a:i64,m:i64)->i64{let(_,x,_) =extended_gcd(a,m);(x%m+m)%m}
pub fn comb(a: i64, b: i64, f: &Vec<(i64, i64)>)->i64{
    if a<b{return 0;}else if b==0 || a==b{ return 1; }
    else{let x=f[a as usize].0;
        let y=f[(a-b) as usize].1;let z=f[b as usize].1;return((x*y)%MOD)*z%MOD;}}
pub fn factorial(x: i64)->Vec<(i64, i64)>{
    let mut f=vec![(1i64,1i64),(1, 1)];let mut z = 1i64;
    let mut inv = vec![0; x as usize+10];inv[1] = 1;
    for i in 2..x+1{z=(z*i)%MOD;
        let w=(MOD-inv[(MOD%i)as usize]*(MOD/i)%MOD)%MOD;
        inv[i as usize] = w;
        f.push((z, (f[i as usize-1].1*w)%MOD));}return f;}
pub fn fast_mod_pow(mut x: i64,p: usize, m: i64)->i64{
    x %= m;
    let mut res=1;let mut t=x;let mut z=p;while z > 0{
        if z%2==1{res = (res*t)%m;}t = (t*t)%m;z /= 2; }res}

pub trait SortD{ fn sort_d(&mut self); }
impl<T: Ord> SortD for Vec<T>{ fn sort_d(&mut self) {self.sort_by(|u, v| v.cmp(&u));} }
pub trait Mx{fn max(&self, rhs: Self)->Self;}
impl Mx for f64{ fn max(&self, rhs: Self)->Self{if *self < rhs{ rhs } else { *self } }}
pub trait Mi{ fn min(&self, rhs: Self)->Self; }
impl Mi for f64{ fn min(&self, rhs: Self)->Self{ if *self > rhs{ rhs } else { *self } } }
pub trait Chmax: PartialOrd + Sized {
    #[inline]
    fn chmax(&mut self, rhs: Self) {
        if *self < rhs {
            *self = rhs;
        }
    }
}
impl<T: PartialOrd> Chmax for T {}

pub trait Chmin: PartialOrd + Sized {
    #[inline]
    fn chmin(&mut self, rhs: Self) {
        if *self > rhs {
            *self = rhs;
        }
    }
}
impl<T: PartialOrd> Chmin for T {}

#[allow(unused_macros)]
macro_rules! chmax {
    ($lhs:expr, $rhs:expr $(,)?) => {{
        let candidate = $rhs;
        let target = &mut $lhs;
        if *target < candidate {
            *target = candidate;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! chmin {
    ($lhs:expr, $rhs:expr $(,)?) => {{
        let candidate = $rhs;
        let target = &mut $lhs;
        if *target > candidate {
            *target = candidate;
            true
        } else {
            false
        }
    }};
}
#[allow(unused)]
use proconio::{*, marker::*};
#[allow(unused)]
use fxhash::{FxMap, FxSet};
#[allow(unused)]
use ac_library::{*};

pub struct MintCombination{
    fact: Vec<MI>,
    inv_fact: Vec<MI>,
    inv: Vec<MI>,
}

impl MintCombination{
    pub fn new(n: usize)->Self {
        let mut fact = vec![MI::new(1); n+1];
        let mut inv_fact = vec![MI::new(0); n+1];
        let mut inv = vec![MI::new(1); n+1];
        for i in 0..n{
            fact[i+1] = fact[i]*(i+1);
        }
        inv_fact[n] = MI::new(1)/fact[n];
        for i in (0..n).rev(){
            inv_fact[i] = inv_fact[i+1]*(i+1);
            inv[i+1] = fact[i]*inv_fact[i+1];
        }
        MintCombination { fact, inv_fact, inv }
    }

    #[inline]
    pub fn inv(&self, x: usize)->MI{
        self.inv[x]
    }

    #[inline]
    pub fn f(&self, x: usize)->MI{
        self.fact[x]
    }

    #[inline]
    pub fn fi(&self, x: usize)->MI{
        self.inv_fact[x]
    }

    #[inline]
    pub fn p(&self, x: usize, y: usize)->MI{
        if x < y{MI::new(0)}
        else {self.fact[x]*self.inv_fact[x-y]}
    }

    #[inline]
    pub fn c(&self, x: usize, y: usize)->MI{
        if x < y{return MI::new(0);}
        self.fact[x]*self.inv_fact[y]*self.inv_fact[x-y]
    }
}

#[allow(dead_code)]
const INF: i64 = 1<<60;
#[allow(dead_code)]
const I: i32 = 1<<30;
#[allow(dead_code)]
const MOD: i64 = 998244353;
#[allow(dead_code)]
const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];
#[allow(dead_code)]
pub fn c2d(c: u8)->(usize, usize){match c{b'U'=>(!0,0),b'D'=>(1,0),b'L'=>(0,!0),b'R'=>(0,1),_=>unreachable!()}}
#[allow(dead_code)]
pub fn c2d_i64(c: u8)->(i64, i64){match c{b'U'=>(-1,0),b'D'=>(1,0),b'L'=>(0,-1),b'R'=>(0,1),_=>unreachable!()}}
#[allow(dead_code)]
pub fn join2str<T: ToString>(v: &[T])->String{v.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" ")}
#[allow(dead_code)]
pub fn join2nospace<T: ToString>(v: &[T])->String{v.iter().map(|x| x.to_string()).collect::<Vec<_>>().join("")}
#[allow(dead_code)]
const D2: [(usize, usize); 8] = [(1, 0), (1, 1), (0, 1), (!0, 1), (!0, 0), (!0, !0), (0, !0), (1, !0)];

// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/Basic/basic_io.rs

pub struct Input {
    buf: Vec<u8>,
    pos: usize,
}

impl Input {
    #[inline]
    pub fn new() -> Self {
        let mut buf = Vec::new();
        io::stdin().read_to_end(&mut buf).unwrap();
        buf.push(0);
        Self { buf, pos: 0 }
    }

    #[inline(always)]
    fn skip_whitespace(&mut self) {
        while self.buf[self.pos].is_ascii_whitespace() {
            self.pos += 1;
        }
    }

    #[inline(always)]
    fn token_range(&mut self) -> (usize, usize) {
        self.skip_whitespace();

        let l = self.pos;

        while self.buf[self.pos] > b' ' {
            self.pos += 1;
        }

        (l, self.pos)
    }

    #[inline(always)]
    pub fn byte(&mut self) -> u8 {
        self.skip_whitespace();
        let res = self.buf[self.pos];
        while self.buf[self.pos] > b' ' {
            self.pos += 1;
        }
        res
    }

    #[inline(always)]
    pub fn bytes(&mut self) -> Vec<u8> {
        let (l, r) = self.token_range();
        self.buf[l..r].to_vec()
    }

    #[inline]
    pub fn binary_u64(&mut self) -> Vec<u64> {
        let (l, r) = self.token_range();
        Self::pack_binary(&self.buf[l..r])
    }

    #[inline]
    pub fn binary_u64_len(&mut self, n: usize) -> Vec<u64> {
        if n == 0 {
            return Vec::new();
        }
        self.skip_whitespace();
        let l = self.pos;
        let r = l.checked_add(n).expect("binary token length overflow");
        assert!(r < self.buf.len(), "binary token shorter than requested");
        assert!(
            self.buf[r] == 0 || self.buf[r].is_ascii_whitespace(),
            "binary token longer than requested"
        );
        self.pos = r;
        Self::pack_binary(&self.buf[l..r])
    }

    fn pack_binary(bytes: &[u8]) -> Vec<u64> {
        let mut invalid = 0u64;
        let words = bytes
            .chunks(64)
            .map(|chunk| {
                let mut word = 0;
                let mut groups = chunk.chunks_exact(8);
                for (i, group) in groups.by_ref().enumerate() {
                    let raw = u64::from_le_bytes(group.try_into().unwrap());
                    invalid |= (raw & 0xfefe_fefe_fefe_fefe) ^ 0x3030_3030_3030_3030;
                    let bits = raw & 0x0101_0101_0101_0101;
                    let packed = bits.wrapping_mul(0x0102_0408_1020_4080) >> 56;
                    word |= packed << (i * 8);
                }
                let offset = (chunk.len() / 8) * 8;
                for (i, &c) in groups.remainder().iter().enumerate() {
                    invalid |= ((c & 0xfe) ^ b'0') as u64;
                    word |= ((c & 1) as u64) << (offset + i);
                }
                word
            })
            .collect();
        assert_eq!(invalid, 0, "binary token must contain only 0 and 1");
        words
    }

    #[inline(always)]
    pub fn string(&mut self) -> String {
        let (l, r) = self.token_range();

        unsafe { String::from_utf8_unchecked(self.buf[l..r].to_vec()) }
    }

    #[inline(always)]
    pub fn char(&mut self) -> char {
        let (l, r) = self.token_range();

        unsafe {
            std::str::from_utf8_unchecked(&self.buf[l..r])
                .chars()
                .next()
                .unwrap()
        }
    }

    #[inline(always)]
    pub fn chars(&mut self) -> Vec<char> {
        let (l, r) = self.token_range();

        unsafe {
            std::str::from_utf8_unchecked(&self.buf[l..r])
                .chars()
                .collect()
        }
    }

    #[inline]
    pub fn f64(&mut self) -> f64 {
        let (l, r) = self.token_range();

        unsafe {
            std::str::from_utf8_unchecked(&self.buf[l..r])
                .parse()
                .unwrap()
        }
    }

    #[inline(always)]
    pub fn usize1(&mut self) -> usize {
        self.usize() - 1
    }

    #[inline]
    pub fn vec_byte(&mut self, n: usize) -> Vec<u8> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.byte());
        }

        res
    }

    #[inline]
    pub fn vec_bytes(&mut self, n: usize) -> Vec<Vec<u8>> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.bytes());
        }
        res
    }

    #[inline]
    pub fn vec_string(&mut self, n: usize) -> Vec<String> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.string());
        }

        res
    }

    #[inline]
    pub fn vec_char(&mut self, n: usize) -> Vec<char> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.char());
        }

        res
    }

    #[inline]
    pub fn vec_chars(&mut self, n: usize) -> Vec<Vec<char>> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.chars());
        }

        res
    }

    #[inline]
    pub fn byte_grid(&mut self, n: usize) -> Vec<Vec<u8>> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.bytes());
        }

        res
    }

    #[inline]
    pub fn vec_f64(&mut self, n: usize) -> Vec<f64> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.f64());
        }

        res
    }

    #[inline]
    pub fn vec_usize1(&mut self, n: usize) -> Vec<usize> {
        let mut res = Vec::with_capacity(n);

        for _ in 0..n {
            res.push(self.usize1());
        }

        res
    }
}

macro_rules! impl_unsigned_input {
    ($($name:ident, $vec_name:ident, $t:ty);* $(;)?) => {
        impl Input {
            $(
                #[inline(always)]
                pub fn $name(&mut self) -> $t {
                    let buf = &self.buf;
                    let mut i = self.pos;

                    while buf[i].is_ascii_whitespace() {
                        i += 1;
                    }

                    let mut res: $t = 0;

                    while buf[i].is_ascii_digit() {
                        res = res * 10 + (buf[i] - b'0') as $t;
                        i += 1;
                    }

                    self.pos = i;
                    res
                }

                #[inline]
                pub fn $vec_name(&mut self, n: usize) -> Vec<$t> {
                    let mut res = Vec::with_capacity(n);

                    for _ in 0..n {
                        res.push(self.$name());
                    }

                    res
                }
            )*
        }
    };
}

macro_rules! impl_signed_input {
    ($($name:ident, $vec_name:ident, $t:ty);* $(;)?) => {
        impl Input {
            $(
                #[inline(always)]
                pub fn $name(&mut self) -> $t {
                    let buf = &self.buf;
                    let mut i = self.pos;
                    while buf[i].is_ascii_whitespace() {
                        i += 1;
                    }
                    let neg = buf[i] == b'-';
                    if neg {
                        i += 1;
                    }
                    let mut res: $t = 0;
                    if neg {
                        while buf[i].is_ascii_digit() {
                            res = res * 10 - (buf[i] - b'0') as $t;
                            i += 1;
                        }
                    } else {
                        while buf[i].is_ascii_digit() {
                            res = res * 10 + (buf[i] - b'0') as $t;
                            i += 1;
                        }
                    }

                    self.pos = i;
                    res
                }

                #[inline]
                pub fn $vec_name(&mut self, n: usize) -> Vec<$t> {
                    let mut res = Vec::with_capacity(n);

                    for _ in 0..n {
                        res.push(self.$name());
                    }

                    res
                }
            )*
        }
    };
}

impl_unsigned_input! {
    u8,    vec_u8,    u8;
    u16,   vec_u16,   u16;
    u32,   vec_u32,   u32;
    u64,   vec_u64,   u64;
    u128,  vec_u128,  u128;
    usize, vec_usize, usize;
}

impl_signed_input! {
    i8,   vec_i8,   i8;
    i16,  vec_i16,  i16;
    i32,  vec_i32,  i32;
    i64,  vec_i64,  i64;
    i128, vec_i128, i128;
}

// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/Basic/basic_output.rs
pub struct Output<W: std::io::Write = std::io::Stdout> {
    writer: std::io::BufWriter<W>,
}

impl Output<std::io::Stdout> {
    pub fn new() -> Self {
        Self::from_writer(std::io::stdout())
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_writer_capacity(capacity, std::io::stdout())
    }
}

impl<W: std::io::Write> Output<W> {
    pub fn from_writer(writer: W) -> Self {
        Self::with_writer_capacity(1 << 16, writer)
    }

    pub fn with_writer_capacity(capacity: usize, writer: W) -> Self {
        Self {
            writer: std::io::BufWriter::with_capacity(capacity, writer),
        }
    }

    #[inline(always)]
    pub fn bytes(&mut self, bytes: &[u8]) -> &mut Self {
        std::io::Write::write_all(&mut self.writer, bytes).unwrap();
        self
    }

    #[inline(always)]
    pub fn string(&mut self, s: &str) -> &mut Self {
        self.bytes(s.as_bytes())
    }

    #[inline(always)]
    pub fn byte(&mut self, byte: u8) -> &mut Self {
        self.bytes(&[byte])
    }

    #[inline(always)]
    pub fn space(&mut self) -> &mut Self {
        self.byte(b' ')
    }

    #[inline(always)]
    pub fn newline(&mut self) -> &mut Self {
        self.byte(b'\n')
    }

    pub fn flush(&mut self) -> std::io::Result<()> {
        std::io::Write::flush(&mut self.writer)
    }

    pub fn into_inner(self) -> Result<W, std::io::IntoInnerError<std::io::BufWriter<W>>> {
        self.writer.into_inner()
    }
}

const OUTPUT_DIGIT_PAIRS: &[u8; 200] = b"00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";

macro_rules! impl_unsigned_output {
    ($($name:ident, $line:ident, $helper:ident, $t:ty, $digits:expr);* $(;)?) => {
        impl<W: std::io::Write> Output<W> {
            $(
                #[inline(always)]
                fn $helper<const LINE: bool>(&mut self, mut value: $t) -> &mut Self {
                    let mut buf = [0u8; $digits + 1];
                    let mut at = buf.len();
                    if LINE {
                        at -= 1;
                        buf[at] = b'\n';
                    }
                    while value >= 100 {
                        let pair = (value % 100) as usize * 2;
                        value /= 100;
                        at -= 2;
                        buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
                    }
                    if value >= 10 {
                        let pair = value as usize * 2;
                        at -= 2;
                        buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
                    } else {
                        at -= 1;
                        buf[at] = b'0' + value as u8;
                    }
                    self.bytes(&buf[at..])
                }

                #[inline(always)]
                pub fn $name(&mut self, value: $t) -> &mut Self {
                    self.$helper::<false>(value)
                }

                #[inline(always)]
                pub fn $line(&mut self, value: $t) -> &mut Self {
                    self.$helper::<true>(value)
                }
            )*
        }
    };
}

macro_rules! impl_signed_output {
    ($($name:ident, $line:ident, $helper:ident, $t:ty, $digits:expr);* $(;)?) => {
        impl<W: std::io::Write> Output<W> {
            $(
                #[inline(always)]
                fn $helper<const LINE: bool>(&mut self, value: $t) -> &mut Self {
                    let mut magnitude = value.unsigned_abs();
                    let mut buf = [0u8; $digits + 2];
                    let mut at = buf.len();
                    if LINE {
                        at -= 1;
                        buf[at] = b'\n';
                    }
                    while magnitude >= 100 {
                        let pair = (magnitude % 100) as usize * 2;
                        magnitude /= 100;
                        at -= 2;
                        buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
                    }
                    if magnitude >= 10 {
                        let pair = magnitude as usize * 2;
                        at -= 2;
                        buf[at..at + 2].copy_from_slice(&OUTPUT_DIGIT_PAIRS[pair..pair + 2]);
                    } else {
                        at -= 1;
                        buf[at] = b'0' + magnitude as u8;
                    }
                    if value < 0 {
                        at -= 1;
                        buf[at] = b'-';
                    }
                    self.bytes(&buf[at..])
                }

                #[inline(always)]
                pub fn $name(&mut self, value: $t) -> &mut Self {
                    self.$helper::<false>(value)
                }

                #[inline(always)]
                pub fn $line(&mut self, value: $t) -> &mut Self {
                    self.$helper::<true>(value)
                }
            )*
        }
    };
}

impl_unsigned_output! {
    u8,    u8_line,    write_u8,    u8,    3;
    u16,   u16_line,   write_u16,   u16,   5;
    u32,   u32_line,   write_u32,   u32,   10;
    u64,   u64_line,   write_u64,   u64,   20;
    u128,  u128_line,  write_u128,  u128,  39;
    usize, usize_line, write_usize, usize, 20;
}

impl_signed_output! {
    i8,    i8_line,    write_i8,    i8,    3;
    i16,   i16_line,   write_i16,   i16,   5;
    i32,   i32_line,   write_i32,   i32,   10;
    i64,   i64_line,   write_i64,   i64,   20;
    i128,  i128_line,  write_i128,  i128,  39;
    isize, isize_line, write_isize, isize, 20;
}

// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/DataStructure/predecessor64.rs
#[derive(Clone, Debug)]
pub struct Predecessor64 {
    mx: usize,
    data: Vec<u64>,
    offset: [usize; 11],
    levels: usize,
}

impl Predecessor64 {
    pub fn new(mx: usize) -> Self {
        let (offset, levels, total) = Self::layout(mx.max(1).div_ceil(64));
        Self {
            mx: mx.max(1),
            data: vec![0; total],
            offset,
            levels,
        }
    }

    fn layout(mut len: usize) -> ([usize; 11], usize, usize) {
        let mut offset = [0; 11];
        let mut levels = 0;
        let mut total = 0;
        loop {
            offset[levels] = total;
            levels += 1;
            total += len;
            if len <= 1 {
                break;
            }
            len = len.div_ceil(64);
        }
        (offset, levels, total)
    }

    pub fn from_vec_u64(mut base: Vec<u64>) -> Self {
        if base.is_empty() {
            return Self::new(1);
        }
        let mx = base.len().checked_mul(64).expect("universe size overflow");
        let (offset, levels, total) = Self::layout(base.len());
        base.reserve_exact(total - base.len());
        base.resize(total, 0);
        for i in 1..levels {
            let (lower, upper) = base.split_at_mut(offset[i]);
            let lower = &lower[offset[i - 1]..];
            let mut chunks = lower.chunks_exact(64);
            let mut words = upper.iter_mut();
            for (chunk, word) in (&mut chunks).zip(&mut words) {
                let mut bits = 0;
                for j in 0..64 {
                    bits |= ((chunk[j] != 0) as u64) << j;
                }
                *word = bits;
            }
            if let Some(word) = words.next() {
                let mut bits = 0;
                for (j, &v) in chunks.remainder().iter().enumerate() {
                    bits |= ((v != 0) as u64) << j;
                }
                *word = bits;
            }
        }
        Self {
            mx,
            data: base,
            offset,
            levels,
        }
    }

    pub fn from_vec_usize(base: Vec<usize>) -> Self {
        Self::from_vec_u64(base.into_iter().map(|v| v as u64).collect())
    }

    pub fn from_01_string(s: String) -> Self {
        let mut base = Vec::with_capacity(s.len().div_ceil(64));
        for chunk in s.as_bytes().chunks(64) {
            let mut word = 0;
            let mut groups = chunk.chunks_exact(8);
            for (i, group) in (&mut groups).enumerate() {
                let mut bytes = [0; 8];
                for j in 0..8 {
                    bytes[j] = (group[j] == b'1') as u8;
                }
                let bits = u64::from_le_bytes(bytes).wrapping_mul(0x0102_0408_1020_4080) >> 56;
                word |= bits << (i * 8);
            }
            let start = chunk.len() & !7;
            for (j, &c) in groups.remainder().iter().enumerate() {
                word |= ((c == b'1') as u64) << (start + j);
            }
            base.push(word);
        }
        Self::from_vec_u64(base)
    }

    #[inline(always)]
    fn word(&self, index: usize) -> u64 {
        // SAFETY: callers use layout indices; public positions are checked against mx.
        unsafe { *self.data.get_unchecked(index) }
    }

    #[inline(always)]
    fn word_mut(&mut self, index: usize) -> &mut u64 {
        // SAFETY: checked leaf positions and nonempty/empty transitions stay within layout.
        unsafe { self.data.get_unchecked_mut(index) }
    }

    #[inline(always)]
    pub fn insert(&mut self, mut p: usize) {
        assert!(p < self.mx);
        let word = self.word_mut(p >> 6);
        let old = *word;
        *word |= 1 << (p & 63);
        if old != 0 {
            return;
        }
        for i in 1..self.levels {
            p >>= 6;
            let word = self.word_mut(self.offset[i] + (p >> 6));
            let old = *word;
            *word |= 1 << (p & 63);
            if old != 0 {
                return;
            }
        }
    }

    #[inline(always)]
    pub fn remove(&mut self, mut p: usize) {
        assert!(p < self.mx);
        let word = self.word_mut(p >> 6);
        let old = *word;
        *word &= !(1 << (p & 63));
        if *word != 0 || old == 0 {
            return;
        }
        for i in 1..self.levels {
            p >>= 6;
            let word = self.word_mut(self.offset[i] + (p >> 6));
            let old = *word;
            *word &= !(1 << (p & 63));
            if *word != 0 || old == 0 {
                return;
            }
        }
    }

    #[inline(always)]
    pub fn include(&self, p: usize) -> bool {
        if p >= self.mx {
            return false;
        }
        self.word(p >> 6) & (1 << (p & 63)) != 0
    }
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.word(self.offset[self.levels - 1]) == 0
    }
    #[inline(always)]
    pub fn min(&self) -> usize {
        self.extreme::<true>()
    }
    #[inline(always)]
    pub fn max(&self) -> usize {
        self.extreme::<false>()
    }
    #[inline(always)]
    fn extreme<const MIN: bool>(&self) -> usize {
        let leaf_index = if MIN { 0 } else { (self.mx - 1) >> 6 };
        let leaf = self.word(leaf_index);
        if leaf != 0 {
            let bit = if MIN {
                leaf.trailing_zeros() as usize
            } else {
                63 - leaf.leading_zeros() as usize
            };
            return (leaf_index << 6) | bit;
        }
        let mut word = self.word(self.offset[self.levels - 1]);
        if word == 0 {
            return !0;
        }
        let mut p = if MIN {
            word.trailing_zeros() as usize
        } else {
            63 - word.leading_zeros() as usize
        };
        for i in (0..self.levels - 1).rev() {
            word = self.word(self.offset[i] + p);
            let bit = if MIN {
                word.trailing_zeros() as usize
            } else {
                63 - word.leading_zeros() as usize
            };
            p = (p << 6) | bit;
        }
        p
    }

    #[inline(always)]
    pub fn prev(&self, p: usize) -> usize {
        self.search_prev::<false>(p)
    }
    #[inline(always)]
    pub fn inprev(&self, p: usize) -> usize {
        self.search_prev::<true>(p)
    }
    #[inline(always)]
    pub fn next(&self, p: usize) -> usize {
        self.search_next::<false>(p)
    }
    #[inline(always)]
    pub fn innext(&self, p: usize) -> usize {
        self.search_next::<true>(p)
    }

    #[inline(always)]
    fn search_prev<const INCLUSIVE: bool>(&self, mut p: usize) -> usize {
        if p >= self.mx {
            return self.max();
        }
        let mask = if INCLUSIVE {
            u64::MAX >> (63 - (p & 63))
        } else {
            (1u64 << (p & 63)) - 1
        };
        let word = self.word(p >> 6) & mask;
        if word != 0 {
            return (p & !63) | (63 - word.leading_zeros() as usize);
        }
        for i in 1..self.levels {
            p >>= 6;
            let word = self.word(self.offset[i] + (p >> 6)) & ((1u64 << (p & 63)) - 1);
            if word != 0 {
                let mut res = (p & !63) | (63 - word.leading_zeros() as usize);
                for j in (0..i).rev() {
                    res = (res << 6)
                        | (63 - self.word(self.offset[j] + res).leading_zeros() as usize);
                }
                return res;
            }
        }
        !0
    }

    #[inline(always)]
    fn search_next<const INCLUSIVE: bool>(&self, mut p: usize) -> usize {
        if p >= self.mx {
            return !0;
        }
        let mask = if INCLUSIVE {
            u64::MAX << (p & 63)
        } else {
            (u64::MAX << (p & 63)) << 1
        };
        let word = self.word(p >> 6) & mask;
        if word != 0 {
            return (p & !63) | (word.trailing_zeros() as usize);
        }
        for i in 1..self.levels {
            p >>= 6;
            let word = self.word(self.offset[i] + (p >> 6)) & ((u64::MAX << (p & 63)) << 1);
            if word != 0 {
                let mut res = (p & !63) | (word.trailing_zeros() as usize);
                for j in (0..i).rev() {
                    res = (res << 6) | (self.word(self.offset[j] + res).trailing_zeros() as usize);
                }
                return res;
            }
        }
        !0
    }
}

// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/OfflineQuery/mo.rs
pub trait MoState {
    type Data;
    type Query;
    type Ans;
    fn add_left(&mut self, idx: usize, data: &Self::Data);
    fn add_right(&mut self, idx: usize, data: &Self::Data);
    fn sub_left(&mut self, idx: usize, data: &Self::Data);
    fn sub_right(&mut self, idx: usize, data: &Self::Data);
    fn ans(&mut self, query_id: usize, q_data: &Self::Query) -> Self::Ans;
}

pub trait SymMoState {
    type Data;
    type Query;
    type Ans;
    fn add(&mut self, idx: usize, data: &Self::Data);
    fn sub(&mut self, idx: usize, data: &Self::Data);
    fn ans(&mut self, query_id: usize, q_data: &Self::Query) -> Self::Ans;
}

impl<M: SymMoState> MoState for M {
    type Data = <M as SymMoState>::Data;
    type Query = <M as SymMoState>::Query;
    type Ans = <M as SymMoState>::Ans;

    #[inline]
    fn add_left(&mut self, idx: usize, data: &Self::Data) {
        self.add(idx, data);
    }
    #[inline]
    fn add_right(&mut self, idx: usize, data: &Self::Data) {
        self.add(idx, data);
    }
    #[inline]
    fn sub_left(&mut self, idx: usize, data: &Self::Data) {
        self.sub(idx, data);
    }
    #[inline]
    fn sub_right(&mut self, idx: usize, data: &Self::Data) {
        self.sub(idx, data);
    }
    #[inline]
    fn ans(&mut self, query_id: usize, q_data: &Self::Query) -> Self::Ans {
        SymMoState::ans(self, query_id, q_data)
    }
}

pub struct MoQuery {
    pub l: usize,
    pub r: usize,
    pub id: usize,
}

pub struct MoSolver<M: MoState> {
    data: Vec<M::Data>,
    query: Vec<(MoQuery, M::Query)>,
}

impl<M> MoSolver<M>
where
    M: MoState,
{
    pub fn new(data: Vec<M::Data>) -> Self {
        MoSolver {
            data,
            query: Vec::new(),
        }
    }

    pub fn add_query(&mut self, l: usize, r: usize, qd: M::Query) {
        self.query.push((
            MoQuery {
                l,
                r,
                id: self.query.len(),
            },
            qd,
        ));
    }

    #[inline]
    fn hilbert_order(x: u32, y: u32, pow: u32, mut rot: u32) -> u64 {
        let mut ord = 0;
        let mut flip = 0;
        for p in (0..pow).rev() {
            let rx = (x >> p) & 1;
            let ry = (y >> p) & 1;
            let seg = ((ry * 3 ^ rx) + rot) & 3;
            rot = (rot + [3, 0, 0, 1][seg as usize]) & 3;
            ord = (ord << 2) | ((seg ^ flip) as u64);
            if seg == 0 || seg == 3 {
                flip ^= 3;
            }
        }
        ord
    }

    fn get_ord(&self) -> Vec<usize> {
        let mx = self
            .query
            .iter()
            .map(|(q, _)| q.l.max(q.r))
            .max()
            .unwrap_or(0);
        let pow = if mx == 0 {
            0
        } else {
            (usize::BITS - mx.leading_zeros()) as u32
        };
        let mut ord = (0..self.query.len())
            .map(|i| {
                let q = &self.query[i].0;
                (Self::hilbert_order(q.l as u32, q.r as u32, pow, 0), i)
            })
            .collect::<Vec<_>>();
        ord.sort_unstable_by_key(|&(key, _)| key);
        ord.into_iter().map(|(_, i)| i).collect()
    }

    pub fn solve(&mut self, state: &mut M) -> Vec<M::Ans> {
        let q = self.query.len();
        let mut res: Vec<Option<M::Ans>> = (0..q).map(|_| None).collect();
        let ord = self.get_ord();
        let mut l = 0;
        let mut r = 0;
        for qi in ord {
            let (query, qd) = &self.query[qi];
            if l > query.l {
                for (offset, value) in self.data[query.l..l].iter().enumerate().rev() {
                    state.add_left(query.l + offset, value);
                }
                l = query.l;
            }
            if r < query.r {
                for (offset, value) in self.data[r..query.r].iter().enumerate() {
                    state.add_right(r + offset, value);
                }
                r = query.r;
            }
            if l < query.l {
                for (offset, value) in self.data[l..query.l].iter().enumerate() {
                    state.sub_left(l + offset, value);
                }
                l = query.l;
            }
            if r > query.r {
                for (offset, value) in self.data[query.r..r].iter().enumerate().rev() {
                    state.sub_right(query.r + offset, value);
                }
                r = query.r;
            }
            res[query.id] = Some(state.ans(query.id, qd));
        }
        res.into_iter().map(|x| x.unwrap()).collect()
    }
}

// Source: https://github.com/InverseAki/arcaki_library/blob/main/src/Basic/integer_sort.rs
mod integer_sort_private {
    pub trait Sealed {}
}

pub trait IntegerSortValue: Copy + Ord + integer_sort_private::Sealed {
    fn sort_key(self) -> u64;
    fn from_sort_key(key: u64) -> Self;
}

macro_rules! integer_sort_unsigned {
    ($($t:ty),*) => {$(
        impl integer_sort_private::Sealed for $t {}
        impl IntegerSortValue for $t {
            #[inline]
            fn sort_key(self) -> u64 { self as u64 }
            #[inline]
            fn from_sort_key(key: u64) -> Self { key as Self }
        }
    )*};
}
integer_sort_unsigned!(u32, u64, usize);

impl integer_sort_private::Sealed for i64 {}
impl IntegerSortValue for i64 {
    #[inline]
    fn sort_key(self) -> u64 {
        (self as u64) ^ (1 << 63)
    }
    #[inline]
    fn from_sort_key(key: u64) -> Self {
        (key ^ (1 << 63)) as Self
    }
}

pub fn integer_sort<T: IntegerSortValue>(values: &mut [T]) {
    integer_sort_with_buffer(values, &mut Vec::new());
}

pub fn integer_sort_with_buffer<T: IntegerSortValue>(values: &mut [T], buffer: &mut Vec<T>) {
    let n = values.len();
    if n <= 128 {
        values.sort_unstable();
        return;
    }
    if values.is_sorted() {
        return;
    }
    if values.windows(2).all(|w| w[0] >= w[1]) {
        values.reverse();
        return;
    }
    let first = values[0].sort_key();
    let mut low = first;
    let mut high = first;
    let mut varying = 0;
    for &value in values.iter() {
        let key = value.sort_key();
        low = low.min(key);
        high = high.max(key);
        varying |= key ^ first;
    }
    let offset = varying.trailing_zeros();
    let range = (high - low) >> offset;
    if range <= 65535 && range < (n / 8) as u64 {
        let mut counts = vec![0usize; range as usize + 1];
        for &value in values.iter() {
            counts[((value.sort_key() - low) >> offset) as usize] += 1;
        }
        let mut pos = 0;
        for (i, count) in counts.into_iter().enumerate() {
            if count != 0 {
                values[pos..pos + count].fill(T::from_sort_key(low + ((i as u64) << offset)));
                pos += count;
            }
        }
        return;
    }
    let mut width = 64 - varying.leading_zeros() - offset;
    let mut base = 0;
    let normalized_width = 64 - range.leading_zeros();
    if normalized_width < width {
        width = normalized_width;
        base = low;
        varying = (u64::MAX >> range.leading_zeros()) << offset;
    }
    if (n < 1024 && width > 16) || (n < 8192 && width > 32) {
        values.sort_unstable();
        return;
    }
    buffer.resize(n, values[0]);
    if width == 9 {
        integer_sort_radix::<T, 512>(values, &mut buffer[..n], varying, base);
    } else if width == 10 {
        integer_sort_radix::<T, 1024>(values, &mut buffer[..n], varying, base);
    } else if width == 11 {
        integer_sort_radix::<T, 2048>(values, &mut buffer[..n], varying, base);
    } else if n < 2048 || width <= 16 {
        integer_sort_radix::<T, 256>(values, &mut buffer[..n], varying, base);
    } else {
        integer_sort_radix::<T, 2048>(values, &mut buffer[..n], varying, base);
    }
}

fn integer_sort_radix<T: IntegerSortValue, const BINS: usize>(
    values: &mut [T],
    buffer: &mut [T],
    mut varying: u64,
    base: u64,
) {
    let bits = BINS.trailing_zeros();
    let mask = BINS - 1;
    let mut shift = varying.trailing_zeros();
    varying >>= shift;
    let mut source = values;
    let mut target = buffer;
    let mut in_buffer = false;
    while varying != 0 {
        if varying & mask as u64 != 0 {
            if source.is_sorted() {
                break;
            }
            let mut counts = [0usize; BINS];
            for &value in source.iter() {
                counts[((value.sort_key() - base) >> shift) as usize & mask] += 1;
            }
            let mut sum = 0;
            for count in counts.iter_mut() {
                let len = *count;
                *count = sum;
                sum += len;
            }
            for &value in source.iter() {
                let pos = &mut counts[((value.sort_key() - base) >> shift) as usize & mask];
                target[*pos] = value;
                *pos += 1;
            }
            std::mem::swap(&mut source, &mut target);
            in_buffer = !in_buffer;
        }
        varying >>= bits;
        shift += bits;
    }
    if in_buffer {
        target.copy_from_slice(source);
    }
}

struct M{
    c1: Vec<i32>,
    c2: Vec<i32>,
    b: Vec<u32>,
    seg1: Predecessor64,
    seg2: Predecessor64,
}

#[inline(always)]
fn inc(p: usize, c2: &mut [i32], seg: &mut Predecessor64){
    if c2[p]==0 {
        seg.insert(p);
    }
    c2[p] += 1;
}

#[inline(always)]
fn dec(p: usize, c2: &mut [i32], seg: &mut Predecessor64){
    c2[p] -= 1;
    if c2[p]==0 {
        seg.remove(p);
    }
}

impl SymMoState for M{
    type Data = usize;

    type Query = (usize, bool);

    type Ans = usize;

    fn add(&mut self, _idx: usize, &p: &Self::Data) {
        let bp = self.b[p]as usize;
        if self.c1[p]==0 {
            let l = self.seg1.prev(p);
            let r = self.seg1.next(p);
            if l==!0 {
                if r!=!0 {
                    inc(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
                }
            } else if r==!0 {
                if l!=!0 {
                    inc(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
                }
            } else {
                dec((self.b[r]-self.b[l])as usize, &mut self.c2, &mut self.seg2);
                inc(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
                inc(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
            }
            self.seg1.insert(p);
        } else {
            inc(0, &mut self.c2, &mut self.seg2);
        }
        self.c1[p] += 1;
    }

    fn sub(&mut self, _idx: usize, &p: &Self::Data) {
        let bp = self.b[p]as usize;
        self.c1[p]-=1;
        if self.c1[p]==0 {
            let l = self.seg1.prev(p);
            let r = self.seg1.next(p);
            if l==!0 {
                if r!=!0 {
                    dec(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
                }
            } else if r==!0 {
                if l!=!0 {
                    dec(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
                }
            } else {
                inc((self.b[r]-self.b[l])as usize, &mut self.c2, &mut self.seg2);
                dec(self.b[r]as usize-bp, &mut self.c2, &mut self.seg2);
                dec(bp-self.b[l]as usize, &mut self.c2, &mut self.seg2);
            }
            self.seg1.remove(p);
        } else {
            dec(0, &mut self.c2, &mut self.seg2);
        }
    }

    fn ans(&mut self, _query_id: usize, &q_data: &Self::Query) -> Self::Ans {
        let (x, f) = q_data;
        if f {
            self.seg2.inprev(x)
        } else {
            self.seg2.innext(x)
        }
    }
}

#[allow(unused)]
type MI = StaticModInt<Mod998244353>;
const MULTI: bool = false;
//#[fastout]
fn solve(){
    let mut ip = Input::new();
    let mut o = Output::new();
    let n = ip.usize();
    let q = ip.usize();
    let a = (0..n).map(|_| ip.u32()).collect::<Vec<_>>();
    let mut z = a.clone();
    integer_sort(&mut z);
    let mut map = FxMap::default();
    for (i, &v) in z.iter().enumerate(){
        map.insert(v, i);
    }
    let b = a.into_iter().map(|x| map[&x]).collect::<Vec<_>>();
    let mut mo = MoSolver::new(b);
    for _ in 0..q {
        let (l,r)=(ip.usize1(),ip.usize());
        let (x, c) = (ip.usize(), ip.byte()==b'L');
        mo.add_query(l, r, (x, c));
    }
    let m = z.len();
    for x in mo.solve(&mut M{b:z.clone(), c1: vec![0;m], c2: vec![0;10000000],seg1: Predecessor64::new(m), seg2: Predecessor64::new(10000000)}){
        o.i32_line(x as i32);
    }
}

fn main() {
    if MULTI{
        input!{
            t: usize,
        }
        for _ in 0..t{
            solve();
        }
    } else {
        solve();
    }
}