Problem Description

Validate a string containing brackets (), [], {} and asterisks (*). An asterisk can act as any type of opening or closing bracket, or be ignored. Determine if the string can be made valid by appropriately assigning roles to asterisks.

Input Format

A single string containing brackets and asterisks.

Output Format

Return "VALID" if the string can be made valid, "INVALID" otherwise.

Constraints

• 1 ≤ string length ≤ 1000

• String contains only (, ), [, ], {, }, and *

• * can be (, ), [, ], {, }, or ignored

• Brackets must be properly nested and matched

• Different bracket types cannot cross-match

Sample Input/Output

(*)

VALID

Explanation

The string "(*)" can be made valid by treating * as ) to get "()" which is valid. Alternatively, * could be ignored to get "(" which is invalid, but since one assignment works, the answer is VALID.