using System;
using System.Collections.Generic;

namespace Clones
{
	public class StackItem<T>
	{
		public T Value;
		public StackItem<T> Previous;
	}
	public class StackClone<T>
{
		public StackItem<T> Tail;
		public int Count;
		public void Push(T item)
		{
			var stackItem = new StackItem<T> { Value = item };
			if (Count == 0)
			{
				stackItem.Previous = null;
				Tail = stackItem;
				Count++;
				return;
			}

			stackItem.Previous = Tail;
			Tail = stackItem;
			Count++;
		}

		public T Pop()
		{
			var item = Tail;
			if (Count == 0)
			{
				Tail = null;
				return item.Value;
			}
			Tail = Tail.Previous;
			Count--;
			return item.Value;
		}
	}
	public class Clon
	{
		public StackClone<string> izucheniecomand = new StackClone<string>();
		public StackClone<string> otcati = new StackClone<string>();
	}
	public class CloneVersionSystem : ICloneVersionSystem
	{
		public Dictionary<string, Clon> dictionary = new Dictionary<string, Clon>() { { "1", new Clon() } };

		public string Execute(string query)
		{
			var array = query.Split(' ');
			if (!(dictionary.ContainsKey(array[1])))
				return null;
			switch (array[0])
			{
				case "learn":
					dictionary[array[1]].izucheniecomand.Push(array[2]);
					dictionary[array[1]].otcati = new StackClone<string>();
					break;

				case "rollback":
					var programmClone = dictionary[array[1]].izucheniecomand.Pop();
					dictionary[array[1]].otcati.Push(programmClone);
					break;

				case "clone":
					dictionary.Add((int.Parse(array[1]) + 1).ToString(), new Clon());
					dictionary[(int.Parse(array[1]) + 1).ToString()].izucheniecomand.Tail = dictionary[array[1]].izucheniecomand.Tail;
					dictionary[(int.Parse(array[1]) + 1).ToString()].otcati.Tail = dictionary[array[1]].otcati.Tail;
					break;

				case "check":
					if (dictionary[array[1]].izucheniecomand.Tail == null) return "basic";
					else return dictionary[array[1]].izucheniecomand.Tail.Value;

				case "relearn":
					var programmClone1 = dictionary[array[1]].otcati.Pop();
					dictionary[array[1]].izucheniecomand.Push(programmClone1);
					break;
			}

			return null;
		}
	}
}