Гра з проміжками

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка мають \(n\) камінців, розташованих у ряд. На \(i\)-ому камінцеві написано число \(a_i\).

Зеник і Марічка грають у гру. Вони ходять по черзі. Марічка ходить першою. На кожному ході гравець бере деякий непорожній послідовний проміжок камінців.

Наприклад, у нас є ряд із камінцями [4, 7, 2, 5, 9]. Гравець може вибрати взяти камінці із числами 2 й 5. Після ходу новий ряд матиме вигляд [4, 7, 9].

Гра завершується, коли всі камінці взяті.

Коли гравець бере камінець із числом \(x\), він отримує \(n^x\) штрафних балів. Гравець із меншою кількістю штрафних балів є переможцем гри.

Визначте, хто виграє, якщо обоє гравців грають оптимально.

Вхідні дані

Перший рядок містить ціле число \(n\) — кількість камінців.

Другий рядок містить \(n\) цілих чисел \(a_i\) — числа, записані на камінцях.

Вихідні дані

Виведіть Zenyk, якщо виграє Зеник, Marichka, якщо виграє Марічка, або Draw, якщо гра закінчиться внічию.

Обмеження

\(1 \le n \le 10^5\),

\(0 \le a_i \le 10^9\).

Приклади