3. A tak sa hrali na štrkovisku

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Emovi na [email protected]

Jitka a Marcel sa išli spolu hrať von na pieskovisko. Po hodine ich to však prestalo baviť, veď už sú dospelí! A veľké deti sa nehrajú na pieskovisku, hrajú sa na štrkovisku. Pobrali si svoje formičky a vybrali sa na neďaleké štrkovisko. No zábava im ani tam nevydržala dlho – skúšali ste robiť pieskový koláčik zo štrku?

Našťastie dostala Jitka nápad na novú hru. Najprv si pozbierali nejaký počet kamienkov a zoradili ich do postupnosti podľa hmotnosti (Marcel je veľmi citlivý človek, a dokáže bezchybne porovnať váhu ľubuvoľných dvoch kamienkov). Následne brali rad radom kamienky, začnúc najťažším. Kamienok si vždy bral hráč, ktorý mal v tom čase menší súčet hmotností kamienkov, poprípade, ak ich kôpky mali rovnakú hmotnosť, vyberala Jitka (dámy majú prednosť). Po zobratí posledného kamienku vyhral hráč s väčším súčtom hmotností.

Ako prvá si kamnieok berie Jitka, keďže obaja majú vtedy súčet hmotností 0 a pamätáte sa, ako je to s tou prednosťou.

S veľkým počtom kamienkov však hra trvá dlho. Vedeli by ste im preto pomôcť napísať program, ktorý by zistil, kto z hráčov vyhrá?

Úloha

Na vstupe je zostupne usporiadaná postupnosť čísel. Jitka a Marcel sa hrajú hru, pri ktorej postupne berú čísla z postupnosti (začínajúc najväčším). V každom ťahu berie hráč s menším súčtom. Na začiatku alebo v prípade, že majú rovnaký súčet berie Jitka. Vašou úlohou je zistiť, ktorý hráč vyhrá a s akým náskokom.

Formát vstupu

Na prvom riadku vstupu dostanete číslo \(n\) (\(1 \leq n \leq 10^5\)).

Na druhom riadku je \(n\) čísel \(k_1\) až \(k_n\) – hmotnosti jednotlivých kamienkov. Platí, že \(1 \leq k_i \leq 10^6\) a tieto hodnoty sú na vstupe zoradené od najväčších čísel po najmenšie.

Formát výstupu

Na jediný riadok výstupu vypíšte meno víťazného hráča (Jitka alebo Marcel) a medzerou oddelený náskok s akým daný hráč vyhral. V prípade remízy vypíšte Remiza.

Hodnotenie

Príklad obsahuje \(5\) sád vstupov. Za každú je možné získať najviac \(3\) body. V prvých troch sadách platí \(n \leq 1\,000\).

Tip: Súčty hmotností kamienkov v poslednej sade môžu byť veľmi veľké čísla. Preto si treba uvedomiť, že v niektorých jazykoch majú bežné celočíselné premenné obmedzený rozsah. Napríklad v C++ int má klasicky 32 bitov, čo nemusí stačiť. Chcete preto použiť 64 bitové premenné (napr. long long v C++, Int64 v Pascale).

Príklad

Input:

5
15 12 11 3 1

Output:

Marcel 4

(Začína Jitka a zoberie kameň hmotnosti 15, potom ďalšie dva kamene zoberie Marcel. Zvyšok už zoberie Jitka, ale to jej na víťazstvo nestačí.)

Input:

4
100 20 20 20

Output:

Jitka 40

(Začína Jitka a zoberie 100, zvyšok uz Marcelovi stačiť nebude.)

Input:

2
7 7

Output:

Remiza