29873번 - Linn 스페셜 저지다국어

Kinnisvaraarendaja tahab ehitada uuele tänavale $N$ maja (nummerdatud $1 \ldots N$). Vaadete vahelduse huvides nõuab linnavalitsus, et majade kõrgused peavad olema $1$ kuni $N$ korrust ja paarikaupa erinevad.

Peale selle on linnavalitsusel majade kõrgustele $M$ lisanõuet, millest igaüks määrab tänava mingile lõigule ehitatavate majade minimaalse lubatud kõrguse. Ehitusprojekti tähtsuse tõttu on linnavalitsus nõus vajadusel loobuma ühest lisanõudest.

Leida võimalik ehitusplaan või tuvastada, et seda pole.

Sisendi esimesel real on majade arv $N$ ja linnavalistuses lisanõuete arv $M$ ($2 \le N \le 3 \cdot 10^5$, $1 \le M \le 3 \cdot 10^5$). Järgmisel $M$ real on igaühel ühe lisanõude kirjeldus: täisarvud $H_i$, $S_i$ ja $F_i$ ($2 \le H_i \le N$, $1 \le S_i \le F_i \le N$), mis tähendavad, et kõik majad alates majast number $S_i$ kuni majani number $F_i$ (mõlemad kaasa arvatud) peavad olema vähemalt $H_i$-korruselised.

Kui nõutud ehitusplaani ei leidu, väljastada ainsale reale 'EI SAA'.

Kui plaan leidub, väljastada esimesele reale 'SAAB' ja teisele reale $N$ täisarvu, mis näitavad majade kõrgusi. Väljastatud plaan peab rahuldama vähemalt $M - 1$ sisendis kirjeldatud lisanõuet. Kui võimalikke plaane on mitu, väljastada ükskõik milline neist.