D. Четно-нечётная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время своих новогодних каникул Алиса и Боб играют в следующую игру, используя массив $$$a$$$ из $$$n$$$ целых чисел:

  • Игроки ходят по очереди, первой ходит Алиса.
  • Каждый ход игрок выбирает любой элемент и удаляет его из массива.
  • Если Алиса выбрала четное число, то она прибавляет его в свой результат. Если же число было нечетным, результат Алисы не меняется.
  • Аналогично, если Боб выбрал нечетное число, то он прибавляет его в свой результат. Если же число было четным, то результат Боба не меняется.

Если в массиве не осталось чисел, то игра заканчивается. Побеждает тот игрок, результат которого больше. Если результаты игроков равны, то объявляется ничья.

Например, если $$$n = 4$$$ и $$$a = [5, 2, 7, 3]$$$, то игра могла пройти следующим образом (существуют и другие варианты):

  • Первым ходом Алиса выбрала число $$$2$$$ и получила два очка. Ее результат теперь равен $$$2$$$. Массив $$$a$$$ становится равным $$$[5, 7, 3]$$$.
  • Вторым ходом Боб выбрал число $$$5$$$ и получил пять очков. Его результат теперь равен $$$5$$$. Массив $$$a$$$ становится равным $$$[7, 3]$$$.
  • Третьим ходом Алиса выбрала число $$$7$$$ и не получила очков. Ее результат теперь равен $$$2$$$. Массив $$$a$$$ становится равным $$$[3]$$$.
  • Последним ходом Боб выбрал число $$$3$$$ и получил три очка. Его результат теперь равен $$$8$$$. Массив $$$a$$$ становится пустым.
  • Так как у Боба на конец игры больше очков, он объявлется победителем.

Вам интересно, кто победит если оба игрока будут играть оптимально. Обратите внимание, что в массиве могут быть повторяющиеся числа.

Входные данные

В первой строке находится целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора содержится целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$.

В следующей строке находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$, с помощью которого проводится игра.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите:

  • «Alice», если при оптимальной игре выиграет Алиса;
  • «Bob», если при оптимальной игре выиграет Боб;
  • «Tie», если при оптимальной игре будет объявлена ничья.
Пример
Входные данные
4
4
5 2 7 3
3
3 2 1
4
2 2 2 2
2
7 8
Выходные данные
Bob
Tie
Alice
Alice