XML

У цьому завданні вам потрібно визначити, чи відповідає наданий документ синтаксису мови, що нагадує XML.

Документ, схожий на XML, можна розібрати як послідовність наступних елементів:

Для того, щоб документ вважався допустимим, після його повного розбору стек контексту повинен бути порожнім. Також важливо зазначити, що порожній рядок вважається допустимим.

Вхідні дані

Вам буде надано кілька документів для аналізу. Кожен документ представлений одним рядком тексту, який може бути порожнім. Введення завершується кінцем файлу.

Вихідні дані

Для кожного документа виведіть "valid" в окремому рядку, якщо документ є допустимим, або "invalid" в протилежному випадку.

Приклади