Validate Device Communication Messages

You are given a list of unique device identifiers and several messages transmitted between these devices. Each message is in the format sender-code-receiver where sender and receiver are device identifiers and code is an arbitrary string. Your task is to check whether both the sender and receiver exist in the provided device list. A message is considered valid if both sender and receiver are present; otherwise, it is invalid.

Input Format:

• The first line contains two integers \(n\) and \(m\), which denote the number of devices and the number of messages respectively.
• The second line contains \(n\) space-separated integers representing the device identifiers.
• The third line contains \(m\) space-separated strings representing the messages in the format sender-code-receiver.

Output Format:

• Output \(m\) lines. Each line should contain either Valid or Invalid corresponding to the validity of each message in the order they were given.

Note: All device identifiers are integers. The problem requires that you parse the messages and validate the sender and receiver against the provided list of device identifiers.

inputFormat

The input is read from standard input and consists of three lines:

1. The first line contains two integers \(n\) and \(m\), separated by a space.
2. The second line contains \(n\) space-separated integers representing device identifiers.
3. The third line contains \(m\) space-separated strings, each string being a message in the format sender-code-receiver.

outputFormat

Print exactly \(m\) lines to standard output. Each line should display Valid if the corresponding message is valid, or Invalid if it is not.

## sample

3 3
101 202 303
101-xyz-202 202-abc-101 404-def-303

Valid
Valid
Invalid

</p>