Ця задача повністю включає в себе попередню задачу «Дерева (вставка, пошук)». Тому, в разі виникнення проблем із розв'язуванням цієї задачі, рекомендується спочатку зробити попередню, а також прочитати примітку наприкінці умови цієї задачі.

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

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

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

Для кожного запиту «DELETE n» слід виконати такі дії: якщо вказане число є в дереві, вилучити його з дерева і вивести на екран слово «DONE», якщо нема – залишати дерево як було і виводити на екран слово «CANNOT». При видаленні елемента, що має обох синів, обов'язково обмінювати значення з максимальним елементом лівого піддерева.

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

Вхідні дані

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

Результати

Для кожного запиту виводити відповідь на нього. Для запитів ADD, SEARCH та DELETE – відповідне слово в окремому рядку (великими латинськими буквами, без лапок). На запит 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 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 1
PRINTTREE
DELETE 7
PRINTTREE

Результат

DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.1
2
..5
.7
DONE
.1
2
.5

Примітки

1. Враховувати вищезгадану фразу «При видаленні елемента, що має обох синів, обов'язково обмінювати значення з максимальним елементом лівого піддерева», на жаль, абсолютно необхідно для зарахування розв'язку. Попри те, що це взагалі-то не є об'єктивно необхідним для непротирічивості дерева (цей спосіб правильний, але є й інші правильні способи). Однак, у цій задачі все-таки необхідно застосувати саме конкретно цей спосіб, бо конкретно в ній визначення правильності Вашої програми робиться просто порівнянням її відповіді зі зразком (без глибшого аналізу смислу), і це переписуватися не буде. Кому це не подобається – може просто не робити цю задачу.

2. Одна з відносно частих помилок при виконанні цієї задачі – написаний студентом код помилково виводить два повідомлення YES замість одного при успішному видаленні елемента, що має обох синів. Переконайтеся, що у Вашого коду нема конкретно цієї проблеми.