Найкраща стратегія

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

Зеник та Марічка вирішили зіграти в таку гру. У них є \(2 n\) камінців, розташованих у ряд, на \(i\)-му камінцеві написане число \(a_i\). Зеник та Марічка ходять по черзі, Марічка розпочинає гру. Під час ходу гравець бере собі найлівіший або найправіший камінець. Гра завершується, коли гравці заберуть усі камінці.

Марічка перемагає у грі, якщо сума чисел її камінців не менша суми чисел камінців Зеника, інакше перемагає Зеник. Зеник вважає, що знає оптимальну стратегію гри — він завжди бере камінець з більшим числом, а якщо вони однакові — найлівіший. Допоможіть Марічці визначити, чи може вона перемогти в такій грі.

Вхідні дані

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

Наступний рядок містить \(2 n\) цілих чисел \(a_i\).

Вихідні дані

У першому рядку виведіть \(\texttt{Marichka}\), якщо Марічка може перемогти, інакше виведіть \(\texttt{Zenyk}\).

Якщо Марічка може перемогти, також виведіть її стратегію — рядок із \(n\) символів, де \(i\)-ий символ рівний L, якщо під час \(i\)-го свого ходу вона має обрати найлівіший камінець, інакше \(i\)-ий символ рівний R. Якщо існує кілька стратегій — виведіть довільну.

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 7 10 4 0 2 5 4 7	Marichka RLRL

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 4 4	Marichka L

Примітки

У першому прикладі сума чисел камінців Марічки рівна 21, а Зеника — 18. Також існують інші виграшні стратегії для Марічки.

Зауважте, що Марічка перемагає якщо суми чисел гравців однакові.