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

namespace BST
{
    class Program
    {
        public static int cmp(string s1, string s2)
        {
            int d1 = 0, d2 = 0;

            int i = 0;
            while (i != 101)
            {
                if (i == s1.Length)
                    break;
                if (s1[i] == ',')
                    break;
                d1++;
                i++;
            }

            i = 0;
            while (i != 101)
            {
                if (i == s2.Length)
                    break;
                if (s2[i] == ',')
                    break;
                d2++;
                i++;
            }

            if (d1 < d2)
                return -1;

            if (d2 < d1)
                return 1;
            if (d1 == d2)
            {
                int size = s1.Length;
                int size1 = s2.Length;
                if (size > size1)
                {
                    for (int j = 0; j < size1; j++)
                    {
                        if (s1[j] < s2[j])
                            return -1;
                        if (s2[j] < s1[j])
                            return 1;
                    }
                }
                else
                for (int j = 0; j < size; j++)
                {
                    if (s1[j] < s2[j])
                        return -1;
                    if (s2[j] < s1[j])
                        return 1;
                }
            }

            return 0;
        }
        public static int cmp1(string s1, string s2)
        {
            int d1 = 0, d2 = 0;

            int i = 0;
            while (i != 101)
            {
                if (i == s1.Length)
                    break;
                if (s1[i] == ',')
                    break;
                d1++;
                i++;
            }

            i = 0;
            while (i != 101)
            {
                if (i == s2.Length)
                    break;
                if (s2[i] == ',')
                    break;
                d2++;
                i++;
            }

            if (d1 < d2)
                return -1;

            if (d2 < d1)
                return 1;
            if (d1 == d2)
            {
                for (int j = 0; j < d1; j++)
                {
                    if (s1[j] < s2[j])
                        return -1;
                    if (s2[j] < s1[j])
                        return 1;
                    else
                        return 0;
                }
            }
            return 0;

        }
        public class Drzewo
        {

            public Node korzen;
            private int poziom=0;
            public Drzewo()
            {
                korzen = null;
            }

            public Drzewo(string wartosc)
            {
                korzen = new Node(wartosc);
            }
            public void W(string wartosc)
            {

                if (korzen == null)
                {
                    Node nowy = new Node(wartosc);
                    korzen = nowy;
                    return;
                }
                else
                {
                    Node obecny = korzen;
                    bool dodany = false;
                    do
                    {
                        if(cmp(wartosc, obecny.wartosc) == 0)
                        {
                            dodany = true;
                        }
                         else if (cmp(wartosc, obecny.wartosc) < 0)
                             {
                            if (obecny.lewy == null)
                            {
                                Node nowy = new Node(wartosc);
                                obecny.lewy = nowy;
                                dodany = true;
                            }
                            else
                            {
                                obecny = obecny.lewy;
                                poziom++;
                            }
                              }
                        else if (cmp(wartosc, obecny.wartosc) > 0)
                        {
                            if (obecny.prawy == null)
                            {
                                Node nowy = new Node(wartosc);
                                obecny.prawy = nowy;
                                dodany = true;
                            }
                            else
                            {
                                obecny = obecny.prawy;
                                poziom++;
                            }
                        }
                    } while (!dodany);
                }
            }
            public void S(string wartosc)
            {
                Node obecny = korzen;
              while(true)
                {
                    if (obecny == null)
                    {
                        Console.WriteLine("NIE");
                        break;
                    }
                    if (cmp(wartosc, obecny.wartosc) == 0)
                    {
                        Console.WriteLine("TAK");
                        break;
                    }
                    else if (cmp(wartosc, obecny.wartosc) < 0)
                    {
                        obecny = obecny.lewy;
                    }
                    else if (cmp(wartosc, obecny.wartosc) > 0)
                    {
                        obecny = obecny.prawy;
                    }
                }
            }

    public void U(string wartosc)
            {
                    Node obecny = korzen;
                    Node pom = obecny;
                while (true)
                {
                    if (obecny == null)
                    {
                        break;
                    }
                    if (cmp(wartosc, obecny.wartosc) == 0)
                    {
                        if (obecny.lewy == null && obecny.prawy == null)
                        {
                            obecny.wartosc = null;
                            break;
                        }
                        else if (obecny.lewy == null && obecny.prawy != null)
                        {
                            obecny.wartosc = obecny.prawy.wartosc;
                        }
                        else if (obecny.lewy != null && obecny.prawy == null)
                        {
                            obecny.wartosc = obecny.lewy.wartosc;
                        }

                        else if (obecny.lewy != null && obecny.prawy != null)
                        {
                            pom = obecny;
                            obecny = obecny.prawy;
                            while (obecny.lewy != null)
                            {
                                obecny = obecny.lewy;
                                pom = obecny;
                                if (obecny.prawy == null)
                                {
                                    obecny = null;
                                }
                                else
                                {
                                    obecny = obecny.prawy;
                                }
                                korzen = pom;
                            }
                        }

                        else if (cmp(wartosc, obecny.wartosc) < 0)
                        {
                            obecny = obecny.lewy;
                        }
                        else if (cmp(wartosc, obecny.wartosc) > 0)
                        {
                            obecny = obecny.prawy;
                        }
                        }
                }
            }
            public int L(Node korzen,string wartosc)
            {
                Node obecny = korzen;

                int licznik = 0;

                    if (obecny == null)
                    {
                        Console.WriteLine("BRAK WYNIKÓW");
                    }
                    if (cmp1(wartosc, obecny.wartosc) == 0 && obecny.lewy!=null && obecny.prawy!=null )
                    {
                        return L(obecny.lewy,wartosc)+ L(obecny.prawy, wartosc)+1;
                    }
                    else if (cmp1(wartosc, obecny.wartosc) < 0)
                    {
                        obecny = obecny.lewy;
                    }
                    else if (cmp1(wartosc, obecny.wartosc) > 0)
                    {
                        obecny = obecny.prawy;
                    }


                return licznik;

            }
        }
        public class Node
        {
            public string wartosc;
            public Node lewy;
            public Node prawy;
            public Node(string wartosc, Node lewy, Node prawy)
            {
                this.wartosc = wartosc;
                this.lewy = lewy;
                this.prawy = prawy;
            }
            public Node(string wartosc)
            {
                this.wartosc = wartosc;
                this.lewy = null;
                this.prawy = null;
            }
        }
        static void Main(string[] args)
        {

            Drzewo d = new Drzewo();

            int n,i;
            string f, s;

            StreamReader reader = new StreamReader("plik.txt");
            string linia = reader.ReadLine();
            n = int.Parse(linia);
            for (i = 0; i < n; i++)
            {
                if (reader.EndOfStream) break;
                else
                {
                    string linijka = reader.ReadLine();
                    string[] oddzielone = linijka.Split(null);
                    f = oddzielone[0];
                    s = oddzielone[1];
                    if (cmp(f, "W") == 0)
                    {
                        d.W(s);

                    }
                    else if (cmp(f, "S") == 0)
                    {
                        d.S(s);

                    }
                    else if (cmp(f, "U") == 0)
                    {
                        d.U(s);

                    }
                    else if (cmp(f, "L") == 0)
                    {
                        d.L(d.korzen,s);

                    }
                }

           }
            Console.ReadKey();
        }
    }
}