gistfile1.txt

We’ve built a new communication protocol that sends messages with a restricted syntax. 
We need to write a function which determines whether a given message is syntactically valid or not. 
Here are the rules:

  1. There are 15 valid characters in the protocol: the lower-case characters ‘a’ through ‘j’ 
     and the uppercase characters ‘Z’, ‘M’, ‘K’, ‘P’, and ‘Q’.
  2. Every lower-case character in isolation is a valid message, e.g., ‘a’ is a valid message.
  3. If σ is a valid message then so is Zσ.
  4. If σ and τ are valid messages then so are Mστ , Kστ , Pστ , and Qστ .
  5. All other messages are invalid.

Write a function in the language of your choosing to check whether messages are valid. 
The input consists of a series of potential messages separated by whitespace and containing 
only the 15 characters above.

The output consists of one line per potential messages, followed by ‘VALID’ if the message is valid 
and ‘INVALID’ if it is invalid.

Below is some example output.

Input      Output
Qa Zj      Qa    INVALID
MZca       Zj    VALID
Khfa       MZca  VALID
           Khfa  INVALID