#![allow(unused_imports, non_snake_case)]
#![allow(dead_code)]
use crate::{
    arraylist::List,
    data_structure::{implicit_treap::ImplicitTreap, monoid::MaxUpdate},
    scanner::Scanner,
};
fn main() {
    let mut scan = Scanner::new();
    let q = scan.int();
    let k = scan.int();
    let mut treap = ImplicitTreap::<MaxUpdate>::new();
    let mut ret = list!();
    for _ in 0..q {
        let tpe = scan.int();
        if tpe == 1 {
            let v = scan.long();
            let i = treap.binary_search(.., v, true);
            treap.insert(i, v);
        } else {
            let r;
            if treap.lens() >= k {
                r = treap.get(k - 1);
                treap.remove(k - 1);
            } else {
                r = -1;
            }
            ret.push(r);
        }
    }
    println!("{}", ret.join("\n"));
}
pub mod data_structure {
    pub mod implicit_treap {
        use crate::data_structure::monoid::{MapMonoid, Monoid};
        use crate::{ext::range::IntRangeBounds, independent::random::Random};
        use std::{
            cmp::Ordering,
            fmt::{Debug, Display, Formatter},
            iter::FromIterator,
            ops::RangeBounds,
        };
        pub struct Node<F: MapMonoid> {
            pub value: <F::M as Monoid>::S,
            pub acc: <F::M as Monoid>::S,
            pub lazy: F::F,
            pub rev: bool,
            pub priority: u64,
            pub len: isize,
            pub left: Tree<F>,
            pub right: Tree<F>,
        }
        impl<F: MapMonoid> Node<F> {
            pub fn new(value: <F::M as Monoid>::S, priority: u64) -> Node<F> {
                Node {
                    value,
                    acc: value,
                    lazy: F::id(),
                    rev: false,
                    priority,
                    len: 1,
                    left: None,
                    right: None,
                }
            }
            pub fn pushup(&mut self) {
                self.update_cnt();
                self.update_acc();
            }
            fn update_cnt(&mut self) {
                let Node {
                    ref mut len,
                    ref left,
                    ref right,
                    ..
                } = self;
                *len = 1;
                *len += get_len(left);
                *len += get_len(right);
            }
            fn update_acc(&mut self) {
                let Node {
                    ref mut acc,
                    ref value,
                    ref left,
                    ref right,
                    ..
                } = self;
                *acc = F::op(get_acc(left), F::op(*value, get_acc(right)));
            }
            pub fn pushdown(&mut self) {
                let Node {
                    ref mut value,
                    ref mut lazy,
                    ref mut rev,
                    ref mut left,
                    ref mut right,
                    ..
                } = self;
                if *rev {
                    *rev = false;
                    std::mem::swap(left, right);
                    if let Some(node) = left {
                        node.rev ^= true;
                    }
                    if let Some(node) = right {
                        node.rev ^= true;
                    }
                }
                if *lazy != F::id() {
                    if let Some(l) = left {
                        l.lazy = F::composite(*lazy, l.lazy);
                        l.acc = F::map(F::p(*lazy, l.len), l.acc);
                    }
                    if let Some(r) = right {
                        r.lazy = F::composite(*lazy, r.lazy);
                        r.acc = F::map(F::p(*lazy, r.len), r.acc);
                    }
                    *value = F::map(F::p(*lazy, 1), *value);
                    *lazy = F::id();
                }
                self.pushup();
            }
            pub fn implicit_key(&self) -> isize {
                self.left.as_ref().map_or(1, |node| node.len + 1)
            }
        }
        type Tree<F> = Option<Box<Node<F>>>;
        fn get_acc<F: MapMonoid>(tree: &Tree<F>) -> <F::M as Monoid>::S {
            tree.as_ref().map_or(F::zero(), |node| node.acc)
        }
        fn get_len<F: MapMonoid>(tree: &Tree<F>) -> isize {
            tree.as_ref().map_or(0, |node| node.len)
        }
        fn get_value<F: MapMonoid>(tree: &Tree<F>) -> <F::M as Monoid>::S {
            tree.as_ref().map_or(F::zero(), |node| node.value)
        }
        fn get_children<F: MapMonoid>(tree: &Tree<F>) -> (&Tree<F>, &Tree<F>) {
            if let Some(node) = tree {
                let Node {
                    ref left,
                    ref right,
                    ..
                } = &**node;
                (left, right)
            } else {
                (&None, &None)
            }
        }
        fn merge<F: MapMonoid>(l_tree: &mut Tree<F>, mut r_tree: Tree<F>) {
            if let Some(l_node) = l_tree {
                l_node.pushdown();
            }
            if let Some(r_node) = &mut r_tree {
                r_node.pushdown();
            }
            match (l_tree.take(), r_tree) {
                (Some(mut l_node), Some(mut r_node)) => {
                    if l_node.priority > r_node.priority {
                        merge(&mut l_node.right, Some(r_node));
                        l_node.pushup();
                        *l_tree = Some(l_node);
                    } else {
                        let mut new_tree = Some(l_node);
                        merge(&mut new_tree, r_node.left.take());
                        r_node.left = new_tree;
                        r_node.pushup();
                        *l_tree = Some(r_node);
                    }
                }
                (new_tree, None) | (None, new_tree) => *l_tree = new_tree,
            }
        }
        fn split<F: MapMonoid>(tree: &mut Tree<F>, index: isize, left_inclusive: bool) -> Tree<F> {
            match tree.take() {
                Some(mut node) => {
                    node.pushdown();
                    let key = node.implicit_key();
                    let cmp = index.cmp(&key);
                    let ret;
                    if cmp == Ordering::Less || (cmp == Ordering::Equal && left_inclusive) {
                        let res = split(&mut node.left, index, left_inclusive);
                        *tree = node.left.take();
                        node.left = res;
                        node.pushup();
                        ret = Some(node);
                    } else {
                        ret = split(&mut node.right, index - key, left_inclusive);
                        node.pushup();
                        *tree = Some(node);
                    }
                    ret
                }
                None => None,
            }
        }
        fn query<F: MapMonoid, B>(tree: &mut Tree<F>, range: B) -> <F::M as Monoid>::S
        where
            B: RangeBounds<isize>,
        {
            let len = get_len(tree);
            if range.empty() {
                return F::zero();
            }
            let ran = range.to_harfopen(0, len);
            let mut tree2 = split(tree, ran.start, false);
            let tree3 = split(&mut tree2, ran.end - ran.start, false);
            let ret = get_acc(&tree2);
            merge(&mut tree2, tree3);
            merge(tree, tree2);
            ret
        }
        fn set<F: MapMonoid>(tree: &mut Tree<F>, index: isize, mut item: Tree<F>) {
            let mut tree2 = split(tree, index, false);
            let tree3 = split(&mut tree2, 1, false);
            merge(&mut item, tree3);
            merge(tree, item);
        }
        fn get<F: MapMonoid>(tree: &mut Tree<F>, index: isize) -> <F::M as Monoid>::S {
            let mut tree2 = split(tree, index, false);
            let tree3 = split(&mut tree2, 1, false);
            let ret = tree2.as_ref().map_or(F::zero(), |node| node.value);
            merge(&mut tree2, tree3);
            merge(tree, tree2);
            ret
        }
        fn apply_range<B, F: MapMonoid>(tree: &mut Tree<F>, range: B, x: F::F)
        where
            B: RangeBounds<isize>,
        {
            if range.empty() {
                return;
            }
            let ran = range.to_harfopen(0, get_len(tree));
            let mut tree2 = split(tree, ran.start, false);
            let tree3 = split(&mut tree2, ran.end - ran.start, false);
            if let Some(t2) = &mut tree2 {
                t2.lazy = F::composite(x, t2.lazy);
                t2.acc = F::map(F::p(x, t2.len), t2.acc);
            }
            merge(&mut tree2, tree3);
            merge(tree, tree2);
        }
        fn find<F: MapMonoid>(
            tree: &Tree<F>,
            x: <F::M as Monoid>::S,
            offset: isize,
            left: bool,
        ) -> Option<isize> {
            if F::op(get_acc(tree), x) == x {
                None
            } else {
                let (l_tree, r_tree) = get_children(tree);
                if left {
                    if l_tree.is_some() && F::op(get_acc(l_tree), x) != x {
                        find(l_tree, x, offset, left)
                    } else {
                        if F::op(get_value(tree), x) != x {
                            Some(offset + get_len(l_tree))
                        } else {
                            find(r_tree, x, offset + get_len(l_tree) + 1, left)
                        }
                    }
                } else {
                    if r_tree.is_some() && F::op(get_acc(r_tree), x) != x {
                        find(r_tree, x, offset + get_len(l_tree) + 1, left)
                    } else {
                        if F::op(get_value(tree), x) != x {
                            Some(offset + get_len(l_tree))
                        } else {
                            find(l_tree, x, offset, left)
                        }
                    }
                }
            }
        }
        fn pushdown_all<F: MapMonoid>(tree: &mut Tree<F>) {
            if let Some(node) = tree {
                node.pushdown();
                pushdown_all(&mut node.left);
                pushdown_all(&mut node.right);
            }
        }
        fn json<F: MapMonoid>(tree: &Tree<F>) -> String
        where
            <F::M as Monoid>::S: std::fmt::Display,
            F::F: std::fmt::Display,
        {
            if let Some(node) = tree {
                format!(
                    r#"{{"key": {}, "value": {}, "acc": {}, "lazy": {}, "left": {}, "right": {}}}"#,
                    node.implicit_key(),
                    node.value,
                    node.acc,
                    node.lazy,
                    json(&node.left),
                    json(&node.right)
                )
            } else {
                "null".to_owned()
            }
        }
        impl<F: MapMonoid> Display for ImplicitTreap<F>
        where
            <F::M as Monoid>::S: std::fmt::Display,
            F::F: std::fmt::Display,
        {
            fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
                write!(f, "{}", json(&self.tree))
            }
        }
        pub struct ImplicitTreap<M: MapMonoid> {
            tree: Tree<M>,
            rng: Random,
        }
        impl<F: MapMonoid> ImplicitTreap<F> {
            pub fn new() -> ImplicitTreap<F> {
                ImplicitTreap {
                    tree: None,
                    rng: Random::new(),
                }
            }
            pub fn lens(&self) -> isize {
                get_len(&self.tree)
            }
            fn from_tree(&self, tree: Tree<F>) -> Self {
                Self {
                    tree,
                    rng: Random::new(),
                }
            }
            pub fn split(&mut self, key: isize) -> Self {
                let right = split(&mut self.tree, key, false);
                self.from_tree(right)
            }
            pub fn merge(&mut self, right: Self) {
                merge(&mut self.tree, right.tree);
            }
            pub fn insert(&mut self, index: isize, value: <F::M as Monoid>::S) {
                let node = Node::new(value, self.rng.next(std::u64::MAX));
                let right = self.split(index);
                self.merge(self.from_tree(Some(Box::new(node))));
                self.merge(right);
            }
            pub fn query<B>(&mut self, range: B) -> <F::M as Monoid>::S
            where
                B: RangeBounds<isize>,
            {
                query(&mut self.tree, range)
            }
            pub fn get(&mut self, index: isize) -> <F::M as Monoid>::S {
                get(&mut self.tree, index)
            }
            pub fn set(&mut self, index: isize, value: <F::M as Monoid>::S) {
                let node = Node::new(value, self.rng.next(std::u64::MAX));
                set(&mut self.tree, index, Some(Box::new(node)));
            }
            pub fn erase<B>(&mut self, range: B)
            where
                B: RangeBounds<isize>,
            {
                if range.empty() {
                    return;
                }
                let ran = range.to_harfopen(0, self.lens());
                let mut tree2 = self.split(ran.start);
                let tree3 = tree2.split(ran.end - ran.start);
                self.merge(tree3);
            }
            pub fn remove(&mut self, index: isize) {
                self.erase(index..=index);
            }
            pub fn apply_range<B>(&mut self, range: B, x: F::F)
            where
                B: RangeBounds<isize>,
            {
                apply_range(&mut self.tree, range, x);
            }
            pub fn apply(&mut self, index: isize, x: F::F) {
                apply_range(&mut self.tree, index..=index, x);
            }
            #[doc = " - `F::op(acc, value) != value`である最左/最右要素の位置"]
            #[doc = " - MaxMonoidで`left=true`のとき`[range.start, return)`の値は`value`以下"]
            pub fn binary_search<B>(
                &mut self,
                range: B,
                value: <F::M as Monoid>::S,
                left: bool,
            ) -> isize
            where
                B: RangeBounds<isize> + Debug,
            {
                if range.empty() {
                    panic!("invalid range: {:?}", &range);
                }
                let ran = range.to_harfopen(0, self.lens());
                let mut tree2 = self.split(ran.start);
                let tree3 = tree2.split(ran.end - ran.start);
                let ret = find(&tree2.tree, value, ran.start, left);
                tree2.merge(tree3);
                self.merge(tree2);
                ret.unwrap_or(if left { ran.end } else { ran.start - 1 })
            }
            pub fn reverse<B>(&mut self, range: B)
            where
                B: RangeBounds<isize>,
            {
                if range.empty() {
                    return;
                }
                let ran = range.to_harfopen(0, self.lens());
                let mut tree2 = self.split(ran.start);
                let tree3 = tree2.split(ran.end - ran.start);
                if let Some(node) = &mut tree2.tree {
                    node.rev ^= true;
                }
                tree2.merge(tree3);
                self.merge(tree2);
            }
            pub fn rotate<B>(&mut self, range: B, new_head: isize)
            where
                B: RangeBounds<isize>,
            {
                if range.empty() {
                    return;
                }
                let ran = range.to_harfopen(0, self.lens());
                self.reverse(range);
                self.reverse(ran.start..ran.start + ran.end - new_head);
                self.reverse(ran.start + ran.end - new_head..ran.end);
            }
            pub fn iter(&mut self) -> impl Iterator<Item = &<F::M as Monoid>::S> {
                pushdown_all(&mut self.tree);
                (0..).scan((&self.tree, Vec::new()), |(current, stack), _| {
                    while let Some(ref node) = current {
                        *current = &node.left;
                        stack.push(node.as_ref());
                    }
                    stack.pop().map(|node| {
                        *current = &node.right;
                        &node.value
                    })
                })
            }
        }
        impl<F: MapMonoid> FromIterator<<F::M as Monoid>::S> for ImplicitTreap<F> {
            fn from_iter<V: IntoIterator<Item = <F::M as Monoid>::S>>(iter: V) -> Self {
                let mut t = ImplicitTreap::new();
                for i in iter {
                    t.insert(t.lens(), i);
                }
                t
            }
        }
    }
    pub mod monoid {
        pub trait Monoid {
            type S: Copy + Eq;
            fn zero() -> Self::S;
            fn op(a: Self::S, b: Self::S) -> Self::S;
        }
        pub trait MapMonoid {
            type M: Monoid;
            type F: Copy + Eq;
            fn zero() -> <Self::M as Monoid>::S {
                Self::M::zero()
            }
            fn op(a: <Self::M as Monoid>::S, b: <Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
                Self::M::op(a, b)
            }
            fn id() -> Self::F;
            fn map(f: Self::F, x: <Self::M as Monoid>::S) -> <Self::M as Monoid>::S;
            fn composite(provider: Self::F, target: Self::F) -> Self::F;
            fn p(f: Self::F, x: isize) -> Self::F;
        }
        pub struct Max;
        impl Monoid for Max {
            type S = i64;
            fn zero() -> Self::S {
                0
            }
            fn op(a: Self::S, b: Self::S) -> Self::S {
                a.max(b)
            }
        }
        pub struct Min;
        impl Monoid for Min {
            type S = i64;
            fn zero() -> Self::S {
                1i64 << 60
            }
            fn op(a: Self::S, b: Self::S) -> Self::S {
                a.min(b)
            }
        }
        pub struct Sum;
        impl Monoid for Sum {
            type S = i64;
            fn zero() -> Self::S {
                0
            }
            fn op(a: Self::S, b: Self::S) -> Self::S {
                a + b
            }
        }
        pub struct MaxIndex;
        impl Monoid for MaxIndex {
            type S = (i64, isize);
            fn zero() -> Self::S {
                (0, 0)
            }
            fn op(a: Self::S, b: Self::S) -> Self::S {
                a.max(b)
            }
        }
        pub struct MaxAdd;
        impl MapMonoid for MaxAdd {
            type M = Max;
            type F = i64;
            fn id() -> Self::F {
                0
            }
            fn map(f: Self::F, x: i64) -> i64 {
                f + x
            }
            fn composite(f: Self::F, g: Self::F) -> Self::F {
                f + g
            }
            fn p(f: Self::F, _x: isize) -> Self::F {
                f
            }
        }
        pub struct MaxUpdate;
        impl MapMonoid for MaxUpdate {
            type M = Max;
            type F = i64;
            fn id() -> Self::F {
                i64::max_value()
            }
            fn map(f: Self::F, x: i64) -> i64 {
                if f != Self::id() {
                    f
                } else {
                    x
                }
            }
            fn composite(new_value: Self::F, target: Self::F) -> Self::F {
                if new_value != Self::id() {
                    new_value
                } else {
                    target
                }
            }
            fn p(f: Self::F, _x: isize) -> Self::F {
                f
            }
        }
        pub struct MinAdd;
        impl MapMonoid for MinAdd {
            type M = Min;
            type F = i64;
            fn id() -> Self::F {
                0
            }
            fn map(f: Self::F, x: i64) -> i64 {
                f + x
            }
            fn composite(f: Self::F, g: Self::F) -> Self::F {
                f + g
            }
            fn p(f: Self::F, _x: isize) -> Self::F {
                f
            }
        }
        pub struct MinUpdate;
        impl MapMonoid for MinUpdate {
            type M = Min;
            type F = i64;
            fn id() -> Self::F {
                i64::max_value()
            }
            fn map(f: Self::F, x: i64) -> i64 {
                if f != Self::id() {
                    f
                } else {
                    x
                }
            }
            fn composite(new_value: Self::F, target: Self::F) -> Self::F {
                if new_value != Self::id() {
                    new_value
                } else {
                    target
                }
            }
            fn p(f: Self::F, _x: isize) -> Self::F {
                f
            }
        }
    }
}
pub mod independent {
    pub mod random {
        #[derive(Debug, Clone)]
        pub struct Random {
            x: std::num::Wrapping<u64>,
        }
        impl Random {
            pub fn new() -> Random {
                Random {
                    x: std::num::Wrapping(88172645463325252),
                }
            }
            pub fn next(&mut self, n: u64) -> u64 {
                self.x = self.x ^ (self.x << 7);
                self.x = self.x ^ (self.x >> 9);
                self.x.0 % n
            }
            pub fn shuffle<T>(&mut self, arr: &mut [T]) {
                let n = arr.len();
                for i in (0..n - 1).map(|i| n - i) {
                    let j = self.next(i as u64) as usize;
                    arr.swap(i, j);
                }
            }
        }
    }
    pub mod integer {
        use std::fmt::Display;
        pub trait Int:
            std::ops::Add<Output = Self>
            + std::ops::Sub<Output = Self>
            + std::ops::Mul<Output = Self>
            + std::ops::Div<Output = Self>
            + std::ops::Rem<Output = Self>
            + std::ops::AddAssign
            + std::ops::SubAssign
            + std::ops::MulAssign
            + std::ops::DivAssign
            + std::hash::Hash
            + PartialEq
            + Eq
            + PartialOrd
            + Ord
            + Copy
            + Display
        {
            fn to_u8(&self) -> u8;
            fn to_u16(&self) -> u16;
            fn to_u32(&self) -> u32;
            fn to_u64(&self) -> u64;
            fn to_u128(&self) -> u128;
            fn to_i8(&self) -> i8;
            fn to_i16(&self) -> i16;
            fn to_i32(&self) -> i32;
            fn to_i64(&self) -> i64;
            fn to_i128(&self) -> i128;
            fn to_usize(&self) -> usize;
            fn to_isize(&self) -> isize;
            fn from_u8(x: u8) -> Self;
            fn from_u16(x: u16) -> Self;
            fn from_u32(x: u32) -> Self;
            fn from_u64(x: u64) -> Self;
            fn from_u128(x: u128) -> Self;
            fn from_i8(x: i8) -> Self;
            fn from_i16(x: i16) -> Self;
            fn from_i32(x: i32) -> Self;
            fn from_i64(x: i64) -> Self;
            fn from_i128(x: i128) -> Self;
            fn from_usize(x: usize) -> Self;
            fn from_isize(x: isize) -> Self;
            fn zero() -> Self;
            fn one() -> Self;
            fn next(&self) -> Self {
                *self + Self::one()
            }
        }
        macro_rules ! impl_integer_functions { ($ selftpe : ident , $ ($ tofn : ident , $ fromfn : ident , $ tpe : ident) ,*) => { $ (fn $ tofn (& self) -> $ tpe { * self as $ tpe } fn $ fromfn (x : $ tpe) -> Self { x as $ selftpe }) * } ; }
        macro_rules ! impl_integer { ($ ($ tpe : ident) ,*) => { $ (impl Int for $ tpe { impl_integer_functions ! ($ tpe , to_u8 , from_u8 , u8 , to_u16 , from_u16 , u16 , to_u32 , from_u32 , u32 , to_u64 , from_u64 , u64 , to_u128 , from_u128 , u128 , to_i8 , from_i8 , i8 , to_i16 , from_i16 , i16 , to_i32 , from_i32 , i32 , to_i64 , from_i64 , i64 , to_i128 , from_i128 , i128 , to_usize , from_usize , usize , to_isize , from_isize , isize) ; fn zero () -> Self { 0 } fn one () -> Self { 1 } }) * } ; }
        impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
    }
}
pub mod ext {
    pub mod range {
        use crate::independent::integer::Int;
        use std::cmp::{max, min};
        use std::ops::{Bound, Range, RangeBounds};
        pub trait IntRangeBounds<U: Int>: RangeBounds<U> {
            #[doc = " inclusive"]
            fn lbopt(&self) -> Option<U> {
                match self.start_bound() {
                    Bound::Included(x) => Some(*x),
                    Bound::Excluded(x) => Some(*x + U::one()),
                    Bound::Unbounded => None,
                }
            }
            #[doc = " exclusive"]
            fn ubopt(&self) -> Option<U> {
                match self.end_bound() {
                    Bound::Included(x) => Some(*x + U::one()),
                    Bound::Excluded(x) => Some(*x),
                    Bound::Unbounded => None,
                }
            }
            #[doc = " inclusive"]
            fn lower_bound(&self, limit: U) -> U {
                self.lbopt().map_or(limit, |x| max(limit, x))
            }
            #[doc = " exclusive"]
            fn upper_bound(&self, limit: U) -> U {
                self.ubopt().map_or(limit, |x| min(limit, x))
            }
            fn to_harfopen(&self, lb: U, ub: U) -> Range<U> {
                self.lower_bound(lb)..self.upper_bound(ub)
            }
            fn domain_of(&self, mut t: U) -> U {
                if let Some(x) = self.lbopt() {
                    if t < x {
                        t = x;
                    }
                }
                if let Some(x) = self.ubopt() {
                    if x <= t {
                        t = x - U::one();
                    }
                }
                t
            }
            fn width(&self) -> U {
                if self.empty() {
                    U::zero()
                } else {
                    self.ubopt().unwrap() - self.lbopt().unwrap()
                }
            }
            fn empty(&self) -> bool {
                match (self.lbopt(), self.ubopt()) {
                    (Some(lb), Some(ub)) => lb >= ub,
                    (None, _ub) => false,
                    (_lb, None) => false,
                }
            }
            fn contain_range(&self, inner: &Self) -> bool {
                (match (self.lbopt(), inner.lbopt()) {
                    (Some(a), Some(b)) => a <= b,
                    (None, _) => true,
                    (Some(_), None) => false,
                }) && (match (inner.ubopt(), self.ubopt()) {
                    (Some(a), Some(b)) => a <= b,
                    (_, None) => true,
                    (None, Some(_)) => false,
                })
            }
            fn separate_range(&self, other: &Self) -> bool {
                if let (Some(a), Some(b)) = (self.ubopt(), other.lbopt()) {
                    if a <= b {
                        return true;
                    }
                }
                if let (Some(a), Some(b)) = (other.ubopt(), self.lbopt()) {
                    if a <= b {
                        return true;
                    }
                }
                false
            }
            fn overlap(&self, other: &Self) -> Range<U> {
                let left = if let (Some(a), Some(b)) = (self.lbopt(), other.lbopt()) {
                    max(a, b)
                } else {
                    self.lbopt().or(other.lbopt()).unwrap()
                };
                let right = if let (Some(a), Some(b)) = (self.ubopt(), other.ubopt()) {
                    min(a, b)
                } else {
                    self.ubopt().or(other.ubopt()).unwrap()
                };
                left..right
            }
        }
        impl<T: ?Sized, U: Int> IntRangeBounds<U> for T where T: RangeBounds<U> {}
    }
}
pub mod scanner {
    use crate::arraylist::List;
    use std::io::{stdin, BufReader, Bytes, Read, Stdin};
    use std::str::FromStr;
    pub struct Scanner {
        buf: Bytes<BufReader<Stdin>>,
    }
    impl Scanner {
        pub fn new() -> Scanner {
            Scanner {
                buf: BufReader::new(stdin()).bytes(),
            }
        }
        fn token<T: std::iter::FromIterator<char>>(&mut self) -> T {
            self.buf
                .by_ref()
                .map(|c| c.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        }
        pub fn read<T: FromStr>(&mut self) -> T {
            self.string().parse().ok().unwrap()
        }
        pub fn readn<T: FromStr>(&mut self, n: isize) -> List<T> {
            (0..n).map(|_| self.read::<T>()).collect()
        }
        pub fn chars(&mut self) -> List<char> {
            self.token()
        }
        pub fn string(&mut self) -> String {
            self.token()
        }
        pub fn char(&mut self) -> char {
            self.read()
        }
        pub fn int(&mut self) -> isize {
            self.read()
        }
        pub fn long(&mut self) -> i64 {
            self.read()
        }
        pub fn double(&mut self) -> f64 {
            self.read()
        }
    }
}
pub mod arraylist {
    use crate::{ext::range::IntRangeBounds, independent::integer::Int};
    use std::fmt::Formatter;
    use std::iter::FromIterator;
    use std::ops::{Deref, DerefMut, Index, IndexMut, RangeBounds};
    use std::slice::Iter;
    #[derive(Clone, PartialEq, Eq)]
    pub struct List<T> {
        pub vec: Vec<T>,
    }
    impl<T> List<T> {
        #[inline]
        pub fn new() -> List<T> {
            List { vec: vec![] }
        }
        #[inline]
        pub fn init(init: T, n: isize) -> List<T>
        where
            T: Clone,
        {
            List {
                vec: vec![init; n as usize],
            }
        }
        #[inline]
        pub fn from_vec(vec: Vec<T>) -> List<T> {
            List { vec }
        }
        #[inline]
        pub fn gen<'a, S>(n: isize, mut f: S) -> List<T>
        where
            S: FnMut(isize) -> T + 'a,
        {
            (0..n).map(|i| f(i)).collect()
        }
        #[inline]
        pub fn lens(&self) -> isize {
            self.vec.len() as isize
        }
        #[inline]
        pub fn iter(&self) -> Iter<'_, T> {
            self.vec.iter()
        }
        #[inline]
        pub fn push(&mut self, item: T) {
            self.vec.push(item);
        }
        #[inline]
        pub fn sort(&mut self)
        where
            T: Ord,
        {
            self.vec.sort();
        }
        #[inline]
        pub fn reverse(&mut self) {
            self.vec.reverse();
        }
        #[inline]
        pub fn sort_by<F>(&mut self, compare: F)
        where
            F: FnMut(&T, &T) -> std::cmp::Ordering,
        {
            self.vec.sort_by(compare)
        }
        #[inline]
        pub fn sort_by_key<K, F>(&mut self, compare: F)
        where
            F: FnMut(&T) -> K,
            K: Ord,
        {
            self.vec.sort_by_key(compare)
        }
        #[inline]
        pub fn first(&self) -> Option<&T> {
            self.vec.first()
        }
        #[inline]
        pub fn last(&self) -> Option<&T> {
            self.vec.last()
        }
        #[inline]
        pub fn first_mut(&mut self) -> Option<&mut T> {
            self.vec.first_mut()
        }
        #[inline]
        pub fn last_mut(&mut self) -> Option<&mut T> {
            self.vec.last_mut()
        }
        #[inline]
        pub fn pop(&mut self) -> Option<T> {
            self.vec.pop()
        }
        #[inline]
        pub fn swap(&mut self, i: isize, j: isize) {
            self.vec.swap(i as usize, j as usize);
        }
        #[inline]
        pub fn concat(&self, other: &Self) -> Self
        where
            T: Clone,
        {
            let mut c = self.clone();
            c.vec.append(&mut other.clone().vec);
            c
        }
        #[inline]
        pub fn append(&mut self, other: &Self)
        where
            T: Clone,
        {
            self.vec.append(&mut other.clone().vec);
        }
        #[inline]
        pub fn mrr(&self) -> std::iter::Cloned<Iter<T>>
        where
            T: Clone,
        {
            self.iter().cloned()
        }
        #[inline]
        pub fn join(&self, sep: &str) -> String
        where
            T: std::fmt::Display,
        {
            self.iter()
                .map(|x| format!("{}", x))
                .collect::<Vec<_>>()
                .join(sep)
        }
        #[inline]
        pub fn map<B, F>(&self, f: F) -> List<B>
        where
            T: Clone,
            F: FnMut(T) -> B,
        {
            self.mrr().map(f).collect()
        }
        #[inline]
        pub fn filter<P>(&self, predicate: P) -> List<T>
        where
            T: Clone,
            P: FnMut(&T) -> bool,
        {
            self.mrr().filter(predicate).collect()
        }
        #[inline]
        pub fn filter_map<B, F>(&self, f: F) -> List<B>
        where
            T: Clone,
            F: FnMut(T) -> Option<B>,
        {
            self.mrr().filter_map(f).collect()
        }
        #[doc = " |acc, x| -> acc"]
        #[inline]
        pub fn fold<B, F>(&self, init: B, f: F) -> B
        where
            T: Clone,
            F: FnMut(B, T) -> B,
        {
            self.mrr().fold(init, f)
        }
        #[inline]
        pub fn any<P>(&self, predicate: P) -> bool
        where
            P: FnMut(&T) -> bool,
        {
            self.iter().any(predicate)
        }
        #[inline]
        pub fn all<P>(&self, predicate: P) -> bool
        where
            P: FnMut(&T) -> bool,
        {
            self.iter().all(predicate)
        }
        #[inline]
        pub fn count<P>(&self, predicate: P) -> isize
        where
            P: FnMut(&&T) -> bool,
        {
            self.iter().filter(predicate).count() as isize
        }
        #[inline]
        pub fn sum(&self) -> T
        where
            T: Int,
        {
            self.iter().cloned().fold(T::zero(), |acc, x| acc + x)
        }
        #[inline]
        pub fn enumerate(&self) -> List<(isize, T)>
        where
            T: Clone,
        {
            self.mrr()
                .enumerate()
                .map(|p| (p.0 as isize, p.1))
                .collect()
        }
        #[inline]
        pub fn find<P>(&self, mut predicate: P) -> Option<&T>
        where
            P: FnMut(&T) -> bool,
        {
            self.iter().find(|x| predicate(*x))
        }
        #[inline]
        pub fn index_of<P>(&self, mut predicate: P) -> Option<isize>
        where
            P: FnMut(&T) -> bool,
        {
            self.iter()
                .enumerate()
                .find(|&(_i, x)| predicate(x))
                .map(|p| p.0 as isize)
        }
        #[inline]
        pub fn to<B: FromIterator<T>>(&self) -> B
        where
            T: Clone,
        {
            self.mrr().collect()
        }
        #[inline]
        pub fn min(&self) -> Option<&T>
        where
            T: Ord,
        {
            self.iter().min()
        }
        #[inline]
        pub fn max(&self) -> Option<&T>
        where
            T: Ord,
        {
            self.iter().max()
        }
        #[inline]
        pub fn argmin(&self) -> Option<isize>
        where
            T: Ord,
        {
            let item = self.iter().min()?;
            self.iter()
                .enumerate()
                .find(|p| p.1 == item)
                .map(|p| p.0 as isize)
        }
        #[inline]
        pub fn argmax(&self) -> Option<isize>
        where
            T: Ord,
        {
            let item = self.iter().max()?;
            self.iter()
                .enumerate()
                .find(|p| p.1 == item)
                .map(|p| p.0 as isize)
        }
        #[inline]
        pub fn part<U>(&self, range: U) -> List<T>
        where
            T: Clone,
            U: RangeBounds<isize>,
        {
            List::from_vec(
                self.vec[range.lower_bound(0) as usize..range.upper_bound(self.lens()) as usize]
                    .to_vec(),
            )
        }
        #[inline]
        pub fn first_exn(&self) -> &T {
            self.first().unwrap()
        }
        #[inline]
        pub fn last_exn(&self) -> &T {
            self.last().unwrap()
        }
        #[inline]
        pub fn first_mut_exn(&mut self) -> &mut T {
            self.first_mut().unwrap()
        }
        #[inline]
        pub fn last_mut_exn(&mut self) -> &mut T {
            self.last_mut().unwrap()
        }
        #[inline]
        pub fn pop_exn(&mut self) -> T {
            self.pop().unwrap()
        }
        #[inline]
        pub fn min_exn(&self) -> &T
        where
            T: Ord,
        {
            self.min().unwrap()
        }
        #[inline]
        pub fn max_exn(&self) -> &T
        where
            T: Ord,
        {
            self.max().unwrap()
        }
        #[inline]
        pub fn argmin_exn(&self) -> isize
        where
            T: Ord,
        {
            self.argmin().unwrap()
        }
        #[inline]
        pub fn argmax_exn(&self) -> isize
        where
            T: Ord,
        {
            self.argmax().unwrap()
        }
        #[inline]
        pub fn find_exn<P>(&self, predicate: P) -> &T
        where
            P: FnMut(&T) -> bool,
        {
            self.find(predicate).unwrap()
        }
        #[inline]
        pub fn index_of_exn<P>(&self, predicate: P) -> isize
        where
            P: FnMut(&T) -> bool,
        {
            self.index_of(predicate).unwrap()
        }
    }
    impl<T> Index<isize> for List<T> {
        type Output = T;
        #[inline]
        fn index(&self, index: isize) -> &Self::Output {
            if cfg!(debug_assertions) {
                self.vec.index(index as usize)
            } else {
                unsafe { self.vec.get_unchecked(index as usize) }
            }
        }
    }
    impl<T> IndexMut<isize> for List<T> {
        #[inline]
        fn index_mut(&mut self, index: isize) -> &mut Self::Output {
            if cfg!(debug_assertions) {
                self.vec.index_mut(index as usize)
            } else {
                unsafe { self.vec.get_unchecked_mut(index as usize) }
            }
        }
    }
    impl<T> Index<char> for List<T> {
        type Output = T;
        #[inline]
        fn index(&self, index: char) -> &Self::Output {
            if cfg!(debug_assertions) {
                self.vec.index(index as usize - 'a' as usize)
            } else {
                unsafe { self.vec.get_unchecked(index as usize - 'a' as usize) }
            }
        }
    }
    impl<T> IndexMut<char> for List<T> {
        #[inline]
        fn index_mut(&mut self, index: char) -> &mut Self::Output {
            if cfg!(debug_assertions) {
                self.vec.index_mut(index as usize - 'a' as usize)
            } else {
                unsafe { self.vec.get_unchecked_mut(index as usize - 'a' as usize) }
            }
        }
    }
    impl<T> FromIterator<T> for List<T> {
        fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
            List {
                vec: iter.into_iter().collect(),
            }
        }
    }
    impl<T> IntoIterator for List<T> {
        type Item = T;
        type IntoIter = std::vec::IntoIter<T>;
        fn into_iter(self) -> std::vec::IntoIter<T> {
            self.vec.into_iter()
        }
    }
    impl<'a, T> IntoIterator for &'a List<T> {
        type Item = &'a T;
        type IntoIter = Iter<'a, T>;
        fn into_iter(self) -> Iter<'a, T> {
            self.vec.iter()
        }
    }
    impl<T: std::fmt::Display> std::fmt::Display for List<T> {
        fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
            write!(
                f,
                "{}",
                self.iter()
                    .map(|x| format!("{}", x))
                    .collect::<Vec<_>>()
                    .join(" ")
            )
        }
    }
    impl<T: std::fmt::Debug> std::fmt::Debug for List<T> {
        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
            write!(
                f,
                "[{}]",
                self.iter()
                    .map(|x| format!("{:?}", x))
                    .collect::<Vec<_>>()
                    .join(", ")
            )
        }
    }
    impl<T> From<Vec<T>> for List<T> {
        fn from(vec: Vec<T>) -> Self {
            Self::from_vec(vec)
        }
    }
    impl<T: Clone> From<&[T]> for List<T> {
        fn from(slice: &[T]) -> Self {
            slice.iter().cloned().collect()
        }
    }
    impl<T> Deref for List<T> {
        type Target = [T];
        fn deref(&self) -> &[T] {
            &self.vec
        }
    }
    impl<T> DerefMut for List<T> {
        fn deref_mut(&mut self) -> &mut [T] {
            &mut self.vec
        }
    }
    #[macro_export]
    macro_rules ! list { () => { $ crate :: arraylist :: List :: new () } ; ($ ($ v : expr) ,+ $ (,) ?) => { $ crate :: arraylist :: List :: from_vec ([$ ($ v) ,+] . to_vec ()) } ; ($ v : expr ; $ a : expr) => { $ crate :: arraylist :: List :: init ($ v , $ a) } ; ($ v : expr ; $ a : expr ; $ ($ rest : expr) ;+) => { $ crate :: arraylist :: List :: init (list ! ($ v ; $ ($ rest) ;+) , $ a) } ; }
}