9446 - 地铁

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 512 MB

题目背景

AHOI2021 初中组 T4

小可可发现自己所学算法在生活中其实无大用，感觉十分沮丧。小雪见状还是嘀咕了几句“应该还是有用的吧”。

“不过没用又怎么样呢？算法只不过是一块名牌大学的敲门砖罢了。”

“你这话我就不同意了。跳蚤国王曾经和我说过，以后科研或者工作中我们还会和信息学竞赛中的某些东西重逢，虽然可能不会再有信息学竞赛这么难。

“除开功利的因素之外，搞信息学竞赛还是能享受到很多思考的乐趣的。”

“你说的也对。每次我在考场上不会做质疑这题是不是有问题的时候，考后看题解总是懊恼又快乐——这么自然的思路我怎么想不到呢！”

一颗理论计算机科学家的种子悄悄萌芽。

沙尘暴突然神奇般的散去了。实在坐不下去的两人决定出门坐地铁瞎逛，随性下车。即使没有刻意为之，小雪在地铁上却想出了一个有意思的问题，你能解决吗？

题目描述

B 市的地铁历史悠久，小雪和小可可乘坐的 X 号线是环形路线，上面分布着 $n$ 个车站，相邻两个车站之间的铁路长度为正整数。现在小雪进行了一些观察，得到了 $m$ 条信息，第 $i$ 条信息是如下形式之一：

环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不小于一个给定的值 $L_i$ （ $S_i$ 和 $T_i$ 是两个车站）；
环上顺时针由 $S_i$ 到 $T_i$ 的一段距离不大于一个给定的值 $L_i$ 。

小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。

输入

第一行两个空格隔开的正整数 $n$ 和 $m$ 。

下面 $m$ 行，第 $i$ 行四个空格隔开的正整数 $type_i,S_i,T_i,L_i$ ，其中 $type_i \in {1,2}$ 表示信息的类型。车站顺时针编号为从 1 开始的连续整数。保证 $1 \le S_i,T_i \le n$ 且 $S_i \ne T_i$ 。

输出

仅一行一个整数，表示所求答案。如果有无穷种取值，请输出 -1。

保证答案不为 0，即至少有一种可能的方案。

样例

输入

输出

输入

3 2
2 1 2 1
2 2 3 1

输出

-1

输入

30 70
2 28 30 30569345
1 1 3 45749841
1 30 2 60746327
1 19 21 54601258
2 9 11 47547052
2 15 17 31218136
1 12 14 36221033
2 21 23 62072739
1 28 30 30569345
2 6 8 71171000
1 26 28 42821635
2 16 18 32716292
1 8 10 77405635
1 24 26 46501180
1 25 27 14162571
2 18 20 35059179
2 3 5 77223051
2 23 25 70374293
2 15 17 31218136
2 18 20 35059179
1 6 8 71171000
1 18 20 35059179
2 14 16 30396740
2 11 13 70220566
2 22 24 68738228
1 26 28 42821635
2 23 25 70374293
1 10 12 49225612
2 25 27 14162571
1 24 26 46501180
1 24 26 46501180
2 29 1 49741058
2 19 21 54601258
1 9 11 47547052
1 13 15 24396814
1 17 19 22560151
2 11 13 70220566
2 29 1 49741058
2 8 10 77405635
1 10 12 49225612
2 17 19 22560151
2 5 7 69282017
1 18 20 35059179
1 17 19 22560151
1 5 7 69282017
2 24 26 46501180
2 7 9 63033397
1 30 2 60746327
2 12 14 36221033
1 17 19 22560151
2 28 30 30569345
1 4 6 60131540
2 29 1 49741058
1 1 3 45749841
1 9 11 47547052
2 18 20 35059179
2 4 6 60131540
1 24 26 46501180
1 11 13 70220566
1 3 5 77223051
1 1 3 45749841
1 26 28 42821635
2 26 28 42821635
1 2 4 44236112
2 1 3 45749841
1 18 20 35059179
1 3 5 77223051
2 3 5 77223051
2 4 6 60131540
1 15 17 31218136

输出

181215177

来源

安徽省选(AHOI2021)