건초 더미 추측

숨겨진 건초 더미 배열이 다음과 같이 준비되어 있습니다. 더미는 모두 $N$개이며($1 \le N \le 1{,}000{,}000$), $1$번부터 $N$번까지 번호가 매겨져 있습니다. 각 더미에 쌓인 건초 다발의 수는 서로 모두 다르며, 그 값은 $1$ 이상 $1{,}000{,}000{,}000$ 이하의 정수입니다.

더미를 직접 볼 수는 없고, 대신 다음과 같은 형태의 질문을 $Q$개 ($1 \le Q \le 25{,}000$) 던집니다.

$Q_l$번부터 $Q_h$번까지의 더미 중에서 ($1 \le Q_l \le Q_h \le N$), 건초 다발이 가장 적은 더미에는 몇 다발이 쌓여 있나요?

각 질문에는 정수 $A$ 하나로 답이 주어집니다. 이 답들은 항상 참이라는 보장이 없어서, 서로 모순되는 답이 섞여 있을 수 있습니다.

$Q$개의 답이 동시에 모두 참일 수 있는지, 즉 모든 답과 일치하는 더미 배열이 하나라도 존재하는지 판정하세요.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $Q$.
• 둘째 줄부터 $Q+1$째 줄까지: 각 줄에 공백으로 구분된 세 정수 $Q_l$, $Q_h$, $A$가 주어집니다. 이는 $Q_l$번부터 $Q_h$번까지의 더미에 대한 질문과 그 답 $A$를 나타냅니다.

• 첫째 줄: 모든 답이 서로 모순되지 않으면(모든 $Q$개의 답과 일치하는 유효한 더미 배열이 존재하면) $0$을 출력합니다. 그렇지 않으면, 앞서 주어진 답들과 처음으로 모순을 일으키는 답의 순서를 $1$부터 $Q$까지의 번호로 출력합니다.

예시에서 세 번째 질문(“3 12 8”)이 앞선 답들과 처음으로 충돌합니다. 처음 두 답과, 모든 더미의 건초 다발 수가 서로 다르다는 사실로부터 $5$번부터 $10$번 더미 중 정확히 하나가 $7$다발을 가져야 함을 알 수 있습니다. 그러면 $7$다발짜리 더미가 $3$번부터 $12$번 구간 안에 들어가는데, 이 구간의 최솟값은 $8$이라고 답했으므로 모순이 발생합니다.