Validate a Calendar Date

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given integer day, month, and year in the Gregorian calendar, validate the month and the day within the actual month length. Negative months, month 0, and months greater than 12 are invalid.

Input

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

Output

Print VALID or INVALID as appropriate.

Subtasks

• Subtask 1 (20 points): Month is one of the 31-day months, -1000 <= d <= 1000, 1 <= y <= 9999.

• Subtask 2 (30 points): Month is any valid non-February month, -1000 <= d <= 1000, 1 <= y <= 9999.

• Subtask 3 (50 points): -1000 <= d,m <= 1000, 1 <= y <= 9999.

Examples

Example 1

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 29 exists.

Example 2

Input

31 4 2024

Output

INVALID

Explanation

For this input, the case-specific computation and the required exact output are shown above. April has only 30 days, so April 31 is invalid.