Problem Description

B City's subway system has a long history. X Line, which Xue and Ke are riding on, is a circular route with $n$ stations. The distance between any two adjacent stations is a positive integer. Xue has made some observations and obtained $m$ pieces of information, where the $i$-th piece is one of the following forms:

1. The distance clockwise from station $S_i$ to station $T_i$ is at least a given value $L_i$.
2. The distance clockwise from station $S_i$ to station $T_i$ is at most a given value $L_i$.

Xue wants you to calculate how many different valid total lengths of the X Line subway are possible.

Input Format

The first line contains two space-separated positive integers $n$ and $m$.

The next $m$ lines, each containing four space-separated positive integers $type_i, S_i, T_i, L_i$, where $type_i \in \{1, 2\}$ indicates the type of information. Stations are numbered clockwise from 1 to $n$. It is guaranteed that $1 \le S_i, T_i \le n$ and $S_i \ne T_i$.

Output Format

Output a single integer, which is the answer to the problem. If there are infinitely many possible values, output -1.

It is guaranteed that the answer is not zero, meaning there is at least one possible solution.

Sample Input and Output

Input Sample #1

4 6
1 1 3 3
2 2 4 5
1 2 4 4
1 3 1 4
2 4 2 5
1 4 2 3

Output Sample #1

4

Input Sample #2

3 2
2 1 2 1
2 2 3 1

Output Sample #2

-1

Input Sample #3

See the attached file subway3.in.

Output Sample #3

See the attached file subway3.ans.

Notes

Sample 1 Explanation

Define an array $d[1..4]$, where $d[i]$ represents the distance from station $i$ to station $i+1$ clockwise.

1. $d=[1,2,2,2]$, total length is $7$;
2. $d=[1,2,2,3]$, total length is $8$;
3. $d=[1,2,2,4]$, total length is $9$;
4. $d=[1,2,3,4]$, total length is $10$.

It can be proven that no other possible lengths exist, so the answer is $4$.

Sample 2 Explanation

The distance from station 3 to station 1 clockwise can be any positive integer.

Data Range and Hints

• For $30\%$ of the data, $n, m \le 9$ and $L_i \le 5$;
• For another $15\%$ of the data, $T_i$ is the station immediately following $S_i$ clockwise;
• For another $20\%$ of the data, $T_i$ is the second station following $S_i$ clockwise;
• For another $25\%$ of the data, $n, m \le 50$;
• For $100\%$ of the data, $3 \le n \le 500$, $1 \le m \le 500$, $1 \le L_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分