#![allow(unused_imports)] use input2::*; use std::{ array, collections::*, io::{self, BufWriter, Read, Write}, }; fn run(mut ss: Input, mut out: O) { let t: u32 = 1; for _ in 0..t { case(&mut ss, &mut out); } } fn case(ss: &mut Input, mut out: O) { use int::*; let n: usize = ss.input(); let a0: i32 = ss.input(); let mut g = 0; wln!(out, "0"); for a in ss.seq::(n - 1) { g = g.gcd(a - a0); wln!(out, "{}", g); } } fn main() { let stdin = io::stdin(); let ss = Input::new(stdin.lock()); let stdout = io::stdout(); let out = BufWriter::new(stdout.lock()); run(ss, out); } pub mod int { use std::ops::*; pub trait UInt: Sized + Copy + Eq + Ord + Add + Sub + Mul + Div + Rem { const ZERO: Self; const ONE: Self; fn div_floor(self, other: Self) -> Self; fn div_ceil(self, other: Self) -> Self; fn abs(self) -> Self; fn gcd(self, other: Self) -> Self; fn lcm(self, other: Self) -> Self { self / self.gcd(other) * other } fn isqrt(self) -> Self; fn quotients(self) -> Qutients { Qutients::new(self) } } pub trait Int: UInt + Neg { fn ext_gcd(mut self, mut other: Self) -> (Self, Self, Self) { use std::mem::swap; let mut a = (Self::ONE, Self::ZERO); let mut b = (Self::ZERO, Self::ONE); while other != Self::ZERO { let d = self / other; self = self % other; swap(&mut self, &mut other); a.0 = a.0 - d * b.0; a.1 = a.1 - d * b.1; swap(&mut a, &mut b); } if self >= Self::ZERO { (self, a.0, a.1) } else { (-self, -a.0, -a.1) } } } pub fn crt(r1: T, m1: T, r2: T, m2: T) -> Option<(T, T)> { if m1 > m2 { return crt(r2, m2, r1, m1); } let (g, v1, _) = m1.ext_gcd(m2); if m1 == g { return if r1 == r2 % m1 { Some((r1, m1)) } else { None }; } if (r2 - r1) % g != T::ZERO { return None; } let u2 = m2 / g; let q = (r2 - r1) / g * v1 % u2; let q = if q >= T::ZERO { q } else { u2 + q }; let x = m1 * q + r1; Some((x, m1 * u2)) } macro_rules! common_fns { ($ ty : ty) => { const ZERO: Self = 0; const ONE: Self = 0; fn gcd(self, other: Self) -> Self { let x = self.abs(); let y = other.abs(); if x == 0 { return y; } if y == 0 { return x; } let tzx = x.trailing_zeros(); let tzy = y.trailing_zeros(); let tzg = tzx.min(tzy); let mut x = x >> tzx; let mut y = y >> tzy; while x != y { if x < y { std::mem::swap(&mut x, &mut y); } x -= y; x >>= x.trailing_zeros(); } x << tzg } }; } macro_rules! uint { ($ ty : ty) => { impl UInt for $ty { common_fns!($ty); fn abs(self) -> Self { self } fn div_floor(self, other: Self) -> Self { self / other } fn div_ceil(self, other: Self) -> Self { let q = self / other; let r = self % other; q + (r != 0) as Self } fn isqrt(self) -> Self { let mut res = 0; let mut diff = self; for exp in (0..=(Self::BITS - self.leading_zeros()) / 2).rev() { if let Some(new_diff) = diff.checked_sub((res << (exp + 1)) + (1 << (2 * exp))) { diff = new_diff; res += 1 << exp; } } res } } }; } macro_rules! int { ($ ty : ty , $ uty : ty) => { impl UInt for $ty { common_fns!($ty); fn abs(self) -> Self { self.abs() } fn div_floor(self, other: Self) -> Self { let q = self / other; let r = self % other; q - ((other ^ r < 0) as Self & (r != 0) as Self) } fn div_ceil(self, other: Self) -> Self { let q = self / other; let r = self % other; q + ((other ^ r > 0) as Self & (r != 0) as Self) } fn isqrt(self) -> Self { assert!(self >= 0, "the value is negative ({self})"); (self as $uty).isqrt() as Self } } impl Int for $ty {} }; } uint!(usize); uint!(u8); uint!(u16); uint!(u32); uint!(u64); uint!(u128); int!(isize, usize); int!(i8, u8); int!(i16, u16); int!(i32, u32); int!(i64, u64); int!(i128, u128); pub fn gcd(x: T, y: T) -> T { x.gcd(y) } pub fn ext_gcd(x: T, y: T) -> (T, T, T) { x.ext_gcd(y) } pub fn lcm(x: T, y: T) -> T { x.lcm(y) } #[derive(Debug, Clone)] pub struct Qutients { n: T, ndivh: T, h: T, } impl Qutients { #[inline] fn new(n: T) -> Self { if n < T::ZERO { unimplemented!() } let mut h = UInt::isqrt(n); if n >= h * (h + T::ONE) { h = h + T::ONE; } Qutients { n, h, ndivh: n / h } } #[inline] pub fn get(&self, i: T) -> Option { if i < self.ndivh { Some(i) } else if self.h > i - self.ndivh { let j = i - self.ndivh; Some(self.n / (self.h - j)) } else { None } } #[inline] pub fn count(&self) -> T { self.h + self.ndivh } pub fn iter(&self) -> QutientsIter { QutientsIter { i: T::ZERO, q: self.clone(), } } } pub struct QutientsIter { i: T, q: Qutients, } impl> Iterator for QutientsIter { type Item = T; fn next(&mut self) -> Option { let q = self.q.get(self.i)?; self.i = self.i + T::ONE; Some(q) } fn size_hint(&self) -> (usize, Option) { let len = (self.q.count() - self.i).try_into().unwrap_or(usize::MAX); (len, Some(len)) } } } pub mod input2 { use std::{ convert::TryInto, io::{self, Read}, marker::PhantomData, mem::{self, MaybeUninit}, ptr, slice, }; pub struct Input { buf: Vec, pos: usize, len: usize, src: R, } macro_rules! def_input2 { ($ f : ident , $ ty : ty) => { pub fn $f(&mut self) -> $ty { self.input() } }; } macro_rules! def_input { ($ ty : ident) => { def_input2!($ty, $ty); }; } impl Input { pub fn new(src: R) -> Self { Self::with_capacity(src, 1 << 20) } pub fn with_capacity(src: R, cap: usize) -> Self { Self { src, buf: vec![0; cap], pos: 0, len: 0, } } pub fn input(&mut self) -> T { T::parse(self) } pub fn map>(&mut self, f: F) -> F::Output { f.map(self) } pub fn seq(&mut self, n: usize) -> Seq { Seq { src: self, n, marker: PhantomData, } } pub fn seq_map>(&mut self, n: usize, f: F) -> SeqMap { SeqMap { src: self, n, f, marker: PhantomData, } } pub fn vec(&mut self, n: usize) -> Vec { self.seq(n).collect() } pub fn map_vec>(&mut self, n: usize, f: F) -> Vec { self.seq_map(n, f).collect() } pub fn str(&mut self) -> &str { std::str::from_utf8(self.bytes()).expect("utf8 error") } pub fn bytes(&mut self) -> &[u8] { let range = self.bytes_inner(); unsafe { self.buf.get_unchecked(range) } } pub fn byte_vec(&mut self) -> Vec { let range = self.bytes_inner(); if range.start == 0 && 2 * range.end >= self.buf.len() { let buf_len = self.buf.len(); let mut new_buf = vec![0; buf_len]; new_buf[..self.len].copy_from_slice(self.remaining()); let mut res = mem::replace(&mut self.buf, new_buf); self.pos = 0; res.truncate(range.end); res } else { self.buf[range].to_vec() } } #[inline] fn bytes_inner(&mut self) -> std::ops::Range { let mut i = 0; loop { if self.len > 0 { if let Some(d) = find_ws(unsafe { self.buf.get_unchecked(self.pos + i..self.pos + self.len) }) { let del = i + d; let range = self.pos..self.pos + del; self.pos += del + 1; self.len -= del + 1; if del == 0 { continue; } return range; } i = self.len; } if self.read() == 0 { let range = self.pos..self.pos + self.len; self.pos = 0; self.len = 0; return range; } } } #[cold] fn read(&mut self) -> usize { if self.pos != 0 { self.buf.copy_within(self.pos..self.pos + self.len, 0); self.pos = 0; } if self.len == self.buf.len() { self.buf.resize((2 * self.buf.len()).max(1 << 13), 0); } loop { match self .src .read(unsafe { self.buf.get_unchecked_mut(self.len..) }) { Ok(n) => { self.len += n; return n; } Err(e) if e.kind() == io::ErrorKind::WouldBlock => {} Err(e) => panic!("io error: {}", e), } } } #[inline] fn remaining(&self) -> &[u8] { unsafe { self.buf.get_unchecked(self.pos..self.pos + self.len) } } def_input!(usize); def_input!(u8); def_input!(u16); def_input!(u32); def_input!(u64); def_input!(isize); def_input!(i8); def_input!(i16); def_input!(i32); def_input!(i64); def_input!(f32); def_input!(f64); def_input!(char); def_input2!(string, String); } pub trait Map { type Output; fn map(&mut self, src: &mut Input) -> Self::Output; } pub trait MapOnce { type Output; fn map(self, src: &mut Input) -> Self::Output; } macro_rules ! map { ($ ($ T : ident) ,*) => { impl <$ ($ T : Parse ,) * O , F : FnMut ($ ($ T) ,+) -> O > Map < fn ($ ($ T) ,+) > for F { type Output = O ; fn map < R : Read > (& mut self , src : & mut Input < R >) -> O { self ($ (src . input ::<$ T > ()) ,*) } } impl <$ ($ T : Parse ,) * O , F : FnOnce ($ ($ T) ,+) -> O > MapOnce < fn ($ ($ T) ,+) > for F { type Output = O ; fn map < R : Read > (self , src : & mut Input < R >) -> O { self ($ (src . input ::<$ T > ()) ,*) } } } ; } map!(A); map!(A, B); map!(A, B, C); map!(A, B, C, D); map!(A, B, C, D, E); const CHUNK_SIZE: usize = mem::size_of::(); #[inline] pub(crate) fn find_ws(s: &[u8]) -> Option { let offset = (32 + s.as_ptr().align_offset(CHUNK_SIZE)).min(s.len()); let mut i = 0; while i < offset { if s[i] <= b' ' { return Some(i); } i += 1; } if i < s.len() { find_ws_long(s, i) } else { None } } fn find_ws_long(s: &[u8], mut i: usize) -> Option { while i + CHUNK_SIZE <= s.len() { if let Some(j) = find_ws_usize(usize::from_le_bytes( unsafe { s.get_unchecked(i..i + CHUNK_SIZE) } .try_into() .unwrap(), )) { return Some(i + j); } i += CHUNK_SIZE; } while i < s.len() { if s[i] <= b' ' { return Some(i); } i += 1; } None } #[inline] fn find_ws_usize(s: usize) -> Option { const SUB: usize = 0x2121212121212121; const MASK: usize = 0x8080808080808080; let t = s.wrapping_sub(SUB) & MASK; (t != 0).then(|| (t.trailing_zeros() / 8) as usize) } pub struct Seq<'a, T, R> { src: &'a mut Input, n: usize, marker: PhantomData<*const T>, } impl<'a, T: Parse, R: Read> Iterator for Seq<'a, T, R> { type Item = T; fn next(&mut self) -> Option { if self.n > 0 { self.n -= 1; Some(self.src.input()) } else { None } } fn size_hint(&self) -> (usize, Option) { (self.len(), Some(self.len())) } } impl<'a, T: Parse, R: Read> ExactSizeIterator for Seq<'a, T, R> { fn len(&self) -> usize { self.n } } pub struct SeqMap<'a, T, F, R> { src: &'a mut Input, n: usize, f: F, marker: PhantomData<*const T>, } impl<'a, T, F: Map, R: Read> Iterator for SeqMap<'a, T, F, R> { type Item = F::Output; fn next(&mut self) -> Option { if self.n > 0 { self.n -= 1; Some(self.f.map(self.src)) } else { None } } fn size_hint(&self) -> (usize, Option) { (self.len(), Some(self.len())) } } impl<'a, T, F: Map, R: Read> ExactSizeIterator for SeqMap<'a, T, F, R> { fn len(&self) -> usize { self.n } } pub trait Parse { fn parse(src: &mut Input) -> Self; } impl Parse for Vec { fn parse(src: &mut Input) -> Self { src.byte_vec() } } impl Parse for String { fn parse(src: &mut Input) -> Self { String::from_utf8(src.byte_vec()).unwrap() } } pub trait ParseBytes { fn parse_bytes(s: &[u8]) -> Self; } macro_rules! parse_int { ($ ty : ident , $ ity : ident) => { impl ParseBytes for $ty { fn parse_bytes(s: &[u8]) -> Self { $ty(s, 0) } } impl ParseBytes for $ity { fn parse_bytes(s: &[u8]) -> Self { let (minus, s) = if let Some((b'-', s)) = s.split_first() { (true, s) } else { (false, s) }; let x = $ty(s, 0); (if minus { (!x).wrapping_add(1) } else { x }) as $ity } } }; } parse_int!(usize, isize); parse_int!(u8, i8); parse_int!(u16, i16); parse_int!(u32, i32); parse_int!(u64, i64); macro_rules! parse { ($ ty : ident) => { impl Parse for $ty { fn parse(src: &mut Input) -> Self { Self::parse_bytes(src.bytes()) } } }; } parse!(usize); parse!(u8); parse!(u16); parse!(u32); parse!(u64); parse!(isize); parse!(i8); parse!(i16); parse!(i32); parse!(i64); parse!(f32); parse!(f64); macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T : Parse) ,+> Parse for ($ ($ T ,) +) { fn parse < T : Read > (src : & mut Input < T >) -> Self { ($ ($ T :: parse (src) ,) +) } } } ; } tuple!(A); tuple!(A, B); tuple!(A, B, C); tuple!(A, B, C, D); tuple!(A, B, C, D, E); tuple!(A, B, C, D, E, F); tuple!(A, B, C, D, E, F, G); tuple!(A, B, C, D, E, F, G, H); impl Parse for [T; N] { fn parse(src: &mut Input) -> Self { struct Guard { ptr: *mut T, i: usize, } impl Drop for Guard { fn drop(&mut self) { unsafe { ptr::drop_in_place(slice::from_raw_parts_mut(self.ptr, self.i)); } } } let mut res: MaybeUninit<[T; N]> = MaybeUninit::uninit(); let mut g = Guard { ptr: res.as_mut_ptr() as *mut T, i: 0, }; unsafe { while g.i < N { g.ptr.add(g.i).write(src.input()); g.i += 1; } mem::forget(g); res.assume_init() } } } #[inline] fn toi8bytes(s: &[u8]) -> (u32, &[u8]) { let (p, rest) = s.split_at(8); let x = u64::from_le_bytes(p.try_into().unwrap()); const MASK1: u64 = 0x000f000f000f000f; let hi = (x >> 8) & MASK1; let lo = x & MASK1; let x = 10 * lo + hi; const MASK2: u64 = 0x0000ffff0000ffff; let hi = (x >> 16) & MASK2; let lo = x & MASK2; let x = 100 * lo + hi; let hi = (x >> 32) as u32; let lo = x as u32; let x = 10000 * lo + hi; (x, rest) } #[inline] fn toi4bytes(s: &[u8]) -> (u32, &[u8]) { let (p, rest) = s.split_at(4); let x = u32::from_le_bytes(p.try_into().unwrap()); const MASK: u32 = 0x000f000f; let hi = (x >> 8) & MASK; let lo = x & MASK; let x = 10 * lo + hi; let hi = x >> 16; let lo = x & 0x0000ffff; let x = 100 * lo + hi; (x, rest) } #[cfg(target_pointer_width = "32")] fn usize(s: &[u8], pre: usize) -> usize { u32(s, pre as u32) as usize } #[cfg(target_pointer_width = "64")] fn usize(s: &[u8], pre: usize) -> usize { u64(s, pre as u64) as usize } #[inline] fn u64(mut s: &[u8], pre: u64) -> u64 { let mut res = pre; while s.len() >= 8 { let (x, rest) = toi8bytes(s); res = 100000000 * res + x as u64; s = rest; } if s.len() >= 4 { let (x, rest) = toi4bytes(s); res = 10000 * res + x as u64; s = rest; } for &c in s { res = 10 * res + (c & 0xf) as u64; } res } #[inline] fn u32(mut s: &[u8], pre: u32) -> u32 { let mut res = pre; if s.len() >= 8 { let (x, rest) = toi8bytes(s); res = x; s = rest; } if s.len() >= 4 { let (x, rest) = toi4bytes(s); res = 10000 * res + x; s = rest; } for &c in s { res = 10 * res + (c & 0xf) as u32; } res } #[inline] fn u16(mut s: &[u8], pre: u16) -> u16 { let mut res = pre; if s.len() >= 4 { let (x, rest) = toi4bytes(s); res = 10000 * res + x as u16; s = rest; } for &c in s { res = 10 * res + (c & 0xf) as u16; } res } #[inline] fn u8(s: &[u8], pre: u8) -> u8 { let mut res = pre; for &c in s { res = 10 * res + (c & 0xf); } res } macro_rules! float { ($ ty : ident , $ uty : ident) => { impl ParseBytes for $ty { fn parse_bytes(s: &[u8]) -> Self { const TEN: [$ty; 18] = [ 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, ]; let (minus, s) = if let Some((b'-', s)) = s.split_first() { (true, s) } else { (false, s) }; let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') { (&s[..p], &s[p + 1..]) } else { (s, &s[..0]) }; let x = $uty(int, 0); let x = if fract.is_empty() { x as $ty } else { let ten = TEN .get(fract.len()) .copied() .unwrap_or_else(|| $ty::powi(10.0, fract.len() as _)); $uty(fract, x) as $ty / ten }; if minus { -x } else { x } } } }; } float!(f32, u32); float!(f64, u64); impl Parse for char { fn parse(src: &mut Input) -> Self { let s = src.str(); let mut cs = s.chars(); match cs.next() { Some(c) if cs.as_str().is_empty() => c, _ => panic!("input is not single char"), } } } pub struct Byte(pub u8); impl Parse for Byte { fn parse(src: &mut Input) -> Self { if let [b] = src.bytes() { Byte(*b) } else { panic!("input is not single byte") } } } } pub mod macros { #[macro_export] macro_rules ! w { ($ dst : expr , $ ($ arg : tt) *) => { if cfg ! (debug_assertions) && std :: io :: IsTerminal :: is_terminal (& std :: io :: stdout ()) { write ! ($ dst , "\x1B[1;33m{}\x1B[0m" , format_args ! ($ ($ arg) *)) . unwrap () ; } else { write ! ($ dst , $ ($ arg) *) . unwrap () ; } } } #[macro_export] macro_rules ! wln { ($ dst : expr) => { writeln ! ($ dst) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } ; ($ dst : expr , $ ($ arg : tt) *) => { { if cfg ! (debug_assertions) && std :: io :: IsTerminal :: is_terminal (& std :: io :: stdout ()) { writeln ! ($ dst , "\x1B[1;33m{}\x1B[0m" , format_args ! ($ ($ arg) *)) . unwrap () ; } else { writeln ! ($ dst , $ ($ arg) *) . unwrap () ; } # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } } #[macro_export] macro_rules! w_iter { ($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{ let mut first = true; for elem in $iter { if first { w!($dst, $fmt, elem); first = false; } else { w!($dst, concat!($delim, $fmt), elem); } } }}; ($ dst : expr , $ fmt : expr , $ iter : expr) => { w_iter!($dst, $fmt, $iter, " ") }; } #[macro_export] macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } } #[macro_export] macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } } #[macro_export] macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } } #[macro_export] #[doc(hidden)] macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } } #[macro_export] macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; } }