Validate Trading Card Game Trades

You are given $T$ test cases. Each test case describes a series of trades in a trading card game. Initially, there are $n$ different types of cards, and you are provided with an array of $n$ integers, where the $i^{th}$ integer represents the number of cards of type $i$. Following that, you will perform $m$ trades. Each trade is given by four integers $(a, b, c, d)$, meaning that you trade $c$ cards of type $a$ to receive $d$ cards of type $b$. A trade is valid only if, at the time of the trade, you have at least $c$ cards of type $a$. If any trade is invalid, then the entire test case is marked as "Invalid"; otherwise, it is "Valid".

Your task is to determine for each test case whether the sequence of trades is valid.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer $T$, representing the number of test cases.
• For each test case:
  • The first line contains two integers $n$ and $m$, where $n$ is the number of card types and $m$ is the number of trades.
  • The second line contains $n$ space-separated integers, representing the initial count of each card type.
  • Each of the next $m$ lines contains four space-separated integers: $a$, $b$, $c$, $d$, describing a trade as explained above.

All input is read from stdin.

outputFormat

For each test case, output a single line to standard output (stdout) containing either "Valid" or "Invalid" based on whether the sequence of trades is valid.## sample

3
3 3
5 10 5
1 2 4 3
3 1 2 2
2 3 1 1
2 2
3 5
1 2 4 6
2 1 3 5
2 1
5 5
1 2 2 2

Valid
Invalid
Valid