use avl_tree::AvlTree; use input::input_array; use input::input_vec; fn main() { let [q, k] = input_array::(); let mut tree = AvlTree::::new(); for _ in 0..q { let query = input_vec::(); match query[0] { 1 => { let x = query[1]; let i = tree.lower_bound(&x); tree.insert(i, x); } 2 => { let ans = tree.get(k - 1).copied().unwrap_or(!0) as isize; tree.remove(k - 1); println!("{}", ans); } _ => unreachable!(), } } } // input {{{ #[allow(dead_code)] mod input { use std::cell::Cell; use std::convert::TryFrom; use std::io::stdin; use std::io::BufRead; use std::io::BufReader; use std::io::Lines; use std::io::Stdin; use std::str::FromStr; use std::sync::Mutex; use std::sync::Once; type Server = Mutex>>; static ONCE: Once = Once::new(); pub struct Lazy(Cell>); unsafe impl Sync for Lazy {} fn line() -> String { static SYNCER: Lazy = Lazy(Cell::new(None)); ONCE.call_once(|| { SYNCER .0 .set(Some(Mutex::new(BufReader::new(stdin()).lines()))); }); unsafe { (*SYNCER.0.as_ptr()) .as_ref() .unwrap() .lock() .unwrap() .next() .unwrap() .unwrap() } } pub trait ForceFromStr: FromStr { fn force_from_str(s: &str) -> Self; } impl ForceFromStr for T where T: FromStr, E: std::fmt::Debug, { fn force_from_str(s: &str) -> Self { s.parse().unwrap() } } pub fn input_array() -> [T; N] where T: std::fmt::Debug, { <[_; N]>::try_from(input_vec()).unwrap() } pub fn input_vec() -> Vec { line() .split_whitespace() .map(T::force_from_str) .collect::>() } pub fn input() -> T { T::force_from_str(&line()) } } // }}} // lg {{{ #[allow(dead_code)] mod lg { use std::borrow::Borrow; use std::fmt::Debug; use std::marker::PhantomData; #[macro_export] macro_rules! lg { (@contents $head:expr $(, $tail:expr)*) => {{ $crate::__lg_variable!($head); $( eprint!(","); $crate::__lg_variable!($tail); )* eprintln!(); }}; ($($expr:expr),* $(,)?) => {{ eprint!("{}❯", line!()); $crate::lg!(@contents $($expr),*) }}; } #[doc(hidden)] #[macro_export] macro_rules! __lg_variable { ($value:expr) => {{ match $value { head => { eprint!( " {} = {}", stringify!($value), $crate::lg::__quiet(format!("{:?}", &head)) ); } } }}; } #[doc(hidden)] pub fn __quiet(s: impl AsRef) -> String { s.as_ref() .replace("18446744073709551615", "*") // u64 .replace("9223372036854775807", "*") // i64 .replace("-9223372036854775808", "*") // i64 .replace("4294967295", "*") // u32 .replace("2147483647", "*") // i32 .replace("-2147483648", "*") // i32 .replace("None", "*") .replace("Some", "") } #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)] pub struct Table { __marker: PhantomData<(T, Row)>, storage: Storage, index_width: usize, column_width: usize, heading_newlines: usize, } pub fn table, Storage: AsRef<[Row]>>( storage: Storage, ) -> Table { Table::new(storage) } impl Table where T: Clone + Debug, Row: AsRef<[T]>, Storage: AsRef<[Row]>, { pub fn new(storage: Storage) -> Self { Self { __marker: PhantomData, storage, column_width: 3, index_width: 2, heading_newlines: 1, } } pub fn index_width(&mut self, index_width: usize) -> &mut Self { self.index_width = index_width; self } pub fn column_width(&mut self, column_width: usize) -> &mut Self { self.column_width = column_width; self } pub fn heading_newlines(&mut self, heading_newlines: usize) -> &mut Self { self.heading_newlines = heading_newlines; self } } impl Debug for Table where T: Clone + Debug, Row: AsRef<[T]>, Storage: AsRef<[Row]>, { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let Self { __marker: _, ref storage, index_width, column_width, heading_newlines, } = *self; for _ in 0..heading_newlines { writeln!(f)?; } let ncols = storage.as_ref()[0].as_ref().len(); write!(f, "\x1b[48;2;127;127;127;37m")?; write!(f, "{}|", " ".repeat(index_width))?; for j in 0..ncols { write!(f, "{j:column_width$}")?; } writeln!(f, "\x1b[0m")?; for (i, row) in storage.as_ref().iter().enumerate() { write!(f, "{:index_width$}|", i, index_width = index_width)?; for value in row.as_ref() { write!(f, "{:>column_width$}", __quiet(format!("{:?}", value)),)?; } writeln!(f)?; } Ok(()) } } pub fn bools(iter: I) -> String where B: Borrow, I: IntoIterator, { format!( "[{}]", iter.into_iter() .map(|b| ['.', '#'][usize::from(*(b.borrow()))]) .collect::(), ) } } // }}} // avl_tree {{{ #[allow(dead_code)] mod avl_tree { #![allow(clippy::unnecessary_box_returns)] use std::borrow::Borrow; use std::cmp::Ordering; use std::fmt::Debug; use std::hash::Hash; use std::iter::successors; use std::iter::FromIterator; use std::mem::swap; use std::ops::Index; #[derive(Clone)] pub struct AvlTree { root: Option>>, } impl AvlTree { pub fn new() -> Self { Self::default() } pub fn is_empty(&self) -> bool { self.root.is_none() } pub fn len(&self) -> usize { len(self.root.as_deref()) } pub fn push_back(&mut self, value: T) { self.append(&mut Self { root: Some(new(value)), }) } pub fn push_front(&mut self, value: T) { let mut swp = Self { root: Some(new(value)), }; swp.append(self); *self = swp; } pub fn pop_back(&mut self) -> Option { let root = self.root.take()?; let last_index = root.len - 1; let (left, center, _right) = split_delete(root, last_index); self.root = left; Some(center.value) } pub fn pop_front(&mut self) -> Option { let (_left, center, right) = split_delete(self.root.take()?, 0); self.root = right; Some(center.value) } pub fn back(&self) -> Option<&T> { self.get(self.len().checked_sub(1)?) } pub fn front(&self) -> Option<&T> { self.get(0) } pub fn back_mut(&mut self) -> Option<&mut T> { self.get_mut(self.len().checked_sub(1)?) } pub fn front_mut(&mut self) -> Option<&mut T> { self.get_mut(0) } pub fn append(&mut self, other: &mut Self) { self.root = merge(self.root.take(), other.root.take()); } pub fn split_off(&mut self, index: usize) -> Self { assert!(index <= self.len()); let (left, right) = split(self.root.take(), index); self.root = left; Self { root: right } } pub fn insert(&mut self, index: usize, value: T) { assert!(index <= self.len()); let other = self.split_off(index); self.root = Some(merge_with_root(self.root.take(), new(value), other.root)); } pub fn remove(&mut self, index: usize) -> Option { if index < self.len() { let (left, center, right) = split_delete(self.root.take().unwrap(), index); self.root = merge(left, right); Some(center.value) } else { None } } pub fn get(&self, index: usize) -> Option<&T> { if index < self.len() { Some(&get(self.root.as_ref().unwrap(), index).value) } else { None } } pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { if index < self.len() { Some(&mut get_mut(self.root.as_mut().unwrap(), index).value) } else { None } } pub fn binary_search_by(&self, f: impl FnMut(&T) -> Ordering) -> Result { binary_search_by(self.root.as_deref(), f) } pub fn binary_search_by_key( &self, b: &B, mut f: impl FnMut(&T) -> B, ) -> Result { self.binary_search_by(|x| f(x).cmp(b)) } pub fn binary_search(&self, value: &Q) -> Result where T: Borrow, { self.binary_search_by(|x| x.borrow().cmp(value)) } pub fn partition_point(&self, mut is_right: impl FnMut(&T) -> bool) -> usize { partition_point(self.root.as_deref(), |node| is_right(&node.value)) } pub fn lower_bound(&self, value: &Q) -> usize where T: Borrow, { partition_point(self.root.as_deref(), |node| value <= node.value.borrow()) } pub fn upper_bound(&self, value: &Q) -> usize where T: Borrow, { partition_point(self.root.as_deref(), |node| value < node.value.borrow()) } pub fn iter(&self) -> Iter<'_, T> { Iter { stack: successors(self.root.as_deref(), |current| current.left.as_deref()) .collect(), rstack: successors(self.root.as_deref(), |current| current.right.as_deref()) .collect(), } } } impl Default for AvlTree { fn default() -> Self { Self { root: None } } } impl PartialEq for AvlTree { fn eq(&self, other: &Self) -> bool { self.iter().eq(other) } } impl PartialEq<[A]> for AvlTree where T: PartialEq, { fn eq(&self, other: &[A]) -> bool { self.iter().eq(other) } } impl Eq for AvlTree {} impl PartialOrd for AvlTree { fn partial_cmp(&self, other: &Self) -> Option { self.iter().partial_cmp(other) } } impl Ord for AvlTree { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other) } } impl Debug for AvlTree { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_list().entries(self).finish() } } impl Hash for AvlTree { fn hash(&self, state: &mut H) { self.iter().for_each(|elm| elm.hash(state)); } } impl IntoIterator for AvlTree { type IntoIter = IntoIter; type Item = T; fn into_iter(self) -> Self::IntoIter { let mut stack = Vec::new(); if let Some(mut current) = self.root { while let Some(next) = current.left.take() { stack.push(current); current = next; } stack.push(current); } IntoIter { stack } } } impl<'a, T> IntoIterator for &'a AvlTree { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl Index for AvlTree { type Output = T; fn index(&self, index: usize) -> &Self::Output { self.get(index).unwrap() } } impl FromIterator for AvlTree { fn from_iter>(iter: I) -> Self { fn from_slice_of_nodes(nodes: &mut [Option>>]) -> Option>> { if nodes.is_empty() { None } else { let i = nodes.len() / 2; Some(merge_with_root( from_slice_of_nodes(&mut nodes[..i]), nodes[i].take().unwrap(), from_slice_of_nodes(&mut nodes[i + 1..]), )) } } Self { root: from_slice_of_nodes( iter.into_iter() .map(new) .map(Some) .collect::>() .as_mut_slice(), ), } } } pub struct Iter<'a, T> { stack: Vec<&'a Node>, rstack: Vec<&'a Node>, } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option { let current = self.stack.pop()?; self.stack .extend(successors(current.right.as_deref(), |node| { node.left.as_deref() })); if std::ptr::eq(current, *self.rstack.last().unwrap()) { self.stack.clear(); self.rstack.clear(); } Some(¤t.value) } } impl<'a, T> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option { let current = self.rstack.pop()?; self.rstack .extend(successors(current.left.as_deref(), |node| { node.right.as_deref() })); if std::ptr::eq(current, *self.stack.last().unwrap()) { self.stack.clear(); self.rstack.clear(); } Some(¤t.value) } } pub struct IntoIter { stack: Vec>>, } impl Iterator for IntoIter { type Item = T; fn next(&mut self) -> Option { let mut current = self.stack.pop()?; if let Some(mut current) = current.right.take() { while let Some(next) = current.left.take() { self.stack.push(current); current = next; } self.stack.push(current); } Some(current.value) } } #[derive(Clone)] struct Node { left: Option>, right: Option>, value: T, len: usize, ht: u8, } fn new(value: T) -> Box> { Box::new(Node { left: None, right: None, value, len: 1, ht: 1, }) } impl Node { fn update(&mut self) { self.len = len(self.left.as_deref()) + 1 + len(self.right.as_deref()); self.ht = 1 + ht(self.left.as_deref()).max(ht(self.right.as_deref())); } } fn len(tree: Option<&Node>) -> usize { tree.as_ref().map_or(0, |node| node.len) } fn ht(tree: Option<&Node>) -> u8 { tree.as_ref().map_or(0, |node| node.ht) } fn balance(node: &mut Box>) { fn rotate_left(node: &mut Box>) { let mut x = node.left.take().unwrap(); let y = x.right.take(); swap(node, &mut x); x.left = y; x.update(); node.right = Some(x); node.update(); } fn rotate_right(node: &mut Box>) { let mut x = node.right.take().unwrap(); let y = x.left.take(); swap(node, &mut x); x.right = y; x.update(); node.left = Some(x); node.update(); } if ht(node.left.as_deref()) > 1 + ht(node.right.as_deref()) { let left = node.left.as_mut().unwrap(); if ht(left.left.as_deref()) < ht(left.right.as_deref()) { rotate_right(left); } rotate_left(node); } else if ht(node.left.as_deref()) + 1 < ht(node.right.as_deref()) { let right = node.right.as_mut().unwrap(); if ht(right.left.as_deref()) > ht(right.right.as_deref()) { rotate_left(right); } rotate_right(node); } else { node.update(); } } fn merge_with_root( mut left: Option>>, mut center: Box>, mut right: Option>>, ) -> Box> { match ht(left.as_deref()).cmp(&ht(right.as_deref())) { Ordering::Less => { let mut root = right.take().unwrap(); root.left = Some(merge_with_root(left, center, root.left.take())); balance(&mut root); root } Ordering::Equal => { center.left = left; center.right = right; center.update(); center } Ordering::Greater => { let mut root = left.take().unwrap(); root.right = Some(merge_with_root(root.right.take(), center, right)); balance(&mut root); root } } } fn merge( left: Option>>, mut right: Option>>, ) -> Option>> { match right.take() { None => left, Some(right) => { let (_none, center, rhs) = split_delete(right, 0); Some(merge_with_root(left, center, rhs)) } } } #[allow(clippy::type_complexity)] fn split_delete( mut root: Box>, index: usize, ) -> (Option>>, Box>, Option>>) { debug_assert!((0..root.len).contains(&index)); let left = root.left.take(); let right = root.right.take(); let lsize = len(left.as_deref()); match lsize.cmp(&index) { Ordering::Less => { let mut res = split_delete(right.unwrap(), index - lsize - 1); res.0 = Some(merge_with_root(left, root, res.0)); res } Ordering::Equal => (left, root, right), Ordering::Greater => { let mut res = split_delete(left.unwrap(), index); res.2 = Some(merge_with_root(res.2, root, right)); res } } } #[allow(clippy::type_complexity)] fn split( tree: Option>>, index: usize, ) -> (Option>>, Option>>) { match tree { Some(root) => { if root.len == index { (Some(root), None) } else { let (left, center, right) = split_delete(root, index); (left, Some(merge_with_root(None, center, right))) } } None => (None, None), } } fn binary_search_by( tree: Option<&Node>, mut f: impl FnMut(&T) -> Ordering, ) -> Result { let node = match tree { None => return Err(0), Some(node) => node, }; let lsize = len(node.left.as_deref()); match f(&node.value) { Ordering::Less => binary_search_by(node.right.as_deref(), f) .map(|index| lsize + 1 + index) .map_err(|index| lsize + 1 + index), Ordering::Equal => Ok(lsize), Ordering::Greater => binary_search_by(node.left.as_deref(), f), } } fn partition_point( tree: Option<&Node>, mut is_right: impl FnMut(&Node) -> bool, ) -> usize { let node = match tree { None => return 0, Some(node) => node, }; let lsize = len(node.left.as_deref()); if is_right(node) { partition_point(node.left.as_deref(), is_right) } else { lsize + 1 + partition_point(node.right.as_deref(), is_right) } } fn get(node: &Node, index: usize) -> &Node { let lsize = len(node.left.as_deref()); match lsize.cmp(&index) { Ordering::Less => get(node.right.as_ref().unwrap(), index - lsize - 1), Ordering::Equal => node, Ordering::Greater => get(node.left.as_ref().unwrap(), index), } } fn get_mut(node: &mut Node, index: usize) -> &mut Node { let lsize = len(node.left.as_deref()); match lsize.cmp(&index) { Ordering::Less => get_mut(node.right.as_mut().unwrap(), index - lsize - 1), Ordering::Equal => node, Ordering::Greater => get_mut(node.left.as_mut().unwrap(), index), } } } // }}}