Борьба за треугольники
Энди и Ральф играют в игру на двоих на треугольной доске, которая выглядит следующим образом:
Каждый игрок по очереди выбирает две соседние вершины и проводит между ними отрезок. Если новый отрезок завершает треугольник на доске (учитываются только минимальные треугольники), игрок забирает этот треугольник и получает право на дополнительный ход. Если треугольник не образуется, ход переходит к другому игроку. Цель игры — захватить как можно больше треугольников. Например, предположим, что сейчас ход Энди, и на доске уже есть пять отрезков, как показано на рисунке ниже. Если Энди проведет отрезок 6, он захватит треугольник, образованный отрезками 4, 5 и 6, и продолжит ходить.
Известно, что на доске уже нарисованы некоторые отрезки. Определите победителя игры, если оба игрока играют оптимально. Энди всегда начинает первым. Обратите внимание, что если треугольник уже существует на доске до первого хода, ни один из игроков его не забирает.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается с строки, содержащей целое число N, 5 ≤ N ≤ 10, которое указывает количество отрезков, уже присутствующих на доске до начала игры. Следующая строка содержит N целых чисел, указывающих индексы этих отрезков. Ввод заканчивается строкой с N = 0.
Выходные данные
Для каждого теста выведите одну строку с результатом игры. Если выигрывает Энди, выведите "Andy wins". Если выигрывает Ральф, выведите "Ralph wins". Если оба игрока получают одинаковое количество треугольников, выведите "Draw". Кавычки используются для ясности и не должны быть напечатаны.