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

Limits: 2 sec., 256 MiB

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

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

Input

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

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

Output

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

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

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
4 7 10 4 0 2 5 4 7	Marichka RLRL

Input (stdin) сopy	Output (stdout) сopy
1 4 4	Marichka L

Notes

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

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