using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {

        }
    }
    class Węzeł
    {
        public Węzeł rodzic;
        public int wartość;
        public Węzeł lewe;
        public Węzeł prawe;

        public Węzeł(int wartość)
        {
            this.wartość = wartość;
        }
    }
    class Drzewo //: IAISD wklej push i popa z zeszłych zajęć
    {
        public Węzeł korzeń;
        public int głębokość;
        public int length;
        public Drzewo(int wartość) //Drzewo d = new Drzewo;
        {
            this.korzeń = new Węzeł(wartość);
            this.głębokość = 0;
            this.length = 1;
        }

        Węzeł ZnajdźRodzica(int numer)
        {
            List<int> droga = new List<int>();
            int tmp = numer;
            while (tmp > 0)
            {
                --tmp;
                tmp = tmp / 2;
                droga.Add(tmp);
            }
            droga.Reverse();
            var rodzic = this.korzeń;
            for (int i = 1; i < droga.Count; i++)
            {
                if (droga[i] % 2 == 1)
                {
                    rodzic = rodzic.lewe;
                }
                else
                {
                    rodzic = rodzic.prawe;
                }
            }
            return rodzic;
        }
        interface IAiSD
        {
            int Pop();
            void Push(int a);
            int Length { get; }
        }
        abstract class SD
        {
            protected int[] dane;
            public int Length
            {
                get;
                protected set;
            }
            /*public int Length
            {
                get
                {
                    return dane.Count;
                }
            }*/

            public SD()
            {
                this.Length = 0;
                this.dane = new int[this.Length];
            }
            public void Push(int element)
            {
                this.Length++;
                int[] tmp = this.Przepisz(this.dane);
                tmp[this.Length - 1] = element;
                this.dane = tmp;
            }
            protected int[] Przepisz(int[] stara)
            {
                int[] nowa = new int[stara.Length + 1];
                for (int i = 0; i < stara.Length; i++)
                {
                    nowa[i] = stara[i];
                }
                return nowa;
            }
            protected int[] Zamien(int[] stara)
            {
                int[] nowa = new int[stara.Length - 1];
                for (int i = 0; i < stara.Length; i++)
                {
                    nowa[i] = stara[i + 1];
                }
                return nowa;
            }

            public int this[int index]
            {
                get
                {
                    return this.dane[index];
                }
                set
                {
                    this.dane[index] = value;
                }
            }
        }
        class Kolejka : SD, IAiSD
        {
            public Kolejka()
            {
            }
            public int Pop()
            {
                int[] nowa = new int[dane.Length - 1];
                for (int i = 0; i < nowa.Length; i++)
                {
                    nowa[i] = dane[i + 1];
                }
                dane = nowa;
                return dane[0];
            }

            public new int Length => throw new NotImplementedException();

            public new void Push(int a)
            {
                throw new NotImplementedException();
            }
        }
        class Stos : SD, IAiSD
        {
            public int Pop()
            {
                int[] nowa = new int[dane.Length - 1];
                for (int i = 0; i < nowa.Length; i++)
                {
                    nowa[i] = dane[i];
                }
                dane = nowa;
                return dane[dane.Length];
            }
            public new int Length => throw new NotImplementedException();
            public new void Push(int a)
            {
                throw new NotImplementedException();
            }
        }


        public void Push(int zmienna)
        {
            Węzeł a = new Węzeł(zmienna);
            a.rodzic = ZnajdźRodzica(zmienna);
            if (zmienna % 2 == 0)
            {
                ZnajdźRodzica(zmienna).lewe = a;
            }
            else
                ZnajdźRodzica(zmienna).prawe = a;
        }
        Węzeł Pop(Węzeł korzeń, int wartość)
        {
            if (korzeń == null) return korzeń;

            if (wartość < korzeń.wartość)
                korzeń.lewe = Pop(korzeń.lewe, wartość);
            else if (wartość > korzeń.wartość)
                korzeń.prawe = Pop(korzeń.prawe, wartość);
            else
            {
                if (korzeń.lewe == null)
                    return korzeń.prawe;
                else if (korzeń.prawe == null)
                    return korzeń.lewe;


                korzeń.prawe = Pop(korzeń.prawe, korzeń.wartość);
            }
            return korzeń;
        }


        string ShowPre(Węzeł w)
        {
            if (w == null)
                return "";
            string wynik = "({0}" + w.wartość.ToString();
            wynik += ShowPre(w.lewe);
            wynik += ShowPre(w.prawe);
            ShowPre(w.prawe);
            return wynik;
        }
        string ShowIn(Węzeł w)
        {
            if (w == null)
                return "";
            wynik += ShowIn(w.lewe);
            string wynik = " " + w.wartość.ToString();
            wynik += ShowIn(w.prawe);
            ShowIn(w.prawe);
            return wynik;
        }

        string ShowPost(Węzeł w)
        {
            if (w == null)
                return "";
            wynik += ShowPost(w.lewe);
            wynik += ShowPost(w.prawe);
            string wynik = "{0}" + w.wartość.ToString();
            ShowPost(w.prawe);
            return wynik;
        }

    }
}