#0000F8

z-pharaoh

Profesor Z predaje istoriju u lokalnoj školi. Njegovi časovi su zanimljivi djacima. Pedja posebno voli časove istorije i toliko se uživeo u lekciju o starom Egiptu, da je zaspao na času i počeo je da sanja piramide.


San: na ulazu u jednu od piramida stoji priča o legendi da onaj ko udje u piramidu i po njenoj unutrašnjosti se ispne na najviši nivo, postaje sledeći faraon. Piramida je kvadratne osnove a blokovi su kocke stranice 1. Osnova je neparne dužine od N blokova. Svaki sledeći nivo je za dva uži a na vrhu piramide je jedan jedini kameni blok.


Tokom godina krize, lopovi su povadili neke od kamenih blokova iz unutrasnjosti piramide, ne dirajući ni jedan blok koji se spolja može videti. Za sobom su ostavili splet hodnika i dvorana po kojima je moguće kretanje i penjanje. Blokovi stoje jedan na drugom ili vise ili lebde u prostoru. Pedja može da se kreće slobodno po nivou na kome se nalazi (levo, desno, napred ili nazad) ili da se popne na susedni blok koji je za jedan viši (ako ima slobodnog prostora iznad sebe) ili da predje na niži nivo bez obzira koliko nisko je sledeći blok. (Blokovi mogu da vise i lebde a Pedji neće ništa biti usled pada jer setite se, on to sanja).


Temelj ispod piramide je kvadratnog oblika dubine N. Ni blokovi iz temelja nisu poštedjeni u teškim vremenima. Kradljivci su ipak ostavili spisak koordinata blokova koji su odneli. prvi red blokova u piramidi je označen kao nulti nivo. Prvi blok u njemu je (1,1,0) a dijagonalno suprotni(N,N,0)


Image: piramida

InputU prvom redu ulaza nalazii se broj N, (2<N<100) dimenzija stranice piramide.
U drugom redu ulaza nalazii se broj B, (1<B<=100 000) broj ukradenih blokova iz piramide.
U sledećih B redova nalaze se po 3 cela broja S<sub>x</sub>, Sy i S<sub>z</sub> koji predstavljaju koordinate odnesenih blokova S. (1 <= Sx, Sy <= N; -N <= Sz <= (N+1)/2).

OutputU prvi red izlaza treba ispisati najviši nivo u piramidi na koji se Pedja može popeti. Pedja uvek polazi sa koordinate ((N+1)/2, 1, 0), što predstavlja polovinu stranice piramide Računanje najvišeg unutrašnjeg nivoa piramide do kod Pedja može stići počinje nakon njegovog prvog koraka.

Ulaz:
7
11
4 1 0
4 2 0
4 2 -1
4 2 -2
4 3 -2
3 3 -2
2 3 -2
1 3 -2
1 4 -2
4 2 -3
4 3 -3

Izlaz:
-2
Image: example

Objašnjenje: Čim udje u piramidu, Pedja pada tri bloka naniže. Odatle može da ide napred jedan blok a zatim može da se popne na blok levo gore To je moguće jer nema kamenog bloka iznad (4,3,-2) koji bi mu blokirao prolaz. Sada se nalazi na nivou za 2 nižem od onog sa koga je krenuo. Još može da se pomeri ulevo dva bloka i jedan napred, ali sve je to na istom nivou. Pošto je pri prvom koraku pao na niži nivo, računanje počinje od -3, a odatle je moguće doći najviše do nivoa -2.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.