Game on a Grid

All submissions for this problem are available.
Alice and Bob are playing a game. A single pawn is placed on a grid. The grid consists of cells (X, Y) for nonnegative integers X and Y. Some cells of the grid have been marked as impassable. A move consists of choosing some positive integer D and moving the pawn from (X, Y) either to (X − D, Y) or to (X, Y − D), of course, if this cell belongs to the grid. In other words, we move the pawn a positive number of steps along the row or column towards the origin. The pawn is not allowed to land on nor pass through an impassable cell. Alice and Bob alternate moves, with Alice going first. The first player unable to make a move loses.
Alice and Bob will play several games on the same grid, but with different starting positions of the pawn. Assuming both players play optimally, determine which player will win each game.
Input
Input will begin with an integer T, the number of test cases that follow. Each test case will begin with an integer N, the number of impassable cells. N lines follow with 2 integers each: the X and Y coordinates of an impassable cell. Following this is a line with an integer Q, the number of games to be played on this grid. Q lines follow with 2 integers each: the X and Y coordinates of the pawn.
Output
For each test case, print the winner of each of the Q games, one per line.
Constraints
 1 ≤ T ≤ 10000 (10^{4})
 1 ≤ N ≤ 100000 (10^{5})
 1 ≤ Q ≤ 100000 (10^{5})
 The sum of N over all test cases will not exceed 100000 (10^{5})
 The sum of Q over all test cases will not exceed 100000 (10^{5})
 All coordinate values will be between 0 and 1000000000 (10^{9}), inclusive
 All impassable cells will be distinct
 No starting position of the pawn will be impassable
Sample Input
1 2 1 1 4 2 4 2 2 1 2 3 4 6 5
Sample Output
Alice Bob Alice Bob
Explanation
In the first game, the pawn is at cell (2, 2). In order to win Alice can begin by moving the pawn to (1, 2). Bob's only available move is to (0, 2) since (1, 1) is impassable. Alice then moves the pawn to (0, 0), leaving Bob with no available moves.
Here is the small portion of the table of winning and losing positions. Here Xdirection goes from the left to the right and Ydirection goes from the top to the bottom. Letter 'A' at the cell (X, Y) means that Alice will win when (X, Y) is the starting position of the pawn and 'B' means that Bob will win. We use different background color for Alice and Bob cells for convenience. Impassable cells have black background color.
0  1  2  3  4  5  6  
0  B  A  A  A  A  A  A 
1  A  B  A  A  A  A  
2  A  B  A  A  B  A  
3  A  A  A  B  A  A  A 
4  A  A  A  A  B  A  A 
5  A  A  A  A  A  A  B 
Author:  pieguy 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/GRIDGAME 
Tags  cook29, game, mediumhard, pieguy 
Date Added:  22112012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions