Under construction

Still being built. Things may change

Knight Game

Time limit2sMemory limit1024 MB

Summary
Given a knight on an H by W board, decide whether Alice or Bob wins when both alternately move the knight to unvisited squares.
Level

Hard8 of 10

Topics
Game theory, Graph, Math
Solved
No attempts yet

Problem

The rule of this game is given as follows.

  • There is a knight and a chessboard with HH rows and WW columns. The square at the ii-th row from the top and the jj-th column from the left is called square (i,j)(i, j). Initially, the knight is placed on square (x,y)(x,y).
  • Alice and Bob take turns, starting with Alice. On each turn, the player moves the knight to one of the unvisited squares according to the knight's movement rule.
  • The knight can move from (x_1,y_1)(x\_1,y\_1) to (x_2,y_2)(x\_2, y\_2) if and only if (x_1−x_2)2+(y_1−y_2)2(x\_1 - x\_2)^2 + (y\_1 - y\_2)^2 is 55.
  • The player who cannot move the knight loses.

Assuming both players play optimally, determine whether Alice or Bob wins. Answer for TT test cases.

An unvisited square is defined as follows.

  • A square on the board that the knight has never visited since the start of the game.

Input

TT

case_1\text{case}\_1

⋮\vdots

case_T\text{case}\_T

case_i\text{case}\_i is the ii-th test case.

Each test case is given in the following format.

HH WW xx yy

Output

Output TT lines. On line ii, print the winner of the ii-th test case, Alice or Bob.

Constraints

  • All inputs are integers.
  • 1≤T≤2×1051 \le T \le 2 \times 10^5
  • 1≤H,W≤1091 \le H, W \le 10^9
  • 1≤x≤H1 \le x \le H
  • 1≤y≤W1 \le y \le W

Examples1

  1. Example 1

    Input
    2
    4 4 1 1
    9 17 7 3
    
    Expected output
    Alice
    Bob