Is the ticket valid?

Problem

A help desk has a list of valid ticket ids. When a customer quotes a ticket id, check whether it is on the list.

Print Valid or Invalid.

Input: The first line holds the valid ids separated by spaces. The second line holds the quoted id.
Output: Valid if the id is on the list, otherwise Invalid.
Constraints: 1 ≤ number of valid ids ≤ 10000

Example 1

Input

T100 T101 T102
T101

Output

Valid

On the list.

Example 2

Input

T100 T101 T102
T999

Output

Invalid

Not on the list.

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

Hint 1

Checking membership in a set is fast.

Hint 2

Make a set of the valid ids and test the quoted id with in.

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