Linn

문제

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

Peale selle on linnavalitsusel majade kõrgustele $MM$ 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 $NN$ ja linnavalistuses lisanõuete arv $MM$ ($2\le N\le 3\cdot {10}^{5}2\; \backslash le\; N\; \backslash le\; 3\; \backslash cdot\; 10^5$, $1\le M\le 3\cdot {10}^{5}1\; \backslash le\; M\; \backslash le\; 3\; \backslash cdot\; 10^5$). Järgmisel $MM$ real on igaühel ühe lisanõude kirjeldus: täisarvud $H_{i}H\_i$, $S_{i}S\_i$ ja $F_{i}F\_i$ ($2\le H_i\le N2\; \backslash le\; H\_i\; \backslash le\; N$, $1\le S_i\le F_i\le N1\; \backslash le\; S\_i\; \backslash le\; F\_i\; \backslash le\; N$), mis tähendavad, et kõik majad alates majast number $S_{i}S\_i$ kuni majani number $F_{i}F\_i$ (mõlemad kaasa arvatud) peavad olema vähemalt $H_{i}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 $NN$ täisarvu, mis näitavad majade kõrgusi. Väljastatud plaan peab rahuldama vähemalt $M-1M\; -\; 1$ sisendis kirjeldatud lisanõuet. Kui võimalikke plaane on mitu, väljastada ükskõik milline neist.