using MCSharp;
using System;
using System.IO;
using System.Threading;
using System.Runtime.Serialization;
using System.Runtime.Remoting.Messaging;

[Serializable()]
public class complex
{
 public double Real;
 public double Image;

 public complex() : this(0, 0) {}

 public complex(double Real) : this(Real, 0) {}

 public complex(double Real, double Image)
 {
  this.Real = Real;
  this.Image = Image;
 }

 public complex Conjugate
 {
  get
  {
   return new complex(Real, -Image);
  }
 }

 public double Magnitude
 {
  get
  {
   return Math.Sqrt(Math.Pow(Real,2) + Math.Pow(Image,2));
  }
 }

 public double ArgGrad
 {
  get
  {
   if ((Real >= 0) && (Image >= 0))
   {
    return Math.Atan(Image / Real) * 180 / Math.PI;
   }
   else if (Real < 0)
   {
    return 180 + Math.Atan(Image / Real) * 180 / Math.PI;
   }
   else //if ((Real > 0) && (Image < 0))
   {
    return 360 + Math.Atan(Image / Real) * 180 / Math.PI;
   }
  }
 }

 public complex Polar(double mag, double angle)
 {
  return new complex(mag * Math.Cos(Math.PI * angle / 180), mag * Math.Sin(Math.PI * angle / 180));
 }

 public complex Exponential(double mag, double angle)
 {
  return new complex(mag * Math.Cos(angle), mag * Math.Sin(angle));
 }

 public static complex operator+(complex fComplex)
 {
  return fComplex;
 }

 public static complex operator+(double amount, complex sComplex)
 {
  return new complex(sComplex.Real + amount, sComplex.Image);
 }

 public static complex operator+(complex fComplex, double amount)
 {
  return new complex(fComplex.Real + amount, fComplex.Image);
 }

 public static complex operator+(complex fComplex, complex sComplex)
 {
  return new complex(fComplex.Real + sComplex.Real, fComplex.Image + sComplex.Image);
 }

 public static complex operator-(complex fComplex)
 {
  return new complex(-fComplex.Real, -fComplex.Image);
 }

 public static complex operator-(double amount, complex sComplex)
 {
  return new complex(amount - sComplex.Real, -sComplex.Image);
 }

 public static complex operator-(complex fComplex, double amount)
 {
  return new complex(fComplex.Real - amount, fComplex.Image);
 }

 public static complex operator-(complex fComplex, complex sComplex)
 {
  return new complex(fComplex.Real - sComplex.Real, fComplex.Image - sComplex.Image);
 }

 public static complex operator*(double amount, complex sComplex)
 {
  return new complex(amount * sComplex.Real, amount * sComplex.Image);
 }

 public static complex operator*(complex fComplex, double amount)
 {
  return new complex(fComplex.Real * amount, fComplex.Image * amount);
 }

 public static complex operator*(complex fComplex, complex sComplex)
 {
  return new complex(fComplex.Real * sComplex.Real - fComplex.Image * sComplex.Image, 
   fComplex.Real * sComplex.Image + fComplex.Image * sComplex.Real);
 }

 public static complex operator/(double amount, complex sComplex)
 {
  return new complex((amount * sComplex.Real) / (sComplex.Real * sComplex.Real + sComplex.Image * sComplex.Image),
   (- amount * sComplex.Image) / (sComplex.Real * sComplex.Real + sComplex.Image * sComplex.Image));
 }

 public static complex operator/(complex fComplex, double amount)
 {
  return new complex(fComplex.Real / amount, fComplex.Image / amount);
 }

 public static complex operator/(complex fComplex, complex sComplex)
 {
  return new complex((fComplex.Real * sComplex.Real + fComplex.Image * sComplex.Image) / 
   (sComplex.Real * sComplex.Real + sComplex.Image * sComplex.Image),
   (sComplex.Real * fComplex.Image - fComplex.Real * sComplex.Image) / 
   (sComplex.Real * sComplex.Real + sComplex.Image * sComplex.Image));
 }

 public override string ToString()
 {
  string str1 = "", str2 = "", str3 = "";
  if ((this.Real >= 0) && (this.Image >= 0))
  {
   str1 = this.Real.ToString("0.0000000000");
   str2 = " + ";
   str3 = "i * " + this.Image.ToString("0.0000000000");
  } 
  else if ((this.Real >= 0) && (this.Image <= 0))
  {
   str1 = this.Real.ToString("0.0000000000");
   str2 = " - ";
   str3 = "i * " + (-this.Image).ToString("0.0000000000");
  } 
  else if ((this.Real <= 0) && (this.Image >= 0))
  {
   str1 = "- " + (-this.Real).ToString("0.0000000000");
   str2 = " + ";
   str3 = "i * " + this.Image.ToString("0.0000000000");
  }
  else if ((this.Real <= 0) && (this.Image <= 0))
  {
   str1 = "- " + (-this.Real).ToString("0.0000000000");
   str2 = " - ";
   str3 = "i * " + (-this.Image).ToString("0.0000000000");
  }
  return str1 + str2 + str3;
 }
}

[Serializable()]
public class FFT : ISerializable
{
 // -------------Channels declarations----------------
 [NonSerialized] private MCSharp.Channel c1;

 // -------------Queues-------------------------------
 [NonSerialized] private MCSharp.ThreadQ mcQueueGet;

 // -------------Masks--------------------------------
 [NonSerialized] private MCSharp.BitMask mcBitMaskGetc1 = new MCSharp.BitMask();
 private const int mcMaskGet = 1 << 0;
 private const int mcMaskc1 = 1 << 1;
 private const int mcMaskGetc1 = mcMaskGet | mcMaskc1;

 // -------------User's code--------------------------
 public void Solve( Channel c, complex[] In )
 {
  if (In.Length < 2)
  {
   c.Send( new object[] { LocalSolve( In ) } );
  }
  else
  {
   uint n = (uint) In.Length;
   uint nh = (uint) (n / 2);
   uint k;
   complex w;
   complex wn = new complex();
   complex[] a0 = new complex[nh];
   complex[] a1 = new complex[nh];
   complex[] y0; // = new complex[nh];
   complex[] y1; // = new complex[nh];
   complex[] y = new complex[n];
    
   wn = wn.Exponential(1, 2 * Math.PI / n);
   w = new complex(1, 0);
      
   for (k = 0; k < nh; k++)
   {
    a0[k] = In[k * 2];
    a1[k] = In[k * 2 + 1];
   }

   FFT fft = new FFT();
   MCSharp.TCP.DeliverMovableMethod( fft, "Solve", new object[] { c1, a0 } );
   y1 = LocalSolve(a1);
   y0 = new complex[nh];
   y0 = Get();

   for (k = 0; k < nh; k++)
   {
    y[k] = y0[k] + w * y1[k];
    y[k + nh] = y0[k] - w * y1[k];
    w = w * wn;
   }
        
   c.Send( new object[] { y } );
  }
 }

 private complex[] LocalSolve(complex[] In)
 {
  uint n = (uint) In.Length;
  uint nh = (uint) (n / 2);
  uint k;
  complex w;
  complex wn = new complex();
  complex[] a0 = new complex[nh];
  complex[] a1 = new complex[nh];
  complex[] y0 = new complex[nh];
  complex[] y1 = new complex[nh];
  complex[] y = new complex[n];

  if (n == 1)
  {
   return (In);
  }
    
  wn = wn.Exponential(1, 2 * Math.PI / n);
  w = new complex(1, 0);
      
  for (k = 0; k < nh; k++)
  {
   a0[k] = In[k * 2];
   a1[k] = In[k * 2 + 1];
  }

  y0 = LocalSolve(a0);
  y1 = LocalSolve(a1);

  for (k = 0; k < nh; k++)
  {
   y[k] = y0[k] + w * y1[k];
   y[k + nh] = y0[k] - w * y1[k];
   w = w * wn;
  }

  return (y);
 }

 // -------------MCSharp's functions------------------
 public FFT() 
 {
  initiate();
 }

 public FFT( SerializationInfo info, StreamingContext context ) 
 {
  initiate();
 }

 public void GetObjectData( SerializationInfo info, StreamingContext context ) 
 {
 }

 public void initiate() 
 {
  LocalHost mcLocalHost = LocalHost.CurrentHost;
  Monitor.Enter( mcLocalHost.objects );
  int mcObjectNumber = mcLocalHost.objects.Count + 1;
  mcLocalHost.objects.Add( mcObjectNumber, this );
  Monitor.Exit( mcLocalHost.objects );

  c1 = new Channel( this, mcObjectNumber, "mcChannelc1" );

  mcQueueGet = new MCSharp.ThreadQ();
 }

 private void scan() 
 {
  if ( mcBitMaskGetc1.match( mcMaskGetc1 ) )
   mcQueueGet.wakeup();
 }
 // -------------Channels-----------------------------
 [OneWay]
 public void mcChannelc1( complex[] x ) 
 {
  lock( mcQueueGet ) 
  {
   c1.Enqueue( x );
   if ( !mcBitMaskGetc1.match( mcMaskc1 ) ) 
   {
    mcBitMaskGetc1.set( mcMaskc1 );
    scan();
   }
  }
 }

 public complex[] Get() 
 {
  Monitor.Enter( mcQueueGet );
  if ( !mcBitMaskGetc1.match( mcMaskGet ) ) goto now;
  later:
   mcQueueGet.yield( mcQueueGet );
  if ( mcQueueGet.empty ) mcBitMaskGetc1.clear( mcMaskGet );
  now:
   if ( mcBitMaskGetc1.match( mcMaskc1 ) ) 
   {
    complex[] x = (complex[]) c1.Dequeue(); 
    if ( c1.Count == 0 ) mcBitMaskGetc1.clear( mcMaskc1 );

    scan();
    Monitor.Exit( mcQueueGet );
   {
    return x;
   }
   }
   else 
   {
    mcBitMaskGetc1.set( mcMaskGet );
    goto later;
   }
 }
}

[Serializable()]
class RecursiveFFT : ISerializable
{
 // -------------Channels declarations----------------
 [NonSerialized] private MCSharp.Channel c;

 // -------------Queues-------------------------------
 [NonSerialized] private MCSharp.ThreadQ mcQueueGet;

 // -------------Masks--------------------------------
 [NonSerialized] private MCSharp.BitMask mcBitMaskGetc = new MCSharp.BitMask();
 private const int mcMaskGet = 1 << 0;
 private const int mcMaskc = 1 << 1;
 private const int mcMaskGetc = mcMaskGet | mcMaskc;

 // -------------User's code--------------------------
 public static void Main(string[] args)
 {
  MCSharp.Session.Init( args );
  uint n, i, k;

  RecursiveFFT rfft = new RecursiveFFT();
  FFT fft = new FFT();

  try
  {
   FileStream f = new FileStream(args[0], FileMode.Open, FileAccess.Read);
   StreamReader rf = new StreamReader(f);

   string str = rf.ReadLine();

   n = (uint) System.Convert.ToInt32(str);
   k = (uint) Math.Ceiling(Math.Log(n, 2));
   complex[] S = new complex[(int) Math.Pow(2, k)];

   string[] ss = new string[2];

   for (i = 0; i < n; i++) 
   {
    str = rf.ReadLine();
    if (str != null)
    {
     ss = str.Split(new char[] {' '}, 2);
     S[i] = new complex(System.Convert.ToDouble(ss[0]), System.Convert.ToDouble(ss[1]));
    }
   }
   rf.Close();

   MCSharp.TCP.DeliverMovableMethod( fft, "Solve", new object[] { rfft.c, S } );
   S = rfft.Get();

   for (i = 0; i < n; i++)
   {
    System.Console.WriteLine("{0}", S[i]);
   }

  }
  catch (Exception e)
  {
   Console.WriteLine("\nNow processing Main() Exception:");
   while (e != null)
   {
    Console.WriteLine("\tInner:  {0}", e.Message);
    e = e.InnerException;
   }
  }
  MCSharp.Session.FinalizeIt();
 }
 // -------------MCSharp's functions------------------
 public RecursiveFFT() 
 {
  initiate();
 }

 public RecursiveFFT( SerializationInfo info, StreamingContext context ) 
 {
  initiate();
 }

 public void GetObjectData( SerializationInfo info, StreamingContext context ) 
 {
 }

 public void initiate() 
 {
  LocalHost mcLocalHost = LocalHost.CurrentHost;
  Monitor.Enter( mcLocalHost.objects );
  int mcObjectNumber = mcLocalHost.objects.Count + 1;
  mcLocalHost.objects.Add( mcObjectNumber, this );
  Monitor.Exit( mcLocalHost.objects );

  c = new Channel( this, mcObjectNumber, "mcChannelc" );
   
  mcQueueGet = new MCSharp.ThreadQ();
 }

 private void scan() 
 {
  if ( mcBitMaskGetc.match( mcMaskGetc ) )
   mcQueueGet.wakeup();
 }

 // -------------Channels-----------------------------
 [OneWay]
 public void mcChannelc( complex[] x ) 
 {
  lock( mcQueueGet ) 
  {
   c.Enqueue( x );
   if ( !mcBitMaskGetc.match( mcMaskc ) ) 
   {
    mcBitMaskGetc.set( mcMaskc );
    scan();
   }
  }
 }

 public complex[] Get() 
 {
  Monitor.Enter( mcQueueGet );
  if ( !mcBitMaskGetc.match( mcMaskGet ) ) goto now;
  later:
   mcQueueGet.yield( mcQueueGet );
  if ( mcQueueGet.empty ) mcBitMaskGetc.clear( mcMaskGet );
  now:
   if ( mcBitMaskGetc.match( mcMaskc ) ) 
   {
    complex[] x = (complex[]) c.Dequeue(); 
    if ( c.Count == 0 ) mcBitMaskGetc.clear( mcMaskc );

    scan();
    Monitor.Exit( mcQueueGet );
   {
    return x;
   }
   }
   else 
   {
    mcBitMaskGetc.set( mcMaskGet );
    goto later;
   }
 }
}