Valid Calendar Date in a Month

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given a day $d$, month $m$, and year $y$ in the Gregorian calendar, determine if this date exists. The curriculum catalog title mentions day ordinal, but the specified output is date validity, not a day-of-year index.

Input

One line contains three integers d,m,y in that order.

Output

Print VALID or INVALID as appropriate.

Subtasks

• Subtask 1 (20 points): All values are between 1 and 9999, and month is a 31-day month.

• Subtask 2 (30 points): All values are between 1 and 9999; month is a valid non-February month.

• Subtask 3 (50 points): All values are between 1 and 9999.

Examples

Example 1

Input

29 2 1900

Output

INVALID

Explanation

For this input, the case-specific computation and the required exact output are shown above. The year 1900 is divisible by 100 but not by 400, so February has 28 days; day 29 is invalid.

Example 2

Input

29 2 2000

Output

VALID

Explanation

For this input, the case-specific computation and the required exact output are shown above. The year 2000 is divisible by 400, so February has 29 days; day 29 is valid.