M. Destiny changes the game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has string $$$s$$$ and Bob has string $$$t$$$, both initially equal to the single-character string "a". There are $$$q$$$ operations. Each operation is one of the following:

  • $$$1$$$ $$$x$$$ $$$k$$$: append the string $$$x$$$ exactly $$$k$$$ times to Alice's string $$$s$$$.
  • $$$2$$$ $$$x$$$ $$$k$$$: append the string $$$x$$$ exactly $$$k$$$ times to Bob's string $$$t$$$.

After each operation, both players may reorder the characters of their current strings to form the lexicographically smallest possible string. They then compare these two strings:

  • If Alice's string is smaller, output "Alice".
  • If Bob's string is smaller, output "Bob".
  • If they are equal, output "Tie".

Both players play optimally at every step. Determine and output the result after each operation.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

Then follow $$$T$$$ test cases. Each test case begins with a line containing a single integer $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$), the number of operations.

Each of the next $$$q$$$ lines has: op x k

where:

  • op is 1 (Alice) or 2 (Bob),
  • x is a non-empty lowercase string $$$( 1 \le |x| \le 4 \cdot 10^5 )$$$,
  • k is an integer $$$(1 \le k \le 2\cdot10^5)$$$.

It is guaranteed that across all test cases, the total length of all appended strings i.e. $$$\sum |x| $$$ does not exceed $$$4\cdot10^5$$$.

Output

For each operation in each test case, print one line:

  • "Alice" if Alice's string is lexicographically smaller,
  • "Bob" if Bob's string is lexicographically smaller,
  • "Tie" if they are equal.
Example
Input
2
3
1 aa 4
2 ab 3
2 aa 4
1
1 a 1
Output
Bob
Alice
Alice
Bob
Note

A string $$$p$$$ is lexicographically smaller than a string $$$q$$$ if :

  • For the first position $$$i$$$ where they differ, $$$p_i \lt q_i$$$, and for all positions before $$$i$$$, $$$p_j = q_j$$$ where $$$j \lt i$$$.
If one string is a prefix of the other (and not identical), the shorter string is smaller.