Напишіть програму, яка реалізовуватиме у бінарному дереві пошуку дії «вставити» та «знайти» (за значенням). Програма повинна виконувати послідовність запитів вигляду «ADD n», «SEARCH n», та «PRINTTREE», де n – натуральне число.

Для кожного запиту «ADD n» слід виконати такі дії: якщо вказаного числа ще нема в дереві, вставити у дерево і вивести на екран слово «DONE», якщо вже є – залишати дерево як було (не вставляти додаткову копію) і виводити на екран слово «ALREADY».

Для кожного запиту «SEARCH n» слід виводити на екран слово «YES» (якщо значення знайдене у дереві) або слово «NO» (якщо не знайдене); при виконанні запитів SEARCH дерево не змінюється.

Для кожного запиту «PRINTTREE» слід виводити на екран усе дерево, обов'язково дотримуючись того ж формату, що й наведений далі алгоритм.

Вхідні дані

В кожному рядку вхідних даних записаний один із запитів «ADD n», або «SEARCH n», або «PRINTTREE» (без лапок; слова записані великими латинськими буквами; для запитів ADD та SEARCH число відділене від слова одинарним пробілом і перебуває в межах від 1 до 1234567890). Гарантується, що запити PRINTTREE будуть лише у моменти, коли дерево не порожнє. Загальна кількість запитів не перевищує 1000, з них не більше 20 запитів PRINTTREE.

Результати

Для кожного запиту виводити відповідь на нього. Для запитів ADD та SEARCH – відповідне слово в окремому рядку (великими латинськими буквами, без лапок). На запит PRINTTREE треба виводити дерево, обов'язково відповідно до такого алгоритму:

public void PrintTree(Node root, int level)
{
    if (root == null)
        return;
    PrintTree(root.left, level + 1);
    Console.WriteLine(new String('.', level) + root.Data);
    PrintTree(root.right, level + 1);
}

(Початковий виклик цього методу – PrintTree(root, 0). Якщо описати цей алгоритм словами, вийде приблизно так: слід виводити спочатку ліве піддерево, потім корінь, потім праве піддерево, і результат виходить впорядкованим згори донизу так, як при класичному зображенні мав би бути впорядкований зліва направо; перед кожним елементом треба виводити стільки крапочок, який це ярус, вважаючи, що корінь є єдиним елементом ярусу 0 (слід взагалі не ставити крапочок), сини кореня є елементами ярусу 1 (слід поставити рівно одну крапочку), «онуки» (сини синів) кореня є елементами ярусу 2 (слід поставити рівно дві крапочки), і так далі.)

Приклади

Вхід

ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7

Результат

DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO

Примітки

Детальніше пояснимо приклад:

DONE – у відповідь на ADD 2

DONE – у відповідь на ADD 3

ALREADY – у відповідь на ADD 2

YES – у відповідь на SEARCH 2

DONE – у відповідь на ADD 5

2 – цим рядком починається відповідь на PRINTTREE

.3

..5 – а цим рядком та сама відповідь на той самий PRINTTREE закінчується

NO – у відповідь на SEARCH 7