use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::io::BufRead;
fn print_iter<I: Iterator>(iter: I)
where
<I as Iterator>::Item: std::fmt::Display,
{
let mut iter = iter;
if let Some(v) = iter.next() {
print!("{}", v);
for v in iter {
print!(" {}", v);
}
}
println!();
}
struct Counter {
counts: BTreeMap<usize, usize>,
}
impl Counter {
pub fn new() -> Self {
Self {
counts: BTreeMap::new(),
}
}
pub fn is_empty(&self) -> bool {
self.counts.is_empty()
}
pub fn first(&self) -> usize {
*self.counts.iter().next().unwrap().0
}
pub fn add(&mut self, val: usize) {
*self.counts.entry(val).or_insert(0) += 1;
}
pub fn remove(&mut self, val: usize) -> bool {
let count = self.counts.get_mut(&val);
if let Some(count) = count {
assert!(*count > 0);
*count -= 1;
if *count == 0 {
self.counts.remove(&val);
}
true
} else {
false
}
}
}
fn solve_with_three_smallest(
v: &[usize],
n: usize,
(a0, a1, a2): (usize, usize, usize),
) -> Option<Vec<usize>> {
// println!("{}, {}, {}", a0, a1, a2);
// What to do with tree smallest elements?
let mut res = Vec::new();
let mut left = Counter::new();
for v in v {
left.add(*v);
}
left.remove(a0 + a1);
left.remove(a0 + a2);
left.remove(a1 + a2);
res.push(a0);
res.push(a1);
res.push(a2);
// The next smallest element has to be a0+??
while !left.is_empty() {
let ai = left.first() - a0;
for a in &res {
if !left.remove(a + ai) {
return None;
}
}
res.push(ai);
}
Some(res)
}
fn solve(v: Vec<usize>, n: usize) -> Vec<usize> {
assert_eq!(v.len(), n * (n - 1) / 2);
let mut v = v;
v.sort();
// Guess the three smallest elements
for i in 2..=(n + 3).min(v.len() - 1) {
let v0 = v[0];
let v1 = v[1];
let vi = v[i];
let a0 = (v0 + v1 - vi) / 2;
let a1 = (v0 + vi - v1) / 2;
let a2 = (v1 + vi - v0) / 2;
if a0 + a1 == v0 && a0 + a2 == v1 && a1 + a2 == vi {
if let Some(res) = solve_with_three_smallest(&v, n, (a0, a1, a2)) {
return res;
}
}
}
unreachable!()
// let v0 = v[0];
// let v1 = v[1];
// let v2 = v[2];
// let a0 = (v0 + v1 - v2) / 2;
// let a1 = (v0 + v2 - v1) / 2;
// let a2 = (v1 + v2 - v0) / 2;
// if a0 + a1 == v0 && a0 + a2 == v1 && a1 + a2 == v2 {
// solve_with_three_smallest(v, n, (a0, a1, a2)).unwrap()
// } else {
// todo!()
// }
// // Guess the three smallest elements
// let v0 = v[0];
// let v1 = v[1];
// let v2 = v[2];
// let a0 = (v0 + v1 - v2) / 2;
// let a1 = (v0 + v2 - v1) / 2;
// let a2 = (v1 + v2 - v0) / 2;
// if a0 + a1 == v0 && a0 + a2 == v1 && a1 + a2 == v2 {
// solve_with_three_smallest(v, n, (a0, a1, a2)).unwrap()
// } else {
// todo!()
// }
}
fn main() {
let stdin = std::io::stdin();
let stdin = stdin.lock();
let mut lines = stdin.lines();
let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
let v = lines
.next()
.unwrap()
.unwrap()
.split_whitespace()
.map(|v| v.parse().unwrap())
.collect();
print_iter(solve(v, n).into_iter());
}
#[cfg(test)]
mod tests {
use super::*;
fn construct_input(v: &[usize]) -> Vec<usize> {
let mut res = Vec::new();
for i in 0..v.len() {
for j in i + 1..v.len() {
res.push(v[i] + v[j]);
}
}
res
}
fn assert_similar(real: Vec<usize>, test: Vec<usize>) {
let mut real = construct_input(&real);
let mut test = construct_input(&test);
real.sort();
test.sort();
assert_eq!(real, test);
}
fn assert_test(res: Vec<usize>) {
let input = construct_input(&res);
let n = res.len();
assert_similar(res, solve(input, n));
}
#[test]
fn test_sample() {
assert_test(vec![1, 3, 3, 3]);
}
#[test]
fn test_many() {
assert_test(vec![1, 2, 3, 4]);
assert_test(vec![1, 2, 3, 4, 5]);
assert_test(vec![1, 10, 11, 12]);
assert_test(vec![1, 11, 12, 13]);
assert_test(vec![1, 10, 20, 30]);
}
#[test]
fn test_medium() {
assert_test(vec![1, 2, 3, 4,1, 2, 3, 4, 5,100,5,19,312,523,456,34,56,12,4,2]);
}
#[test]
fn test_big() {
use rand::distributions::{Distribution, Uniform};
use std::time::{Duration, Instant};
const ITERS: u32 = 30;
const SIZE: usize = 100;
let mut time = Duration::from_nanos(1);
for i in 0..ITERS {
let mut model: Vec<usize> = vec![0; SIZE];
for i in 0..SIZE {
model[i] = Uniform::from(0..1_000_000).sample(&mut rand::thread_rng());
}
let input = construct_input(&model);
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
let start = Instant::now();
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
let output = solve(input, model.len());
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
let stop = Instant::now();
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
time += stop - start;
assert_similar(model, output);
}
let time = (time / ITERS).as_secs_f64();
assert!(time < 1.0, "Took time {}", time);
}
}