XML

В этой задаче вам предстоит определить, соответствует ли предоставленный документ синтаксису языка, напоминающего XML.

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

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

Входные данные

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

Выходные данные

Для каждого документа выведите "valid" в отдельной строке, если документ является допустимым, или "invalid" в противном случае.

Примеры