RMQ 역문제

구간 최댓값 질의(RMQ) 문제는 다음과 같다.

$1$부터 $N$까지의 정수로 이루어진 순열 $P$가 주어진다. 질의는 $1 \le L \le R \le N$을 만족하는 $(L, R)$ 꼴이고, $P$의 $L$번째 수부터 $R$번째 수까지 중 최댓값을 묻는다.

$P = (3, 1, 4, 2, 5)$인 경우 질의 $(1, 2)$의 답은 $\max(3, 1) = 3$, 질의 $(2, 4)$의 답은 $\max(1, 4, 2) = 4$, 질의 $(4, 5)$의 답은 $\max(2, 5) = 5$이다.

이 문제에서는 RMQ를 거꾸로 푼다. 정수 $N$과 질의의 개수 $M$, 그리고 각 질의 $(L_i, R_i)$와 그 답 $A_i$가 주어진다. 주어진 질의를 모두 만족하는 순열 $P$가 존재하는지 판정하는 프로그램을 작성하시오.

첫째 줄에 $N$과 질의의 개수 $M$이 주어진다. ($1 \le N \le 10^9$, $1 \le M \le 50$)

둘째 줄부터 $M$개의 줄에 각 질의의 $L_i$, $R_i$와 답 $A_i$가 주어진다. ($1 \le L_i \le R_i \le N$, $1 \le A_i \le N$)

주어진 질의를 모두 만족하는 순열이 존재하면 1을, 존재하지 않으면 0을 출력한다.