Is this coupon valid?

Problem

A store has a list of valid coupon codes. Customers type some codes at checkout. For each typed code say whether it is on the valid list.

Input: The first line has m, then one line with m valid codes. Then a line with q, then one line with q typed codes.
Output: One line per typed code: VALID or INVALID.
Constraints: 1 ≤ m, q ≤ 10^5

Example

Input

3
SAVE10 NEW20 FREE5
3
NEW20 SAVE15 SAVE10

Output

VALID
INVALID
VALID

SAVE15 is not on the list.

Try the problem first. Open one hint at a time.

Hint 1

Put the valid codes in a HashSet.

Hint 2

contains answers each query without scanning the list.

Write your Java code, run it on the examples and submit it to hidden tests.