A valid street name is a string of words (word: a sequence of consecutive non-space characters) satisfying the following:

• The first word is an integer between 1 and 9999 without leading zero.
• All subsequent words consist of English letters only.
• For all subsequent words:
• The first letter of the word must be uppercase.
• All remaining letters of the word must be lowercase.
• The last word must be Street only.
• There should be at least one word between the number and Street.

We guarantee the input consists of English letters and numbers only. Each word will be separated by exactly one space and there are no leading/trailing spaces.

Determine if the given string is a valid street name.

Input

The only line of input contains a string (non-empty, at most 100 characters).

Output

Output Valid if the string is a valid street name, otherwise output Invalid.