ADAGAME2 - Ada and Easy Game

Ada the Ladybug is frequently playing board games against her friend Velvet Mite Vinit. Last time, they were playing Game of Digits. Anyway Vinit is slightly mad at Ada, because she "cheated". She let one of her good friends to make program which helped her significantly. As Vinit wants to avoid this, he created Game of Piles with his own rules. He puts many piles with many nuts on the table. He then chooses a few numbers (rules), which are possible moves. Ada and Vinit play alternately (as Vinit is gentleman, Ada starts). In each move one can choose a pile, any number from rules (not greater than the number of nuts in the pile) and eats that many nuts from pile. The one who can't move looses. Vinit is very excited to play since he is ensured Ada can't cheat this time.

Well that was just a fun fact from world of bugs and now lets solve some completely different problem. Your good friend Ada has asked you to help her win a game against one of her friends...

Input

First line of input will consist T ≤ 200 number of test-cases.

Each testcase will begin with two numbers 0 < N ≤ 105 [number of piles] and 0 < M ≤ 30 [number of rules].

The next line will consist of M numbers, 1 ≤ Ri ≤ 105 [rules]

The last line of each test-case will consist of N numbers,1 ≤ Pi ≤ 105 [sizes of pile]

Output

For each test-case, print the name of winner ("Ada" or "Vinit") [if both played optimally].

Example Input

6
4 1
2
1 2 3 4
4 2
1 2
4 4 3 5
1 3
2 3 5
20
2 2
1 3
4 7
5 5
1 2 7 13 15
10 20 30 40 50
1 2
1 2
98997

Example Output

Vinit
Ada
Ada
Ada
Ada
Vinit

Added by:Morass
Date:2016-09-27
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2019-08-14 07:59:37
Getting tle using hash set. someone plz suggest some other method, thnk u in advance.
2017-03-08 17:00:36
@morass nice question and thnx for suggestion
2017-03-08 10:48:23
@jedyn: Hi - I have not tested in java and can't see much through it - but I guess you can make it faster by using "something faster" than hash-set :)

GL & Have Nice Day!
2017-03-08 07:44:01
I am getting tle in java. any help?
2016-09-28 14:01:00
@:D: Yay thank you! I hopefully repaired, but It would need cross-check :P
2016-09-28 13:23:17 :D
I think link to the previous problem is malformed.
2016-09-28 03:52:23
@[Rampage] Blue.Mary: Thank you so much! Updated!
2016-09-28 03:41:38 [Rampage] Blue.Mary
"any number from rules (greater than the number of nuts in the pile) "
should be
"any number from rules (not greater than the number of nuts in the pile) "
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.