Алиса и Боб играют в игру с \(n\) кучками камней, где \(i\)-я кучка содержит \(a_i\) камней. Игроки делают ходы по очереди, причем Алиса ходит первой.
На каждом ходу игрок выполняет следующие три шага:
- Выбирает целое число \(k\) (\(1 \leq k \leq \frac n 2\)). Обратите внимание, что значение \(k\) может быть разным для разных ходов.
- Удаляет \(k\) куч камней.
- Выбирает еще \(k\) кучек камней и разделяет каждую кучку на две кучки. Количество камней в каждой новой куче должно быть простым числом.
Игрок, который не сможет сделать ход, проигрывает.
Определите, кто выиграет, если оба игрока играют оптимально.
Выходные данные
Для каждого набора входных данных выведите «Alice» (без кавычек), если Алиса выиграет, и «Bob» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «alIcE», «Alice» и «alice» будут считаться одинаковыми.
Примечание
В первом наборе входных данных есть \(2\) кучи камней с количествами камней \(2\) и \(1\) соответственно. Поскольку ни \(1\), ни \(2\) не могут быть разделены на два простых числа, Алиса не может сделать ход, поэтому Боб выигрывает.
Во втором наборе входных данных есть \(3\) кучи камней с \(3\), \(5\) и \(7\) камнями соответственно. Алиса может выбрать \(k = 1\), удалить кучу из \(7\) камней, а затем разделить кучу из \(5\) камней на две кучи камней с простыми количествами \(2\) и \(3\). В итоге получится \(3\) кучки камней с \(3\), \(2\) и \(3\) камнями соответственно, в результате чего у Боба не остается ни одного допустимого хода, и Алиса выигрывает.
В третьем наборе входных данных есть \(4\) кучи камней с \(4\), \(6\), \(8\) и \(10\) камнями соответственно. Алиса может выбрать \(k = 2\) и удалить две кучи камней \(8\) и \(10\). Далее она делит кучу камней \(4\) на две кучи камней с простыми количествами \(2\) и \(2\), а кучу камней \(6\) — на две кучи камней \(3\) и \(3\). После этого у Боба не остается допустимых ходов, и Алиса выигрывает.
В четвертом наборе входных данных есть \(5\) куч камней, каждая из которых содержит \(8\) камней. Можно показать, что если оба игрока играют оптимально, то победит Боб.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
2 1
3
3 5 7
4
4 6 8 10
5
8 8 8 8 8
|
Bob
Alice
Alice
Bob
|