Validate Lexicographically Sorted Messages

You are given a series of messages. Each message is a string consisting of space‐separated words. For each message, you must validate it according to the following rules:

• Each word must consist solely of lowercase English letters (a–z).
• No word should appear more than once in the message.
• The words in the message must be in lexicographical (dictionary) order.

An empty message (i.e. a message with no words) is considered valid.

Your task is to read the messages from stdin, validate each one, and output either VALID or INVALID for every message on a separate line.

inputFormat

The first line contains an integer n — the number of messages. Each of the following n lines contains a message. A message is a string that might be empty or contain several words separated by spaces.

outputFormat

Output exactly n lines. For each message, print VALID if the message satisfies the following criteria:

• Every word is composed only of lowercase alphabetic characters.
• No word is repeated.
• The words are sorted in lexicographical order.

Otherwise, output INVALID.

1
a b c d

VALID