Csigavonal

Sajnos hiába próbáltuk megzavarni a támadók kísérleteit, ők mégis bejutottak a hálózatunkba. Jelenleg AI botok százait engedték szabadon a routerek, switchek, szerverek között annak érdekében, hogy megzavarják a verseny lefolyását. Szerencsére ezek kezdetleges, jutalmazási rendszeren alapuló AI botok, melyek a hálózatban csak "körbe-körbe" keringenek és ha alacsonyabb értékű szerverhez jutnak, mint az előző lépésben akkor lefagy a működésük. Így a Ti feladatotok az lesz, hogy eldöntsétek, hogy egy adott robot ténykedését megfigyelve eldöntsétek, hogy a robot eljut-e a legértékesebb szerverig, avagy nem.

Input

A bemenet egy n x n-es mátrix az alábbiak szerint:

• Az első sor egy n pozitív egész páratlan szám, mely megadja a mátrix sorainak és oszlopainak számát.
• A következő n sor mindegyike n darab, szóközzel elválasztott egész számot tartalmaz.
• Az első sor első száma a mátrix [0][0] eleme, míg az utolsó sor utolsó száma a mátrix [n-1][n-1] eleme.

Megjegyzés: minden bemeneti sor végén egy sor vége karakter található.

Output

A kimenet az 1-es szám amennyiben a bemenetben megadott M mátrix "középső" (M[(n-1)/2][(n-1)/2]-edik) elemétől jobbra indulva, az óramutató járásával ellentétesen, csigavonalban haladva az M[0][0] értékig (beleértve az M[0][0]-t is) az összes szám nagyobb-egyenlő, mint az előző.

Amennyiben ez nem teljesül, úgy a kimenet a 0 szám.

Példa

Magyarázat

Az első esetben a kiindulási számunk a 13 és mivel jobbra indulunk, így a 14-es elem a következő. Az óramutató járásával ellentétes csigavonal az alábbi haladást adja nekünk a [0][0] elemig:
13-14-9-8-7-12-17-18-19-20-15-10-5-4-3-2-1
Mivel ez a sorozat nem monoton növekvő, így a válasz 0.

A második esetben a kiindulási számunk az 5-ös és mivel jobbra indulunk, így a 6-os elem a következő. Az óramutató járásával ellentétes csigavonal az alábbi haladást adja nekünk a [0][0] elemig:
5-6-7-8-9
Mivel ez a sorozat monoton növekvő, így a válasz 1.