Counting Valid Total Lengths of a Circular Subway Line

B City has a historic metro system. The X line is a circular route with n stations. The distance between any two adjacent stations is a positive integer. Xiaoxue has made m observations. Each observation is one of the following two types:

1. A minimum requirement: The total distance when travelling clockwise from station \(S_i\) to station \(T_i\) is at least \(L_i\). (Note that if \(S_i \le T_i\) the distance is \(d_{S_i} + d_{S_i+1} + \cdots + d_{T_i-1}\), and if \(S_i > T_i\) the distance is \(d_{S_i} + \cdots + d_n + d_1 + \cdots + d_{T_i-1}\).)
2. A maximum requirement: The clockwise distance from station \(S_i\) to station \(T_i\) is at most \(L_i\).

Every adjacent segment \(d_i\) (for \(1 \le i \le n\)) is a positive integer. Your task is to determine how many different values of the total length (i.e. \(S = d_1+d_2+\cdots+d_n\)) are possible such that there exists an assignment of positive integers \(d_1, d_2, \dots, d_n\) satisfying all the observations.

Note: Some observations may concern the full circle (i.e. when \(S_i = T_i\)); these directly impose constraints on \(S\). If there is no finite upper bound on \(S\) (i.e. infinitely many possible total lengths), output -1.

All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of stations and the number of observations).

Each of the next \(m\) lines contains four integers: type S T L. Here, type is either 1 or 2. If type = 1, it means the clockwise distance from station \(S\) to station \(T\) is at least \(L\); if type = 2, it means the distance is at most \(L\). The stations are numbered from 1 to \(n\). Note that when \(S > T\), the considered segment wraps around from station \(n\) to station 1.

outputFormat

Output a single integer, indicating the number of different valid total lengths of the circular line. If there are infinitely many valid total lengths, output -1.

sample

3 3
1 1 2 3
2 1 1 15
1 1 1 10

6