Unfair Game

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka decided to play games in order to take a break from intensive preparation for the ZNO. Zenyk suggested playing a game with stones. In this game, players are given \(n\) piles of stones, numbered from 1 to \(n\). The pile numbered \(i\) contains \(a_i\) stones. The players take turns, starting with Marichka. In one turn, a player can choose any pile with a positive number of stones and take a positive number of stones from it. The player who cannot make a move loses.

Marichka doesn’t want to play this game because she considers it very boring, so she suggested modifying it. Now Marichka has the right to take a positive number of stones from any subset of piles of size from 1 to \(n-1\). The rules of the game for Zenyk remain unchanged.

Overconfident Zenyk agreed to this modification, not suspecting that Marichka has a huge advantage in such a game. Who will win under optimal play by both players?

Input

The first line contains a single integer \(n\) — the number of piles.

The second line contains \(n\) integers — \(a_1\), \(a_2\), ..., \(a_n\).

Output

In the first line, if Marichka wins, output Marichka, otherwise output Zenyk.

If Marichka wins, then in the next line output \(n\) non-negative integers \(b_i, 0 \le b_i \le a_i\), separated by spaces, where \(b_i\) represents the number of stones that Marichka should take from the pile numbered \(i\) on her first move.

The number of non-zero elements in the output sequence cannot be equal to 0 or \(n\).

Constraints

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

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

for 40% of the tests:

\(2 \le n \le 4\).

Samples

Input (stdin) сopy	Output (stdout) сopy
5 1 1 1 1 1	Marichka 1 1 0 0 0

Input (stdin) сopy	Output (stdout) сopy
2 1 1	Zenyk

Notes

In the first example, Marichka can take stones from the first and second piles on her first move. Regardless of Zenyk’s decision, on the next turn, there will be two non-empty piles left, from which Marichka can take all the remaining stones.