Саша подарил Ане на День святого Валентина массив \(a\) из \(n\) целых чисел. Ане не нужен этот массив, поэтому она предлагает его уничтожить, сыграв в игру.
Игроки ходят по очереди. Саша джентльмен, поэтому уступает право первого хода Ане.
- Аня в свой ход должна выбрать элемент \(a_i\) из массива и развернуть последовательность цифр его значения. Например, если Аня выбрала элемент со значением \(42\), он превратится в \(24\); если Аня выбрала элемент со значением \(1580\), он превратится в \(851\). Обратите внимание, что ведущие нули удаляются. После этого хода количество элементов в массиве не изменится.
- Саша в свой ход должен извлечь два элемента \(a_i\) и \(a_j\) (\(i \ne j\)) из массива, склеить их в любом порядке и вставить результат в массив. Например, если Саша выбрал элементы равные \(2007\) и \(19\), то он удалит эти два элемента из массива и добавит значение \(200719\) или \(192007\). После этого хода количество элементов в массиве уменьшится на \(1\).
Пропускать ходы игроки не могут. Игра заканчивается, когда Саша не может сделать ход, то есть после хода Ани осталось ровно одно число. Если это число не меньше \(10^m\) (т.е., \(\ge 10^m\)), побеждает Саша. В противном случае побеждает Аня.
Можно показать, что игра всегда закончится. Сообщите, кто выиграет, если оба игрока играют оптимально.
Выходные данные
Для каждого набора входных данных выведите:
- «Sasha», если при оптимальной игре побеждает Саша;
- «Anna», если при оптимальной игре побеждает Аня.
Примечание
Рассмотрим первый набор входных данных.
Аня может развернуть число \(2\), тогда Саша склеит числа \(2\) и \(14\), получив число \(214\), что больше \(10^2 = 100\). Если бы Аня развернула число \(14\), Саша бы склеил числа \(41\) и \(2\), получив число \(412\), что больше \(10^2 = 100\). Других возможных ходов у Ани нет, поэтому она проигрывает.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
2 2
14 2
3 5
9 56 1
4 10
1 2007 800 1580
4 5
5000 123 30 4
10 10
6 4 6 2 3 1 10 9 10 7
1 1
6
1 1
10
8 9
1 2 9 10 10 2 10 2
4 5
10 10 10 10
|
Sasha
Anna
Anna
Sasha
Sasha
Anna
Anna
Anna
Sasha
|