Алиса получила перестановку \(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\), выигрывает Боб, в противном случае — Алиса. Найдите, кто из игроков выиграет, если оба игрока играют оптимально.
Выходные данные
Для каждого набора входных данных выведите в единственной строке имя победителя, предполагая, что оба игрока играют оптимально. Если выигрывает Алиса, выведите \(\texttt{Alice}\); в противном случае выведите \(\texttt{Bob}\).
Примечание
В первом наборе входных данных Боб может выиграть, удаляя те же элементы, что и Алиса.
Во втором наборе входных данных Алиса может удалить \(3\) на первом ходу, а затем на втором ходу удалить элемент, который отличается от того, что Боб удалил на первом ходу, чтобы выиграть игру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
1 2
1 2
3
1 2 3
2 3 1
|
Bob
Alice
|