In Shane's neighbourhood, there are ~N~ streets, and Halloween is celebrated by every house on each street. As part of the spooky season, each house only gives out one type of candy, and the candy given out by all houses follow a unique rule: the tastiness of any candy given out is a power of ~2~.

Shane's friend, Aaron, tells him to visit every house on each street from left to right, and keep the candies he has recieved in a list. Aaron also informs Shane that at any given house on street ~i~, the following will occur:

1. If the last ~2~ candies recieved from street ~i~ in Shane's list are of the same tastiness, say ~2^y~, Shane can exchange those two candies and recieve a new candy of tastiness ~2^{y+1}~. Shane can repeat this exchange as many times as he likes at any given house.

2. Shane will recieve a candy of tastiness ~2^x~.

Note that when an exchange is made, the two candies exchanged are removed from the list, while the candy recieved is added.

Aaron then proceeds to tell Shane that he managed to obtain a certain sequence of candies from each street, following the above rules, and challenges Shane to do the same. However, knowing that Aaron is a massive troll, Shane wonders if he is being truthful about every sequence. In addition, Shane needs to leave to go trick-or-treating with his girlfriend soon, as he told her dad "I'll have her home by 10".

Can you help Shane figure out which sequences Aaron is being truthful about?

Constraints

~1 \le N \le 10^3~

~1 \le M_i \le 10^3~, the number of houses on street ~i~.

~1 \le A_i \le 10^3~, the number of candies in Aaron's claimed sequence from street ~i~.

~0 \le x_j \le 10^3~, where ~2^{x_j}~ is the tastiness of the candy from house ~j~ on street ~i~.

~0 \le a_k \le 10^3~, where ~2^{a_k}~ is the tastiness of the ~k~th candy in Aaron's claimed sequence from street ~i~.

Subtask 1 [20%]

~0 \le x_j, a_k \le 30~

Subtask 2 [80%]

No Further Constraints.

Input Specification

The first line of input will contain ~N~.

The next ~3N~ lines of input will contain the following repeated ~3~ lines:

• ~2~ integers, ~M_i~ and ~A_i~,
• ~M_i~ integers, with ~x_j~ representing the exponent of the tastiness of a candy from house ~j~ on street ~i~,
• ~A_i~ integers, with ~a_k~ representing the exponent of the tastiness of the ~k~th candy in Aaron's claimed sequence from street ~i~.

Ouput Specification

For each street, print VALID if Shane can exchange his way to the sequence of candies Aaron claims to have, and print INVALID otherwise.

Sample Input

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

Sample Output

VALID
VALID
INVALID
VALID
INVALID
VALID

Sample Explanation

Explanations labelled by street number.

1. No exchanges are needed, as Aaron's sequence is identical to the candies given out by houses on street ~1~.

2. Shane can exchange the candies recieved from houses ~1~ and ~2~ (both of tastiness ~2^1~) at house ~3~ for a candy of tastiness ~2^2~.

3. At no house can Shane exchange ~2~ candies of equal tastiness for the first candy in Aaron's sequence.

4. Shane can exchange the candies recieved from houses ~3~ and ~4~ (both of tastiness ~2^3~) at house ~5~ for a candy of tastiness ~2^4~.

5. At no house can Shane exchange ~2~ candies of equal tastiness for the fourth candy in Aaron's sequence.

6. Shane can exchange the candies recieved from houses ~2~ and ~3~ (both of tastiness ~2^1~) at house ~4~ for a candy of tastiness ~2^2~, then exchange that and the candy from house ~1~ (both of tastiness ~2^2~) for a candy of tastiness ~2^3~; Shane's list after visiting house ~4~: 3 3. At house ~5~, Shane can exchange the candy recieved from the last exchange and the candy recieved from house ~4~ (both of tastiness ~2^3~) for a candy of tastiness ~2^4~; Shane's list after visiting house ~5~: 4 4. Finally, at the ~6~th house, Shane can exchange that candy and the one recieved from house ~5~ (both of tastiness ~2^4~) for a candy of tastiness ~2^5~; Shane's list after visiting house ~6~: 5 1.