D. Игра в делимость
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть массив $$$a$$$ из $$$n$$$ элементов и массив $$$b$$$ из $$$m$$$ элементов.

Игроки ходят по очереди. Первой ходит Алиса. На своем ходу каждый игрок выбирает число $$$x$$$ из массива $$$a$$$ и число $$$y$$$ из массива $$$b$$$. При этом у Алисы есть свое правило выбора $$$x$$$ и $$$y$$$, а у Боба свое:

  • Алиса должна выбрать $$$x$$$ и $$$y$$$ так, чтобы $$$y$$$ делился нацело на $$$x$$$.
  • Боб должен выбрать $$$x$$$ и $$$y$$$ так, чтобы $$$y$$$ не делился нацело на $$$x$$$.

После выбора $$$x$$$ и $$$y$$$ из массива $$$b$$$ удаляется $$$y$$$ (но при этом $$$x$$$ остается в $$$a$$$). Когда $$$y$$$ удаляется из $$$b$$$, если в массиве несколько вхождений $$$y$$$, удаляется только одно из них. Проигрывает тот игрок, который не может сделать ход.

Кто победит, если оба игрока играют оптимально?

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^{6}$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{i}$$$ ($$$1 \le a_{i} \le n + m$$$) — элементы массива $$$a$$$.

Последняя строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$b_{i}$$$ ($$$1 \le b_{i} \le n + m$$$) — элементы массива $$$b$$$.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$;
  • сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Выходные данные

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

  • Alice (если победит Алиса);
  • Bob (если победит Боб).
Пример
Входные данные
3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5
Выходные данные
Alice
Bob
Alice
Примечание

Рассмотрим первый набор входных данных. Покажем, как Алиса выигрывает по ходам:

  • Ход Алисы: $$$x = 3, y = 6$$$ (после этого $$$6$$$ удалится из $$$b$$$, в результате $$$b = [7, 12]$$$)
  • Ход Боба: $$$x = 3, y = 7$$$ (Боб в свой ход выберет $$$y = 7$$$ в любом случае, так как не существует $$$x$$$, который не делит $$$y = 12$$$, после этого хода $$$b = [12]$$$)
  • Ход Алисы: $$$x = 4, y = 12$$$ (после этого хода $$$b$$$ становится пустым)
  • Ход Боба: Боб проигрывает, так как не может сделать ход