Background

AHOI2021 Junior T4.

You may choose to skip the background part.

Xiaokeke found that the algorithms she learned were actually of little use in real life, and felt very depressed. Seeing this, Xiaoxue muttered a few words, “They should still be useful, right?”

“But what if they are useless? Algorithms are just a stepping stone to a famous university.”

“I disagree. The Flea King once told me that in future research or work, we will meet again some things from informatics competitions, although it may not be as hard as informatics competitions.

“Apart from practical benefits, doing informatics competitions also lets you enjoy a lot of the fun of thinking.”

“You are right. Every time in the exam I cannot solve a problem and start doubting whether the problem is wrong, after the exam when I read the editorial I always feel both annoyed and happy—why couldn’t I think of such a natural idea!”

A seed of a theoretical computer scientist quietly sprouted.

The sandstorm suddenly, as if by magic, dispersed. The two, who really could not sit still anymore, decided to go out and take the subway to wander around, getting off at will. Even without trying on purpose, Xiaoxue came up with an interesting problem on the subway. Can you solve it?

Problem 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