macro_rules! semigroup_impl { ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr) => { impl $crate::math::algebra::Semigroup for $marker { type T = $t; fn append($lhs: &$t, $rhs: &$t) -> $t { $append } } }; } macro_rules! monoid_impl { ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, $identity:expr) => { semigroup_impl! { $marker, $t, |$lhs, $rhs| $append } impl $crate::math::algebra::Monoid for $marker { fn identity() -> $t { $identity } } }; } macro_rules! group_impl { ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, | $x:ident | $invert:expr, $identity:expr) => { monoid_impl! { $marker, $t, |$lhs, $rhs| $append, $identity } impl $crate::math::algebra::Group for $marker { fn invert($x: &$t) -> $t { $invert } } }; } macro_rules! commutative_monoid_impl { ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, $identity:expr) => { monoid_impl! { $marker, $t, |$lhs, $rhs| $append, $identity } impl $crate::math::algebra::CommutativeMonoid for $marker {} }; } macro_rules! commutative_group_impl { ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, | $x:ident | $invert:expr, $identity:expr) => { group_impl! { $marker, $t, |$lhs, $rhs| $append, |$x| $invert, $identity } impl $crate::math::algebra::CommutativeMonoid for $marker {} impl $crate::math::algebra::CommutativeGroup for $marker {} }; } fn solve(_reader: R, _writer: &mut W) { let mut _scanner = Scanner::new(_reader); #[allow(unused_macros)] macro_rules! scan { ($t:ty) => { _scanner.next::<$t>().unwrap() }; ($($t:ty),+) => { ($(scan!($t)),+) }; ($t:ty; $n:expr) => { scan_iter!($t; $n).collect::>() }; ($t_0:ty, $t_1:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1; $n) }; ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => { scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n) }; ($($t:ty = $i:tt),+; $n:expr) => {{ let mut vecs = ($(Vec::<$t>::with_capacity($n)),+); for _ in 0..$n {$( vecs.$i.push(scan!($t)); )+} vecs }}; } #[allow(unused_macros)] macro_rules! scan_iter { ($t:ty; $n:expr) => { _scanner.take::<$t>($n).map(|x| x.unwrap()) }; } #[allow(unused_macros)] macro_rules! print { ($fmt:expr) => { write!(_writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { write!(_writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! println { () => { writeln!(_writer).unwrap() }; ($fmt:expr) => { writeln!(_writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { writeln!(_writer, $fmt, $($arg)*).unwrap() }; } use data_structures::{CoordinateCompressor, FenwickTree}; use math::algebra::AdditiveGroup; use std::iter::FromIterator; let n = scan!(usize); let (a, b) = scan!(i64, i64; n); let m = scan!(usize); let (x, y) = scan!(i64, i64; m); let compressor = CoordinateCompressor::from_iter(b.iter().chain(y.iter()).cloned()); let mut fenwick_tree = FenwickTree::>::new(compressor.len()); enum Type { People, Mentaiko, } let mut stream = Vec::with_capacity(n + m); for (i, (a, b)) in a.into_iter().zip(b).enumerate() { stream.push((i, Type::People, a, b)); } for (i, (x, y)) in x.into_iter().zip(y).enumerate() { stream.push((i, Type::Mentaiko, x, y)); } stream.sort_by_key(|&(_, _, p, _)| -p); let mut max = 0; let mut ans = Vec::with_capacity(m); for (i, t, _, q) in stream { let q = compressor.compress(q).unwrap(); match t { Type::People => fenwick_tree.append(q, &1), Type::Mentaiko => { let crt = fenwick_tree.prefix_concat(..q + 1); if crt > max { ans.clear(); max = crt; ans.push(i + 1); } else if crt == max { ans.push(i + 1); } } } } if max == 0 { println!("0"); return; } ans.sort(); for i in ans.into_iter() { println!("{}", i); } } fn main() { let stdin = stdin(); let stdout = stdout(); #[cfg(debug_assertions)] let mut writer = stdout.lock(); #[cfg(not(debug_assertions))] let mut writer = ::std::io::BufWriter::new(stdout.lock()); solve(stdin.lock(), &mut writer); writer.flush().unwrap(); } use io::Scanner; use std::io::{stdin, stdout, BufRead, Write}; pub mod math { pub mod algebra { pub use self::additive_group::*; pub use self::commutative_group::*; pub use self::commutative_monoid::*; pub use self::group::*; pub use self::monoid::*; pub use self::semigroup::*; mod semigroup { use std::fmt::Debug; pub trait Semigroup { type T: Clone + PartialEq + Debug; fn append(lhs: &Self::T, rhs: &Self::T) -> Self::T; fn append_assign(lhs: &mut Self::T, rhs: &Self::T) { *lhs = Self::append(lhs, rhs); } } } mod monoid { use math::algebra::Semigroup; pub trait Monoid: Semigroup { fn identity() -> Self::T; } } mod group { use math::algebra::Monoid; pub trait Group: Monoid { fn invert(&Self::T) -> Self::T; fn append_inverse(lhs: &Self::T, rhs: &Self::T) -> Self::T { Self::append(lhs, &Self::invert(rhs)) } fn append_inverse_assign(lhs: &mut Self::T, rhs: &Self::T) { *lhs = Self::append_inverse(lhs, rhs); } } } mod commutative_monoid { use math::algebra::Monoid; pub trait CommutativeMonoid: Monoid {} } mod commutative_group { use math::algebra::{CommutativeMonoid, Group}; pub trait CommutativeGroup: Group + CommutativeMonoid {} } mod additive_group { use std::marker::PhantomData; pub struct AdditiveGroup { _marker: PhantomData T>, } macro_rules! additive_group_impl { ($($t:ty)+) => {$( commutative_group_impl! { AdditiveGroup<$t>, $t, |lhs, rhs| lhs + rhs, |x| -x, 0 } )+}; } additive_group_impl! { i32 i64 isize } } } } pub mod data_structures { pub use self::coordinate_compressor::*; pub use self::fenwick_tree::*; mod coordinate_compressor { use std::collections::HashMap; use std::hash::Hash; use std::iter::FromIterator; pub struct CoordinateCompressor { map: HashMap, vec: Vec, } impl CoordinateCompressor { pub fn len(&self) -> usize { debug_assert_eq!(self.map.len(), self.vec.len()); self.map.len() } pub fn compress(&self, x: T) -> Option { self.map.get(&x).cloned() } pub fn decompress(&self, index: usize) -> Option<&T> { self.vec.get(index) } } impl FromIterator for CoordinateCompressor { fn from_iter>(iter: I) -> Self { let mut vec = iter.into_iter().collect::>(); vec.sort(); vec.dedup(); vec.shrink_to_fit(); let mut map = HashMap::with_capacity(vec.len()); for (i, x) in vec.iter_mut().enumerate() { map.insert(x.clone(), i); } CoordinateCompressor { map: map, vec: vec } } } } mod fenwick_tree { use math::algebra::{CommutativeGroup, CommutativeMonoid}; use search::BinarySearch; use std::iter::FromIterator; use std::ops::{Range, RangeTo}; pub struct FenwickTree { vec: Vec, } impl FenwickTree { pub fn new(size: usize) -> Self { FenwickTree { vec: vec![M::identity(); size + 1] } } pub fn len(&self) -> usize { self.vec.len() - 1 } pub fn append(&mut self, index: usize, x: &M::T) { assert!(index < self.len()); let mut i = index as isize + 1; while i <= self.len() as isize { M::append_assign(&mut self.vec[i as usize], x); i += i & -i; } } pub fn prefix_concat(&self, range: RangeTo) -> M::T { assert!(range.end <= self.len()); let mut acc = M::identity(); let mut r = range.end as isize; while r > 0 { M::append_assign(&mut acc, &self.vec[r as usize]); r -= r & -r; } acc } } impl FenwickTree { pub fn get(&self, index: usize) -> G::T { debug_assert!(index < self.len()); self.cocnat(index..index + 1) } pub fn set(&mut self, index: usize, x: &G::T) { debug_assert!(index < self.len()); let diff = G::append_inverse(x, &self.get(index)); self.append(index, &diff); } pub fn cocnat(&self, range: Range) -> G::T { assert!(range.start <= range.end); assert!(range.end <= self.len()); let mut acc = G::identity(); let mut l = range.start as isize; let mut r = range.end as isize; while l < r { G::append_assign(&mut acc, &self.vec[r as usize]); r -= r & -r; } while r < l { G::append_inverse_assign(&mut acc, &self.vec[l as usize]); l -= l & -l; } acc } } impl BinarySearch for FenwickTree { type Output = RangeTo; fn binary_search bool>(&self, mut f: F) -> Option> { let mut i = 0usize; let mut sum = G::identity(); let mut k = if self.len().is_power_of_two() { self.len() } else { self.len().next_power_of_two() / 2 }; while k > 0 { if let Some(current_segment_sum) = self.vec.get(i + k) { if !f(&G::append(current_segment_sum, &sum)) { G::append_assign(&mut sum, current_segment_sum); i += k; } } k /= 2; } if i < self.len() { Some(..i + 1) } else { None } } } impl FromIterator for FenwickTree { fn from_iter>(iter: I) -> Self { let iter = iter.into_iter(); let mut vec = Vec::with_capacity(1 + iter.size_hint().0); vec.push(M::identity()); vec.extend(iter); for i in 1..(vec.len() - 1) as isize { let j = (i + (i & -i)) as usize; if j < vec.len() { vec[j] = M::append(&vec[j], &vec[i as usize]); } } vec.shrink_to_fit(); FenwickTree { vec: vec } } } } } pub mod io { pub use self::scanner::*; mod scanner { use std::io::BufRead; use std::marker::PhantomData; use std::str::{from_utf8, FromStr}; pub struct Scanner { reader: R, buffer: Vec, position: usize, } impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buffer: vec![], position: 0 } } pub fn next(&mut self) -> Option { Parse::parse(self.next_bytes().unwrap_or(&[])) } pub fn take(&mut self, n: usize) -> Take { Take { scanner: self, n: n, _marker: PhantomData } } pub fn next_bytes(&mut self) -> Option<&[u8]> { if self.buffer.is_empty() { self.read_line(); } loop { match self.buffer.get(self.position) { Some(&b' ') => self.position += 1, Some(&b'\n') => self.read_line(), Some(_) => break, None => return None, } } let start = self.position; loop { match self.buffer.get(self.position) { Some(&b' ') | Some(&b'\n') | None => break, Some(_) => self.position += 1, } } Some(&self.buffer[start..self.position]) } fn read_line(&mut self) { self.position = 0; self.buffer.clear(); self.reader.read_until(b'\n', &mut self.buffer).unwrap(); } } pub struct Take<'a, R: 'a, T> { scanner: &'a mut Scanner, n: usize, _marker: PhantomData T>, } impl<'a, R: BufRead, T: Parse> Iterator for Take<'a, R, T> { type Item = Option; fn next(&mut self) -> Option { if self.n > 0 { self.n -= 1; Some(self.scanner.next()) } else { None } } fn size_hint(&self) -> (usize, Option) { (self.n, Some(self.n)) } } impl<'a, R: BufRead, T: Parse> ExactSizeIterator for Take<'a, R, T> {} pub trait Parse: Sized { fn parse(bytes: &[u8]) -> Option; } impl Parse for u8 { fn parse(bytes: &[u8]) -> Option { if bytes.len() == 1 { Some(*unsafe { bytes.get_unchecked(0) }) } else { None } } } macro_rules! parse_impl { ($($t:ident)+) => {$( impl Parse for $t { fn parse(bytes: &[u8]) -> Option { from_utf8(bytes).ok().and_then(|s| $t::from_str(s).ok()) } } )+}; } parse_impl! { i32 i64 isize u32 u64 usize String } } } pub mod search { pub use self::binary_search::*; mod binary_search { use std::ops::Range; pub trait BinarySearch { type Output; fn binary_search bool>(&self, f: F) -> Option; fn lower_bound(&self, x: &T) -> Option where T: Ord, { self.binary_search(|t| t >= x) } fn upper_bound(&self, x: &T) -> Option where T: Ord, { self.binary_search(|t| t > x) } } macro_rules! binary_search_impl { ($ok:expr, $ng:expr, $cond1:expr, $cond2:expr) => {{ let mut ok_end = $ok; let mut ng_start = $ng; while ok_end - ng_start > 1 { let mid = ng_start + (ok_end - ng_start) / 2; if $cond1(mid) { ok_end = mid; } else { ng_start = mid; } } if $cond2(ok_end) { None } else { Some(ok_end as Self::Output) } }}; } impl BinarySearch for [T] { type Output = usize; fn binary_search bool>(&self, mut f: F) -> Option { binary_search_impl!(self.len() as isize, -1isize, |mid| f(&self[mid as usize]), |ok_end| ok_end as usize == self.len()) } } macro_rules! binary_search_impl_range { ($t:ty, $it:ty) => { impl BinarySearch<$t> for Range<$t> { type Output = $t; fn binary_search bool>(&self, mut f: F) -> Option<$t> { assert!(self.start <= self.end); binary_search_impl!(self.end as $it, self.start as $it - 1, |mid| f(&(mid as $t)), |ok_end| ok_end == self.end as $it) } } }; ($($ut:ty, $it:ty);+) => {$( binary_search_impl_range! { $ut, $it } binary_search_impl_range! { $it, $it } )+}; } binary_search_impl_range! { usize, isize; u32, i32; u64, i64 } } }