Inverse RMQ

Time limit2sMemory limit512 MB

Summary

Given query intervals and their maximum answers over a hidden permutation of 1..N, decide whether some permutation of 1..N satisfies all queries.

Level: Medium7 of 10
Topics: Greedy, Intervals, Sorting
Solved: No attempts yet

Problem

The range maximum query (RMQ) problem is stated as follows.

A permutation $P$ of the integers $1$ through $N$ is given. A query has the form $(L, R)$ with $1 \le L \le R \le N$ , and it asks for the largest value among the $L$ -th through $R$ -th entries of $P$ .

For $P = (3, 1, 4, 2, 5)$ , the answer to query $(1, 2)$ is $\max(3, 1) = 3$ , the answer to query $(2, 4)$ is $\max(1, 4, 2) = 4$ , and the answer to query $(4, 5)$ is $\max(2, 5) = 5$ .

This problem runs RMQ backwards. You are given an integer $N$ , the number of queries $M$ , and for each query the pair $(L_i, R_i)$ together with its answer $A_i$ . Write a program that decides whether some permutation $P$ satisfies every given query.

Input

The first line contains $N$ and the number of queries $M$ . ( $1 \le N \le 10^9$ , $1 \le M \le 50$ )

Each of the next $M$ lines contains $L_i$ , $R_i$ , and the answer $A_i$ . ( $1 \le L_i \le R_i \le N$ , $1 \le A_i \le N$ )

Output

Print 1 if a permutation satisfying every given query exists, and 0 otherwise.

Examples6

Example 1
Input
```
5 3
1 2 3
2 4 4
4 5 5
```
Expected output
```
1
```
Example 2
Input
```
5 3
1 1 3
2 2 3
3 3 3
```
Expected output
```
0
```

Example 3

Input

600 6
1 100 100
101 200 200
201 300 300
301 400 400
401 500 500
501 600 600

Expected output

Example 4

Input

1000000000 2
1234 5678 10000
1234 5678 20000

Expected output

Example 5

Input

Expected output

Example 6
Input
```
1000000000 1
1 1000000000 19911120
```
Expected output
```
0
```