/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P07Fourier {

  private static final String FileInputName = "fourier.in";
  private static final String FileOutputName = "fourier.out";

  private static List<Complex> fft(List<Complex> a) {
    int n = a.size();
    if (n <= 1)
      return a;
    Complex wn = new Complex(Math.cos(2 * Math.PI / n), Math.sin(2 * Math.PI / n));
    Complex w = new Complex(1.0, 0.0);
    List<Complex> a0 = new ArrayList<Complex>();
    List<Complex> a1 = new ArrayList<Complex>();
    List<Complex>  y = new ArrayList<Complex>();
    for (int i = 0; i < n; i++) {
      Complex c = a.get(i);
      if (i % 2 == 0)
        a0.add(c);
      else
        a1.add(c);
      y.add(new Complex(0, 0));
    }
    List<Complex> y0 = fft(a0);
    List<Complex> y1 = fft(a1);
    for (int i = 0; i < n / 2; i++) {
      Complex aux = w.multiply(y1.get(i));
      y.set(i, y0.get(i).add(aux));
      y.set(i + n / 2, y0.get(i).substract(aux));
      w = w.multiply(wn);
    }
    return y;
  }

  public static void main(String[] args) throws IOException {
    Scanner sc = null;
    PrintStream out = null;
    try {
      out = new PrintStream(new File(FileOutputName));
      sc = new Scanner(new File(FileInputName)).useLocale(Locale.ENGLISH);
      List<Complex> a = new ArrayList<Complex>();
      while (sc.hasNextDouble()) {
        double re = sc.nextDouble();
        double im = sc.nextDouble();
        a.add(new Complex(re, im));
      }
      List<Complex> y = fft(a);
      for (Complex c : y) {
        out.println(c);
      }
    } finally {
      if (sc != null) {
        sc.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}

class Complex {
  private double re, im;

  Complex() {
    this(0, 0);
  }

  Complex(double newRe, double newIm) {
    re = newRe;
    im = newIm;
  }

  public String toString() {
    return this.re + "  " + this.im;
  }

  public Complex add(Complex z) {
    return new Complex(re + z.re, im + z.im);
  }

  public Complex substract(Complex z) {
    return new Complex(re - z.re, im - z.im);
  }

  public Complex multiply(Complex z) {
    return new Complex(re * z.re - im * z.im, re * z.im + im * z.re);
  }
}