// ---------- begin karatsuba multiplication ---------- fn karatsuba(a: &[T], b: &[T], c: &mut [T], zero: T, buf: &mut [T]) where T: std::marker::Copy + std::ops::Add + std::ops::Sub + std::ops::Mul + { assert!(a.len() == b.len()); let n = a.len(); if n <= 16 { for (i, a) in a.iter().enumerate() { for (c, b) in c[i..].iter_mut().zip(b.iter()) { *c = *c + *a * *b; } } return; } if n & 1 == 1 { karatsuba(&a[1..], &b[1..], &mut c[2..], zero, buf); let x = a[0]; let y = b[0]; c[0] = c[0] + x * y; for (c, (a, b)) in c[1..].iter_mut().zip(a[1..].iter().zip(b[1..].iter())) { *c = *c + x * *b + *a * y; } return; } let m = n / 2; let (fa, ta) = a.split_at(m); let (fb, tb) = b.split_at(m); karatsuba(fa, fb, &mut c[..n], zero, buf); karatsuba(ta, tb, &mut c[n..], zero, buf); let (x, buf) = buf.split_at_mut(m); let (y, buf) = buf.split_at_mut(m); let (z, buf) = buf.split_at_mut(n); for z in z.iter_mut() { *z = zero; } for (x, (p, q)) in x.iter_mut().zip(fa.iter().zip(ta.iter())) { *x = *p + *q; } for (y, (p, q)) in y.iter_mut().zip(fb.iter().zip(tb.iter())) { *y = *p + *q; } karatsuba(x, y, z, zero, buf); for (z, (p, q)) in z.iter_mut().zip(c[..n].iter().zip(c[n..].iter())) { *z = *z - (*p + *q); } for (c, z) in c[m..].iter_mut().zip(z.iter()) { *c = *c + *z; } } fn multiply(a: &[T], b: &[T], zero: T) -> Vec where T: std::marker::Copy + std::ops::Add + std::ops::Sub + std::ops::Mul + { let mut i = 0; let mut j = 0; let mut ans = vec![zero; a.len() + b.len()]; let mut buf = vec![zero; 4 * std::cmp::min(a.len(), b.len())]; let mut c = Vec::with_capacity(a.len() + b.len()); while i < a.len() && j < b.len() { let x = a.len() - i; let y = b.len() - j; let z = std::cmp::min(x, y); c.clear(); c.resize(2 * z, zero); karatsuba(&a[i..(i + z)], &b[j..(j + z)], &mut c, zero, &mut buf); for (ans, c) in ans[(i + j)..].iter_mut().zip(c.iter()) { *ans = *ans + *c; } if x <= y { j += x; } else { i += y; } } ans.truncate(a.len() + b.len() - 1); ans } // ---------- end karatsuba multiplication ---------- // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- fn run() { input! { n: usize, q: usize, a: [u32; n], r: [usize; q], } let mut c = vec![0; n]; for r in r { c[r] += 1; } c.reverse(); let b = a.iter().cloned().cycle().take(2 * n).collect::>(); let c = multiply(&c, &b, 0); let mut s = String::new(); for i in 0..n { s.push_str(&format!("{} ", c[n - 1 + i])); } s.pop(); println!("{}", s); } fn main() { run(); }