Hectic Game
Tag(s):

## Algorithms, Bit manipulation, Easy, Greedy algorithm, Hash function

Problem
Editorial
Analytics

Alice and Bob are playing a hectic game in which there are a total of $N$ tasks each consisting of a start time $S_i$ and end time $E_i$.

Both players take alternate turns, Alice plays first. In each turn, a player chooses the maximum number of tasks that are non-overlapping as both Alice and Bob can perform only one task at a time. In the next turn, the other player will choose the maximum number of tasks that are non-overlapping from the remaining tasks and so on.

Now, both the players will take XOR (Exclusive - OR) of the total tasks count value obtained in each of their turns. Let the value be $A$ for Alice and $B$ for Bob. Now, If $A \gt B$, Alice wins. If $B \gt A$, Bob wins. If $A = B$, it's a tie. Find out the winner?

Note: The ending time $E_i$ for each selected task in each turn should be as less as possible, e.i. if the given tasks are $[1\;5]$, $[3\;8]$, $[6\;10]$, $[9\;15]$, Alice can choose maximum 2 tasks in 3 ways as $[1\;5]$, $[6\;10]$ or $[1\;5]$, $[9\;15]$ or $[3\;8]$, $[9\;15]$. Alice will choose $[1\;5]$, $[6\;10]$ as the ending time for each selected task is as less as possible in this case.

Input Format

The first line of the input will be $T$, the total number of test cases.

The first line of each test case will be $N$, the total number of tasks.

Then $N$ lines follow each consisting of two space-separated integers $S_i$ and $E_i$ the start time and the end time.

Output Format

For each test case print the respective result Alice, Bob or Tie.

Constraints

$1 \le T \le 10$

$1 \le N \le 10^3$

$1 \le S_i \le E_i \le 10^9$

SAMPLE INPUT
1
5
1 2
1 3
4 5
3 4
1 5

SAMPLE OUTPUT
Alice

Explanation

Initially, there are maximum 2 tasks Alice can choose i.e. $[1\;2]$ and $[3\;4]$. From the remaining tasks, Bob can choose maximum 2 tasks i.e. $[1\;3]$ and $[4\;5]$. Now, Alice chooses the 1 last task i.e. $[1\;5]$.

$A$ = 2 ^ 1 = 3

$B$ = 2

$A > B$ thus, Alice wins.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

QuEST Global Coding Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays