XML Validator

Professor Dasom Lee, who teaches Internet Programming, believes that XML is the revolutionary language that will change the world and constantly promotes its benefits to students. But because misusing it can cause serious trouble, a parser is needed to decide whether a document's syntax is correct. Since Professor Lee cannot write XML, you must implement the validator instead.

A document is judged valid by the following rules. A document is read as a sequence of the elements below; if at any position a part does not match one of these rules, the whole document is invalid.

1. Plain text: characters whose ASCII code is between 32 and 127 inclusive. The three characters <, >, and & may not appear as plain text.
2. Escape strings: the following strings encode <, >, and & respectively and are valid.
   • < → <
   • > → >
   • & → &
3. Hex escape: a string of the form &xHEX;, where HEX is a hexadecimal string with a positive, even number of digits, made up of 0~9 or the letters A~F (both uppercase and lowercase allowed).
4. Opening tag <tag>: tag must be a non-empty string of lowercase letters or digits. This tag name is pushed onto the context stack.
5. Self-closing tag <tag/>: this tag is not pushed onto the context stack.
6. Closing tag </tag>: pops the top value of the context stack. The tag name on top of the stack must match this tag's name.

After the entire document is parsed, the context stack must be empty. An empty string is also judged valid.

Several lines are given as input. For each line, decide whether it is valid XML syntax. Each line consists only of characters with ASCII code between 32 and 127, and empty lines may appear. Input ends at end of file (EOF).

For each line, print valid if the line is valid XML syntax, and invalid otherwise.