ADAXMAS - Ada and Christmas

no tags 

Ada the Ladybug was recently unwrapping presents and guess what? She got a new chessboard from her good friend Flea Feodorv. As he though "the bigger chessboard the better the chess game will be", he gave Ada a chessboard even bigger than last time: Now the upper-right corner is [999999999,999999999] (109-1).

As you might guess, she can't play classical (nor rapid) chess on such board. But as she doesn't to throw such valuable (well.. at least big) gift away, she've decided to play Palace Game again. She invited her friend Velvet Mite Vinit. As they played this game recently, they decided to expand the rules a little bit. They have decided to play this game with five most important chess-pieces: Rook, Bishop, King, Knight and obviously, the Palace.

The game rules are simple: A few chess-pieces are placed onto chessboard. Ada and Vinit alternate in moves. In each move one can choose any piece on chessboard and move it toward bottom-left corner. Moving toward means, that the Manhattan distance from bottom-left corner will decrease and also that none of the coordinates of chess-piece will increase. A player who can't make a move will lose. Can you tell who'll be the winner if both of them play optimally? As Ada is a lady, she goes first.

NOTE: Rules are slightly different than in original Palace Game (even though it wouldn't affect the original game, this game might yield slightly different results).


The first line of input will contain 1 ≤ T ≤ 3*105, the number of test-cases.


The next T lines will contain 1 ≤ N ≤ 3*105, the number of chess pieces placed on chessboard.


Each test-case will contain N lines containing two integers and a character: 0 ≤ x, y < 109, the coordinates of chess-piece and c ∈ {T, B, K, N, P} (stands for rook(T), Bishop, King, kNight and Palace).


The sum of N over all test-cases will not exceed 3*105


For each test-case output the name of winner, so either "Ada" or "Vinit".

Example Input

7 0 B
3 4 T
6 7 K
9 1 B
8 7 B
9 4 K
4 4 T
8 5 T
6 5 K
1 2 P
6 1 B
4 4 P
1 2 B
0 9 K
1 9 K
5 0 K
0 4 B
9 1 K
0 4 K
0 5 K
3 2 K
6 4 N
1 2 N
0 7 N

Example Output


hide comments
morass: 2017-12-26 23:36:16

@Michael Kharitonov: Oh, thanx - hopefully fixed now ^_^ Merry XMAS to you too :)

Michael Kharitonov: 2017-12-26 20:41:07

@morass: Now it's Rook in one place and Tower in other :)
Merry XMAS to you and to all SPOJ users!

morass: 2017-12-26 18:00:28

@Michael Kharitonov: Good day to you! Thank you... yes.. I don't know why is this happening.. every time I link a SPOJ problem, SPOJ translates the link (to something which looks like local-link) which doesn't work :/

And yes it is ROOK .. sorry :p

Both shall be fixed now

Thank you so much & Wish you a Nice Day!

Michael Kharitonov: 2017-12-26 17:42:11

The link to "Palace Game" is wrong. It should be "".
And I assume Tower means Rook ?

Last edit: 2017-12-26 17:48:20

Added by:Morass
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)