### Problem Statement

Imagine a simple input dialog box. The user is supposed to enter a positive integer from a given range into the box.

Recently you realized that sometimes you can tell that the user's input is invalid before he finishes entering the number. For example, if the valid range is 300 to 347, and the user wants to enter the number 372, as soon as he types "37" you can be sure that his input won't be valid.

More precisely, we call a number valid if it is a prefix of some number in the given range, and invalid otherwise.

You are given two ints smallest and largest (denoting the range of valid inputs), and a int[] numbers. The range of valid inputs contains all integers between smallest and largest, inclusive.

Write a method that will determine for each number in numbers whether it represents a valid input for the given range. Return a String[] that has the same number of elements as numbers. If the i-th element of numbers represents a valid input, the i-th element of the return value has to be "VALID", otherwise it has to be "INVALID" (quotes for clarity only).

### Definition

 Class: InputBoxChecker Method: checkPrefix Parameters: int, int, int[] Returns: String[] Method signature: String[] checkPrefix(int smallest, int largest, int[] numbers) (be sure your method is public)

### Constraints

-smallest is between 1 and 2,000,000,000, inclusive.
-largest is between 1 and 2,000,000,000, inclusive.
-smallest is less than or equal to largest.
-numbers contains between 1 and 50 elements, inclusive.
-Each element in numbers is between 1 and 2,000,000,000, inclusive.

### Examples

0)

 `300` `347` `{37}`
`Returns: {"INVALID" }`
 This is the example from the problem statement.
1)

 `310` `320` `{3, 31, 317, 3174, 310, 320}`
`Returns: {"VALID", "VALID", "VALID", "INVALID", "VALID", "VALID" }`
 Please note that smallest and largest represent an inclusive range.
2)

 `600` `1020` `{7, 73, 734, 7349}`
`Returns: {"VALID", "VALID", "VALID", "INVALID" }`
3)

 `64` `78` `{1,2,3,4,5,6,7,8,9}`
```Returns:
{"INVALID",
"INVALID",
"INVALID",
"INVALID",
"INVALID",
"VALID",
"VALID",
"INVALID",
"INVALID" }```
4)

 `1` `1234567890` `{123, 456, 789, 1234567, 7654321, 3245354, 325432532, 243212}`
`Returns: {"VALID", "VALID", "VALID", "VALID", "VALID", "VALID", "VALID", "VALID" }`
 Watch out for the time limit.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6542

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9990&pm=6542

misof

#### Testers:

PabloGilberto , brett1479 , Olexiy , marian

#### Problem categories:

Greedy, Simple Math