// $Id: ackermann.csharp,v 1.0 2002/02/14 10:58:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    public static int Ack(int M, int N) {
        if (M == 0) return( N + 1 );
        if (N == 0) return( Ack(M - 1, 1) );
        return( Ack(M - 1, Ack(M, (N - 1))) );
    }
    
    public static int Main(String[] args) {
        int n;
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
    
        Console.WriteLine("Ack(3," + n.ToString() + "): " + System.Convert.ToString(Ack(3, n)) + "\n");
        return(0);
    }
}

// $Id: ary3.csharp,v 1.0 2002/05/09 12:57:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    public static int Main(String[] args) {        
        int i, j, k, n;
        int[] x;
        int[] y;
        
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
        
        x = new int[n];
        y = new int[n];
        
        for (i = 0; i < n; i++)
            x[i] = i + 1;
        for (k = 0; k < 1000; k++ )
            for (j = n-1; j >= 0; j--)
                y[j] += x[j];
        
        Console.WriteLine(y[0].ToString() + " " + y[n-1].ToString());
        return(0);
    }
}

// $Id: wc.csharp,v 1.0 2002/02/14 10:21:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {
    public static int Main(String[] args) {
        int nread;
        int i;
        char c;
        char[] buf = new char[4096];
        int nl = 0, nw = 0, nc = 0;
        bool state = false;
        while( (nread = Console.In.Read( buf, 0, 4096)) > 0 ) {
            nc += nread;
            for (i=0; i<nread; i++) {
                c = buf[i];
                if (c == '\n') ++nl;
                if (c == ' ' || c == '\n' || c == '\t') state = false;
                else if (state == false) {
                    state = true;
                    nw++;
                }
            }
        }
        Console.WriteLine(nl.ToString() + " " + nw.ToString() + " " + nc.ToString() + "\n");
        return(0);
    }
}

// $Id: exceptions.csharp,v 1.0 2002/09/28 10:21:00 dada Exp $
// http://dada.perl.it/shootout/
// contributed by Erik Saltwell

using System;

namespace Exceptions
{
    class LoException : System.Exception
    {
        public LoException(){}
    }

    class HiException : System.Exception 
    {
        public HiException(){}
    }

    public class App 
    {
        static int Lo = 0;
        static int Hi = 0;
        static int count=0;
        public static void Main(string[] args)
        {
            int n = int.Parse(args[0]);
            for (count=0; count<n; count++) 
            {
                SomeFunction();
            }
            System.Text.StringBuilder bldr = new System.Text.StringBuilder(100);
            bldr.Append("Exceptions: HI=").Append(Hi).Append(" / LO=").Append(Lo);
            Console.WriteLine(bldr.ToString());
        }

        public static void SomeFunction() 
        {
            try 
            {
                HiFunction();
            } 
            catch (Exception e) 
            {
                Console.WriteLine("We shouldn't get here: " + e.Message);
            }
        }

        public static void HiFunction() 
        {
            try 
            {
                LoFunction();
            } 
            catch (HiException) 
            {
                Hi++;
            }
        }
        public static void LoFunction()
        {
            try 
            {
                BlowUp();
            } 
            catch (LoException) 
            {
                Lo++;
            }
        }
        public static void BlowUp() 
        {
            if ((count & 1) == 0) 
            {
                throw new LoException();
            } 
            else 
            {
                throw new HiException();
            }
        }
    }
}

// $Id: fibo.csharp,v 1.0 2002/02/14 10:49:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    public static int fib(int n) {
        return (n < 2) ? 1 : fib(n-2) + fib(n-1);
    }
    public static int Main(String[] args) {
        int N;
        int f;
        N = System.Convert.ToInt32(args[0]);
        if(N < 1) N = 1;
        f = fib(N);
        Console.WriteLine(f.ToString()+"\n");
        return(0);
    }
}

// $Id: hash.csharp,v 1.0 2002/02/14 14:48:00 dada Exp $
// http://dada.perl.it/shootout/

using System;
using System.Collections;

class App {
    public static int Main(String[] args) {        
        int n;
        Hashtable X = new Hashtable();     
        int c = 0;
        
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
        
        for(int i=1; i<=n; i++) {
            X.Add( i.ToString("x"), i);
        }
        
        for(int i=n; i>0; i--) {
            if(X.ContainsKey(i.ToString())) c++;
        }
        Console.WriteLine(c.ToString());
        return(0);
    }
}

// $Id: hash2.csharp,v 1.0 2002/02/14 15:01:00 dada Exp $
// http://dada.perl.it/shootout/

using System;
using System.Collections;

class App {
    public static int Main(String[] args) {        
        int n;        
        Hashtable hash1 = new Hashtable();
        Hashtable hash2 = new Hashtable();
        
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
                
        for(int i=0; i<=9999; i++) {
            hash1.Add( "foo_" + i.ToString(), i);
        }
        
        for(int i = 0; i < n; i++) {
            IDictionaryEnumerator it = hash1.GetEnumerator();
            while(it.MoveNext()) {
                if(hash2.ContainsKey(it.Key)) {
                    int v1 = (int) hash1[it.Key];
                    int v2 = (int) hash2[it.Key];                
                    hash2[it.Key] = v1 + v2;
                } else {
                    hash2.Add(it.Key, hash1[it.Key]);
                }
            }
        }
        Console.WriteLine(hash1["foo_1"] + " " + hash1["foo_9999"] + " " + hash2["foo_1"] + " " + hash2["foo_9999"]);
        return(0);
    }
}

// $Id: heapsort.csharp,v 1.0 2002/09/28 10:21:00 dada Exp $
// http://dada.perl.it/shootout/
// contributed by Erik Saltwell

using System;

namespace HeapSort
{
    class App
    {
        public const long IM = 139968;
        public const long IA =   3877;
        public const long IC =  29573;

        public static long last = 42;
        
        public static double gen_random(double max) 
        {
            return( max * (last = (last * IA + IC) % IM) / IM );
        }

        public static int count =0;

        [STAThread]
        static void Main(string[] args)
        {
            count = int.Parse(args[0]);
            double[] ary = new double[count+1];
            unsafe
            {
                for(int i=0;i<=count;++i)
                {
                    ary[i]=gen_random(1);
                }
            }
            heapsort(ary);
            Console.WriteLine(ary[count]);
        }
    
        public static void heapsort(double[] ra) 
        {
            unsafe
            {
            int l, j, ir, i;
            double rra;

            l = (count >> 1) + 1;
            ir = count;
                for (;;) 
                {
                    if (l > 1) 
                    {
                        rra = ra[--l];
                    } 
                    else 
                    {
                        rra = ra[ir];
                        ra[ir] = ra[1];
                        if (--ir == 1) 
                        {
                            ra[1] = rra;
                            return;
                        }
                    }
                    i = l;
                    j = l << 1;
                    while (j <= ir) 
                    {
                        if (j < ir && ra[j] < ra[j+1]) { ++j; }
                        if (rra < ra[j]) 
                        {
                            ra[i] = ra[j];
                            j += (i = j);
                        } 
                        else 
                        {
                            j = ir + 1;
                        }
                    }
                    ra[i] = rra;
                }
            }
        }

    }
}

// $Id: hello.csharp,v 1.0 2002/02/14 11:40:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    public static int Main(String[] args) {
        Console.WriteLine("hello world\n");
        return(0);
    }
}

// $Id: listops.csharp,v 1.0 2002/09/28 10:21:00 dada Exp $
// http://dada.perl.it/shootout/
// contributed by Erik Saltwell
using System;

namespace ListOps
{
    class IntDeQueue : ICloneable
    {
        private int[] data=null;
        private int start=0;
        private int end=0;
        private int size=0;
        private int temp=0;
        public bool Empty{get{return start==end;}}
        public object Clone()
        {
            IntDeQueue temp =new IntDeQueue(size-1);
            temp.start=start;
            temp.end=end;
            data.CopyTo(temp.data, 0);
            return temp;
        }

        public bool Equals(IntDeQueue other)
        {
            if(Count!=other.Count)
                return false;
            int i = this.start;
            int iOther = other.start;
            while(i!=this.end)
            {
                if(data[i]!=other.data[iOther])
                    return false;
                Advance(ref i);
                other.Advance(ref iOther);
            }
            return true;
        }

        public int Count
        {
            get
            {
                if(end>=start) 
                    return  end-start;
                else 
                    return size + end - start; 
            }
        }
        public void Reverse()
        {
            if(Count<2)
                return;
            Array.Reverse(data);
            int endEnd=size-1;
            int startEnd=0;
            if(end<start)
            {
                endEnd = 0;
                startEnd=size-1;
            }
            int temp = start;
            Regress(ref end);
            start = Math.Abs(startEnd - Math.Abs(end - endEnd));
            end = Math.Abs(endEnd - Math.Abs(temp - startEnd));
            Advance(ref end);
        }

        public void PushFront(int i)
        {
            temp = start;
            Regress(ref start);
            if(start==end)
            {
                start=temp;
                throw new System.Exception("Invalid operation");
            }
            data[start]=i;
        }
        public int PopFront()
        {
            int i=data[start];
            if(start!=end)
                Advance(ref start);
            else
                throw new System.Exception("Invalid operation");
            return i;
        }
        public int PeekFront() 
        {
            if(start==end)
                throw new System.Exception("Invalid Operation");
            return data[start];
        }
        public int PeekBack() 
        {
            if(start==end)
                throw new System.Exception("Invalid Operation");
            int temp = end;
            Regress(ref temp);
            return data[temp];
        }
        public void PushBack(int i)
        {
            temp = end;
            Advance(ref end);
            if(start==end)
            {
                end= temp;
                throw new System.Exception("Invalid operation");
            }
            data[temp]=i;
        }
        public int PopBack()
        {
            if(start!=end)
                Regress(ref end);
            else
                throw new System.Exception("Invalid operation");
            return data[end];
        }
        public IntDeQueue(int Size){data = new int[Size+1];this.size=Size+1;}
        private void Advance(ref int item)
        {
            if((++item)==size)
                item=0;
        }

        private void Regress(ref int item)
        {
            if(item!=0)
                --item;
            else
                item = (size-1);
        }

        public void Clear()
        {
            start=0;
            end=0;
        }
    }

    class App
    {
        public const int SIZE=10000;
        [STAThread]
        static void Main(string[] args)
        {
            int n=int.Parse(args[0]);
            int result=0;
            for(int i=0;i<n;++i)
                result = RunLists();
            Console.WriteLine(result);
        }
        static public int RunLists()
        {
            IntDeQueue q = new IntDeQueue(SIZE);
            for(int i=0;i<SIZE;++i)
                q.PushBack(i+1);
            IntDeQueue q2 = (IntDeQueue)q.Clone();
            IntDeQueue q3=new IntDeQueue(SIZE);
            while(!q2.Empty)
                q3.PushBack(q2.PopFront());
            while(!q3.Empty)
                q2.PushBack(q3.PopBack());
            q.Reverse();
            if(q.PeekFront() != SIZE)
            {
                Console.WriteLine("q.PeekFront()!=SIZE");
                return 0;
            }
            if(!q.Equals(q2))
            {
                Console.WriteLine("q!=q2");
                return 0;
            }

            return q.Count;
        }
    }
}

// $Id: matrix.csharp,v 1.0 2002/05/09 12:45:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    static int SIZE = 30;

    public static int[,] mkmatrix (int rows, int cols) {
        int count = 1;
        int[,] m = new int[rows,cols];
        for (int i=0; i<rows; i++) {
            for (int j=0; j<cols; j++) {
            m[i,j] = count++;
            }
        }
        return(m);
    }

    public static void mmult (int rows, int cols, 
                          int[,] m1, int[,] m2, int[,] m3) {
        for (int i=0; i<rows; i++) {
            for (int j=0; j<cols; j++) {
                int val = 0;
                for (int k=0; k<cols; k++) {
                    val += m1[i,k] * m2[k,j];
                }
                m3[i,j] = val;
            }
        }
    }

    public static int Main(String[] args) {        
        int n;
        int[,] m1 = mkmatrix(SIZE, SIZE);
        int[,] m2 = mkmatrix(SIZE, SIZE);
        int[,] mm = new int[SIZE,SIZE];
        
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
        
        for (int i=0; i<n; i++) {
            mmult(SIZE, SIZE, m1, m2, mm);
        }
        
        Console.WriteLine(
            mm[0,0].ToString() + " " + mm[2,3].ToString() + " " +
            mm[3,2].ToString() + " " + mm[4,4].ToString());
        return(0);
    }
}

// $Id: methcall.csharp,v 1.0 2002/02/14 13:01:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class Toggle {
    public bool state = true;
    public Toggle(bool start_state) {
        this.state = start_state;
    }
    
    public bool value() {
        return(this.state);
    }
    
    public Toggle activate() {
        this.state = !this.state;
        return(this);
    }
}

class NthToggle : Toggle {
    int count_max = 0;
    int counter = 0;

    public NthToggle(bool start_state, int max_counter) : base(start_state) {
        this.count_max = max_counter;
        this.counter = 0;
    }
    public new NthToggle activate() {
        this.counter += 1;
        if (this.counter >= this.count_max) {
            this.state = !this.state;
            this.counter = 0;
        }
        return(this);
    }
}

class App {
    public static int Main(String[] args) {
        bool val = true;
        int n;

        Toggle toggle = new Toggle(val);
        NthToggle ntoggle = new NthToggle(true, 3);

        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;

        for (int i=0; i<n; i++) {
            val = toggle.activate().value();
        }
        Console.WriteLine((val ? "true" : "false"));
        
        for (int i=0; i<n; i++) {
            val = ntoggle.activate().value();
        }
        Console.WriteLine((val ? "true" : "false"));
        
        return(0);
    }
}

// $Id: nestedloop.csharp,v 1.0 2002/02/14 11:17:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    public static int Main(String[] args) {
        int n;
        int a, b, c, d, e, f, x=0;
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;

        for (a=0; a<n; a++)
        for (b=0; b<n; b++)
            for (c=0; c<n; c++)
            for (d=0; d<n; d++)
                for (e=0; e<n; e++)
                for (f=0; f<n; f++)
                    x++;
    
        Console.WriteLine(x.ToString() + "\n");
        return(0);
    }
}

// $Id: objinst.csharp,v 1.0 2002/02/14 13:27:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class Toggle {
    public bool state = true;
    public Toggle(bool start_state) {
        this.state = start_state;
    }
    
    public bool value() {
        return(this.state);
    }
    
    public Toggle activate() {
        this.state = !this.state;
        return(this);
    }
}

class NthToggle : Toggle {
    int count_max = 0;
    int counter = 0;

    public NthToggle(bool start_state, int max_counter) : base(start_state) {
        this.count_max = max_counter;
        this.counter = 0;
    }
    public new NthToggle activate() {
        this.counter += 1;
        if (this.counter >= this.count_max) {
            this.state = !this.state;
            this.counter = 0;
        }
        return(this);
    }
}

class App {
    public static int Main(String[] args) {
        int n;

        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;

        Toggle toggle1 = new Toggle(true);
        for (int i=0; i<5; i++) {
            Console.WriteLine((toggle1.activate().value()) ? "true" : "false");
        }

        for (int i=0; i<n; i++) {
            Toggle toggle = new Toggle(true);
        }
        Console.WriteLine();
        
        
        NthToggle ntoggle1 = new NthToggle(true, 3);
        for (int i=0; i<8; i++) {
            Console.WriteLine((ntoggle1.activate().value()) ? "true" : "false");
        }
        for (int i=0; i<n; i++) {
            NthToggle toggle = new NthToggle(true, 3);
        }
        return(0);
    }
}

// $Id: prodcons.csharp,v 1.0 2002/04/30 17:25:00 dada Exp $
// http://dada.perl.it/shootout/

// based on a sample from the Microsoft .NET SDK Documentation

using System;
using System.Threading;
using System.Collections;

class prodcons {

    private int   m_produced = 0;
    private int   m_consumed = 0;
    private int   m_count = 0;
    private Queue m_smplQueue;
    
    public prodcons(int count) {
        m_count = count;
        m_smplQueue = new Queue(); 
    }

    public void Producer() {
        lock(m_smplQueue) {
            while(m_produced < m_count) {
               //Wait, if the queue is busy.
               Monitor.Wait(m_smplQueue);
               //Push one element.
               m_smplQueue.Enqueue(m_produced);
               //Release the waiting thread.
               Monitor.Pulse(m_smplQueue);   
               m_produced++;
            }
        }
    }

    public void Consumer() {

        while(m_consumed < m_count) {
            lock(m_smplQueue) {
                Monitor.Pulse(m_smplQueue);
                while(Monitor.Wait(m_smplQueue,1000)) {
                    //Pop the first element.
                    m_smplQueue.Dequeue();
                    //Release the waiting thread.
                    Monitor.Pulse(m_smplQueue);
                    m_consumed++;
                }
            }
        }
    }
   
    public void run() {         
         //Create the first thread.
         Thread tProducer = new Thread(new ThreadStart(this.Producer));
         //Create the second thread.
         Thread tConsumer = new Thread(new ThreadStart(this.Consumer));
         //Start threads.
         tProducer.Start();
         tConsumer.Start();
         //wait to the end of the two threads
         tProducer.Join();
         tConsumer.Join();         
         //Print the number of the queue elements.
         Console.WriteLine(this.m_produced.ToString() + " " + this.m_consumed.ToString());     
    }
}

class App {
    public static int Main(String[] args) {
        int n;
        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;
        new prodcons(n).run();
        return 0;
    }
}

// $Id: random.csharp,v 1.0 2002/02/14 13:42:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {

    public static int IM = 139968;
    public static int IA = 3877;
    public static int IC = 29573;
    public static long last = 42;


    public static double gen_random(double max) {        
        last = (last * IA + IC) % IM;
        return( max * last / IM );
    }

    public static int Main(String[] args) {
        int n;
        double result = 0;

        n = System.Convert.ToInt32(args[0]);
        if(n < 1) n = 1;

        while (n-->0) {
            result = gen_random(100.0);
        }
        Console.WriteLine(result.ToString("F9"));

        return(0);
    }
}

// $Id: reversefile.csharp,v 1.0 2002/11/29 10:31:00 dada Exp $
// http://dada.perl.it/shootout/
// 
// This is a straightforward *alternative* C# implementation.
// It'll be interesting to compare it to a fast C# implementation.
//
// contributed by Isaac Gouy

using System;
using System.Collections;

namespace LanguageShootout
{
    class reversefile
    {
        [STAThread]
        static void Main(string[] args)
        {
            Stack lines = new Stack();
            String line;
            while ( (line = Console.ReadLine()) != null ) lines.Push(line);

            System.Collections.IEnumerator items = lines.GetEnumerator();
            while ( items.MoveNext() ) Console.WriteLine( items.Current );
        }
    }
}

// $Id: sieve.csharp,v 1.0 2002/02/14 14:02:00 dada Exp $
// http://dada.perl.it/shootout/

using System;


class App {
    public static int Main(String[] args) {        
        int NUM;
        bool[] flags = new bool[8193];
        long i, k;
        int count = 0;
        
        NUM = System.Convert.ToInt32(args[0]);
        if(NUM < 1) NUM = 1;
        
        while(NUM-->0) {
            count = 0;
            for(i=2; i <= 8192; i++) {
                flags[i] = true;
            }
            for(i=2; i <= 8192; i++) {
                if(flags[i]) {
                    // remove all multiples of prime: i
                    for(k=i+i; k <= 8192; k+=i) {
                        flags[k] = false;
                    }
                    count++;
                }
            }
        }
        
        Console.WriteLine("Count: " + count.ToString());
        return(0);
    }
}

// $Id: moments.csharp,v 1.0 2002/11/27 13:19:00 dada Exp $
// http://dada.perl.it/shootout/
// 
// Transliterated from the Java implementation.  
//
// contributed by Isaac Gouy

using System;
using System.Collections;

namespace LanguageShootout
{
    class Moments
    {
        [STAThread]
        static void Main(string[] args)
        {
            String line;
            ArrayList numbers = new ArrayList();
            double num, sum = 0.0;
            double mean = 0.0;
            double average_deviation = 0.0;
            double standard_deviation = 0.0;
            double variance = 0.0;
            double skew = 0.0;
            double kurtosis = 0.0;
            double median = 0.0;
            double deviation = 0.0;
            int i, n, mid = 0;

            while ( (line = Console.ReadLine()) != null ) {
                num = Double.Parse(line);
                sum += num;
                numbers.Add(num);
            }

            n = numbers.Count;
            mean = sum / n;
            for (i=0; i<n; i++) {
                deviation = (double)numbers[i] - mean;
                average_deviation += Math.Abs(deviation);
                variance += Math.Pow(deviation,2);
                skew += Math.Pow(deviation,3);
                kurtosis += Math.Pow(deviation,4);
            }
            average_deviation /= n;
            variance /= (n - 1);
            standard_deviation = Math.Sqrt(variance);
            if (variance != 0.0) {
                skew /= (n * variance * standard_deviation);
                kurtosis = kurtosis/(n * variance * variance) - 3.0;
            }
    
            numbers.Sort();

            mid = n / 2;
            median = (n % 2 != 0) ?
                (double)numbers[mid] :
                ((double)numbers[mid] + (double)numbers[mid-1]) / 2;

            Console.WriteLine("n:                  {0:d}", n);
            Console.WriteLine("median:             {0:f6}", median);
            Console.WriteLine("mean:               {0:f6}", mean);
            Console.WriteLine("average_deviation:  {0:f6}", average_deviation);
            Console.WriteLine("standard_deviation: {0:f6}", standard_deviation);
            Console.WriteLine("variance:           {0:f6}", variance);
            Console.WriteLine("skew:               {0:f6}", skew);
            Console.WriteLine("kurtosis:           {0:f6}", kurtosis);
        }
    }
}

// $Id: strcat.csharp,v 1.1 2002/10/16 16:52:00 dada Exp $
// http://dada.perl.it/shootout/
//
// code contributed by Erik Saltwell  

using System;

class App {

    public static int Main(String[] args) {
        int N;
        N = int.Parse(args[0]);
        if(N < 1) N = 1;

        System.Text.StringBuilder sb = new System.Text.StringBuilder(32);

        for (int i=0; i<N; i++) {
            sb.Append("hello\n");
        }

        Console.WriteLine(sb.Length);
        return(0);
    }
}

// $Id: sumcol.csharp,v 1.0 2002/02/14 11:20:00 dada Exp $
// http://dada.perl.it/shootout/

using System;

class App {
    public static int Main(String[] args) {
        int sum = 0;

        for (String line = Console.In.ReadLine(); line != null; line = Console.In.ReadLine()) {
            sum += System.Convert.ToInt32(line);
        }
        Console.WriteLine(sum.ToString() + "\n");
        return(0);
    }
}