Problem H
Vandring

När Ellinor reser gillar hon att gå på äventyr. Just nu befinner hon sig på rutan högst uppe till vänster i ett $R \times R$ stort rutnät. Hon vill ta sig till rutan längst nere till höger. För att göra detta kommer hon utföra en vandring, där hon endast går ät åt höger eller nedåt. Varje ruta innehåller en sevärdhet, numrerad från $0$ till $R \cdot R-1$. Samma sevärdhet kan finnas på flera rutor. Hon tycker att en vandring är intressant om alla sevärdheter längs med vägen är unika, det vill säga besöker hon aldrig samma sevärdhet två gånger. Om Ellinor utför sin vandring helt slumpmässigt, är det garanterat att den kommer vara intressant?

Indata

Den första raden i indatan innehåller heltalet $R$ ($1 \leq R \leq 1000$), antalet rader i rutnätet.

Därefter följer en beskrivning av rutnätet. Varje av de $R$ raderna innehåller $R$ heltal mellan $0$ och $R \cdot R - 1$, sevärdheterna i den raden.

Notera att det här problemet har väldigt mycket indata. Det är därför rekommenderat att använda snabb indataläsning.

Utdata

Om Ellinors vandring kommer vara intressant oavsett hur hon utför den, skriv ut 1. Om inte, skriv ut 0 istället.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

Exempelfall 1: eftersom alla sevärdheter är unika finns det ingen risk att se samma sevärdhet två gånger.

Exempelfall 2: även om sevärdhet $1$ dyker upp två gånger är det omöjligt att se den två gånger.

Exempelfall 3: om Ellinor har otur går hon först ner och sedan till höger och ser då sevärdhet $1$ två gånger. Därmed är inte alla möjliga vandringar intressanta.

Exempelfall 4: Ellinors start- och slutrutor innehåller båda sevärdhet $0$, så ingen är vandring intressant.

2
0 1
2 3

1

2
0 1
1 2

1

2
0 2
1 1

0

2
0 1
1 0

0

1
0

1