There are $q$ statement, each of the form $(l, r, t)$ means that $$A_l + A_{l + 1} + ... + A_r$$ is odd if $t = 1$, or is even if $t = 0$.
Find the largest $k$ that there is at least one array $A$ of length $n$ satisfies every statement from $1$ to $k$.
### Input
- The first line contains 2 integers $n, q$.
- The next $q$ lines, each line contains 3 integers $l, r, t$, a statement.
### Output
- Print the a single integer is the largest possible $k$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le l, r \le n$.
- $0 \le t \le 1$.
### Example
Input:
```
10 5
1 2 0
3 4 1
5 6 0
1 6 0
7 10 1
```
Output:
```
3
```
