Description

The subway in City B has a long history. Line X, which Xiaoxue and Xiaokeke take, is a circular line with $n$ stations on it. The track length between any two adjacent stations is a positive integer. Now Xiaoxue made some observations and obtained $m$ pieces of information. The $i$-th piece of information is of one of the following forms:

1. The clockwise distance along the ring from $S_i$ to $T_i$ is not less than a given value $L_i$ ($S_i$ and $T_i$ are two stations).
2. The clockwise distance along the ring from $S_i$ to $T_i$ is not greater than a given value $L_i$.

Xiaoxue wants you to compute how many different valid values the total length of Line X can take.

Input Format

The first line contains two positive integers $n$ and $m$, separated by spaces.

The next $m$ lines each describe one piece of information. The $i$-th line contains four positive integers $type_i, S_i, T_i, L_i$, separated by spaces, where $type_i \in \{1,2\}$ indicates the type of the information. Stations are numbered clockwise as consecutive integers starting from 1. It is guaranteed that $1 \le S_i, T_i \le n$ and $S_i \ne T_i$.

Output Format

Output one integer in a single line, representing the required answer. If there are infinitely many possible values, output -1.

It is guaranteed that the answer is not $0$, i.e. there is at least one feasible solution.

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

4

3 2
2 1 2 1
2 2 3 1

-1

见附加文件的 subway3.in。 

见附加文件的 subway3.ans。

Hint

[Sample 1 Explanation]

Define an array $d[1..4]$, where $d[i]$ denotes the track length 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 total lengths are possible, so the answer is $4$.

[Sample 2 Explanation]

The track length from station $3$ to station $1$ clockwise can be any positive integer.

[Constraints and Hints]

• For $30\%$ of the testdata, $n, m \le 9$ and $L_i \le 5$ are guaranteed.
• For another $15\%$ of the testdata, $T_i$ is the first station after $S_i$ in the clockwise direction.
• For another $20\%$ of the testdata, $T_i$ is the second station after $S_i$ in the clockwise direction.
• For another $25\%$ of the testdata, $n, m \le 50$ are guaranteed.
• For $100\%$ of the testdata, $3 \le n \le 500$, $1 \le m \le 500$, and $1 \le L_i \le 10^9$ are guaranteed.

Translated by ChatGPT 5