B. Игра с удалением
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса получила перестановку $$$a_1, a_2, \ldots, a_n$$$ чисел $$$[1,2,\ldots,n]$$$, а Боб — другую перестановку $$$b_1, b_2, \ldots, b_n$$$ чисел $$$[1,2,\ldots,n]$$$. Они собираются сыграть в игру с этими массивами.

На каждом ходу игры происходят следующие события по порядку:

  • Алиса выбирает первый или последний элемент своего массива и удаляет его из массива;
  • Боб выбирает первый или последний элемент своего массива и удаляет его из массива.

Игра продолжается в течение $$$n-1$$$ ходов, после чего в обоих массивах останется ровно по одному элементу: $$$x$$$ в массиве $$$a$$$ и $$$y$$$ в массиве $$$b$$$.

Если $$$x=y$$$, выигрывает Боб, в противном случае — Алиса. Найдите, кто из игроков выиграет, если оба игрока играют оптимально.

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

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

В первой строке каждого набора входных данных дано целое число $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$, все $$$a_i$$$ различны) — перестановка Алисы.

Следующая строка содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_i\le n$$$, все $$$b_i$$$ различны) — перестановка Боба.

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

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

Для каждого набора входных данных выведите в единственной строке имя победителя, предполагая, что оба игрока играют оптимально. Если выигрывает Алиса, выведите $$$\texttt{Alice}$$$; в противном случае выведите $$$\texttt{Bob}$$$.

Пример
Входные данные
2
2
1 2
1 2
3
1 2 3
2 3 1
Выходные данные
Bob
Alice
Примечание

В первом наборе входных данных Боб может выиграть, удаляя те же элементы, что и Алиса.

Во втором наборе входных данных Алиса может удалить $$$3$$$ на первом ходу, а затем на втором ходу удалить элемент, который отличается от того, что Боб удалил на первом ходу, чтобы выиграть игру.