A rácsos süti

Hansel és Gretel szeretik a süteményeket, különösen a Wolfgang Puck éttermeiben kapható úgynevezett „rácsos sütit”, amely mn különböző süteményből készül, és felülről nézve egy kétdimenziós, m×n-es rácsra emlékeztet (innen az elnevezés).

Az egyetlen dolog, amit Hansel és Gretel nem szeretnek a rácsos sütikben, az az, hogy mindegyik tartalmaz egy szelet karamellmázas süteményt is. (Egy 3×4-es rácsos süti látható a lenti ábrán, barnával jelölve a karamellmázas süteményt.) Wolfgang Puck receptkönyve valójában csak azért tartalmazza a karamellmázas süteményt, mert örökölte az üküknagymamájától.

Sem Hansel, sem Gretel nem szeretné a „rossz” szeletet a maga részében, így a következő módon döntik el, hogy ki kapja azt: először Hansel levág egy darabot magának a rácsvonalak mentén, majd Gretel teszi ugyanezt, és mindezt felváltva folytatják mindaddig, amíg már csak a karamellmázas sütemény marad, amelyet valamelyikük kénytelen elvenni.

Egy 2×3-as rácsos süti esetén például a lenti ábra az alábbi lépéseket mutatja:

1. Hansel levágja a bal oldali oszlopot. (Gretelnek marad egy 2×2-es rácsos süti.)
2. Gretel levágja a bal oldali oszlopot. (Hanselnek marad egy 2×1-es rácsos süti.)
3. Hansel levágja az alsó négyzetet. (Gretelnek marad a karamellmázas sütemény.)

Vágások sorozata annak eldöntésére, hogy Hansel vagy Gretel kapja-e a rossz szeletet.

Hansel és Gretel nagyon sok rácsos sütit megettek már együtt, és olyan sokszor játszották ezt a játékot, hogy már a kezdés előtt tudják, kinek jut végül a rossz szelet. Ha úgy látják, hogy Hanselnek jut, akkor Gretel tudja, milyen stratégia szerint kell játszania, hogy biztosan Hansel kapja a rossz szeletet. Hasonlóan Hansel is ismeri ezt a stratégiát.

Ha adott az eredeti sütemény és benne a karamellmázas szelet pozíciója, ki kapja meg a rossz szeletet?

A bemenet specifikációja

A bemenet első sora egy t egész számot, a tesztesetek számát tartalmazza (1 ≤ t ≤ 100). Ezután t sor következik, amelyek mindegyikében m n r c szerepel (szóközökkel elválasztva), ahol m és n (2 ≤ m, n ≤ 48) a rácsos süti szélességét és hosszúságát adják meg, (r,c) pedig a karamellmázas sütemény pozíciója a rácsos sütiben (0 ≤ r ≤ m – 1, 0 ≤ c ≤ n – 1). A bal felső sarok koordinátája (0,0).

A kimenet specifikációja

Minden tesztesetre annak a személynek a nevét kell a kimenetre írni külön sorban, aki végül megkapja a rossz szeletet, feltételezve, hogy Hansel végzi az első vágást, és hogy Hansel és Gretel mindig optimális helyen vágnak (próbálva elkerülni a karamellmázas süteményt). A „vágás” itt egy egyenes vonalú, rácsvonal mentén végrehajtott vágást jelent, amely két részre osztja a sütit.

Példa bemenet

1. 2
2. 2 3 0 2
3. 11 11 5 5

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Gretel
2. Hansel

letöltés szöveges állományként