도시

건설업자가 새 도로에 $N$개의 건물을 지으려고 합니다. 건물에는 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 시청은 경관에 변화를 주기 위해 각 건물의 높이가 $1$층부터 $N$층 사이이고, 어떤 두 건물도 높이가 같지 않아야 한다고 정합니다.

시청은 이 밖에도 $M$개의 추가 조건을 정해 두었습니다. 각 추가 조건은 도로의 일정 구간에 세울 건물의 최소 높이를 정합니다. 이 사업은 중요하므로, 시청은 필요하다면 추가 조건 하나를 포기할 수 있습니다.

조건을 만족하는 건설 계획을 찾거나, 그런 계획이 존재하지 않음을 밝히세요.

첫 줄에 건물 수 $N$과 추가 조건 수 $M$이 주어집니다 ($2 \le N \le 3 \cdot 10^5$, $1 \le M \le 3 \cdot 10^5$). 다음 $M$개의 줄에는 각각 정수 $H_i$, $S_i$, $F_i$가 주어집니다 ($2 \le H_i \le N$, $1 \le S_i \le F_i \le N$). 이는 $S_i$번 건물부터 $F_i$번 건물까지(양 끝 포함) 모든 건물이 $H_i$층 이상이어야 한다는 뜻입니다.

건설 계획이 존재하지 않으면 한 줄에 EI SAA를 출력합니다. 계획이 존재하면 첫 줄에 SAAB를 출력하고, 둘째 줄에 건물 $1$번부터 $N$번까지의 높이를 나타내는 정수 $N$개를 출력합니다. 출력한 계획은 주어진 추가 조건 중 최소 $M-1$개를 만족해야 합니다. 가능한 계획이 여러 개라면 그중 아무거나 출력하면 됩니다.