City

Time limit3sMemory limit1024 MB

Summary

Assign distinct heights 1 to N to N buildings so that at least M-1 of the M segment minimum-height requirements hold, or report that no plan exists.

Level: Medium7 of 10
Topics: Greedy, Segment tree, Array
Solved: No attempts yet

Problem

A property developer wants to build $N$ buildings on a new street, numbered $1$ to $N$ . To keep the street skyline varied, the city council requires that each building has between $1$ and $N$ floors, and that no two buildings have the same height.

The council also has $M$ additional requirements. Each one sets a minimum height for the buildings in one segment of the street. Because the project is important, the council is willing to drop one of the additional requirements if needed.

Find a valid construction plan, or determine that none exists.

Input

The first line contains $N$ and $M$ ( $2 \le N \le 3 \cdot 10^5$ , $1 \le M \le 3 \cdot 10^5$ ). Each of the next $M$ lines contains three integers $H_i$ , $S_i$ , $F_i$ ( $2 \le H_i \le N$ , $1 \le S_i \le F_i \le N$ ). This means that every building from $S_i$ to $F_i$ (inclusive) must have at least $H_i$ floors.

Output

If no plan exists, print EI SAA on a single line. Otherwise, print SAAB on the first line and $N$ integers on the second line, giving the heights of buildings $1$ to $N$ . The plan must satisfy at least $M-1$ of the given requirements. If several plans are possible, print any of them.

Examples3

Example 1
Input
```
2 2
2 1 1
2 1 2
```
Expected output
```
SAAB
2 1
```
Example 2
Input
```
3 2
2 1 2
2 2 3
```
Expected output
```
SAAB
1 3 2
```
Example 3
Input
```
4 2
4 1 2
3 2 4
```
Expected output
```
EI SAA
```