XML

In this problem, you are asked to determine if a given document satisfies the syntax of an XML-like language.

A simple XML-like document can be parsed as a sequence of the following:

By the time the entire document is parsed, the context stack is empty for a valid document. We should also note that the empty string is considered valid.

Input

You will be given a number of documents to process. Each document is given as one line oftext which may be empty. The input is terminated by the end of file.

Output

For each document given, print valid on a single line if it is a valid XML-like document,or invalid otherwise.

Examples