小青鱼有 $n$ 个珠子排成一个环，按顺时针方向从 $1$ 到 $n$ 编号。每个珠子可以被染成青色或白色。他用 $S(l, r)$ 表示区间 $I(l, r)$ 内青色珠子的数量，其中区间 $I(l, r)$ 的定义如下：

• 如果 $l \le r$，它包含编号为 $l, l + 1, \dots, r$ 的珠子。
• 如果 $l > r$，它包含编号为 $l, l + 1, \dots, n, 1, 2, \dots, r$ 的珠子（一个从 $n$ 绕回到 $1$ 的环形区间）。

他还没有决定将哪些珠子染成青色，但他写下了 $m$ 个希望最终染色方案满足的限制。总共有 $m$ 个限制，分为三种不同的类型，每个限制由一个四元组 $(t, l, r, v)$ 表示，其中 $t \in \{1, 2, 3\}$。这三种类型限制的含义如下：

• 类型 1 ($t = 1$)：$S(l, r)$ 必须至少为 $v$（即 $S(l, r) \ge v$）。
• 类型 2 ($t = 2$)：$S(l, r)$ 必须至多为 $v$（即 $S(l, r) \le v$）。
• 类型 3 ($t = 3$)：$S(l, r)$ 必须恰好为 $v$（即 $S(l, r) = v$）。

小青鱼想知道是否存在满足所有这些限制的染色方案。如果至少存在一种合法的染色方案，他还想知道有多少个区间 $I(l, r)$（$1 \le l, r \le n$）在所有合法的染色方案中都具有相同的 $S(l, r)$ 值。两个区间 $I(l_1, r_1)$ 和 $I(l_2, r_2)$ 被认为是不同的，当且仅当 $l_1 \neq l_2$ 或 $r_1 \neq r_2$。

输入格式

输入的第一行包含两个整数 $n$（$2 \le n \le 10^9$）和 $m$（$1 \le m \le 1000$），分别表示珠子的数量和限制的数量。

接下来的 $m$ 行描述所有的限制。这些行中的每一行都包含四个整数 $t, l, r, v$（$t \in \{1, 2, 3\}$，$1 \le l, r \le n$，$0 \le v \le L$，其中 $L = |I(l, r)|$ 是区间 $I(l, r)$ 内珠子的总数），描述一个类型为 $t$ 的限制。

输出格式

如果不存在合法的染色方案，输出单行，包含一个整数 $-1$。否则，输出单行，包含一个整数，表示在所有合法的染色方案中 $S(l, r)$ 值都相同的区间 $I(l, r)$ 的数量。

样例

输入样例 1

16 8
1 1 3 1
1 5 7 1
1 9 11 1
1 13 15 1
2 2 6 1
2 6 10 1
2 10 14 1
2 14 2 1

输出样例 1

128

输入样例 2

1000000000 1
2 114514 114513 0

输出样例 2

1000000000000000000

输入样例 3

100 3
3 1 10 1
3 91 100 1
3 81 20 2

输出样例 3

253

输入样例 4

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

输出样例 4

-1

说明

样例 1 说明

只有两种可能的染色方案（W = 白色，C = 青色）：

• CWWWCWWWCWWWCWWW
• WWCWWWCWWWCWWWCW

在 $16^2$ 个区间中，恰好有一半（即 $128$ 个区间）在两种染色方案中包含相同数量的青色珠子。

注意，虽然区间 $I(1, 16), I(2, 1), I(3, 2), \dots, I(16, 15)$ 都包含全部 $16$ 个珠子，但在计算答案时，它们被视为不同的区间。

在第二个样例中，唯一合法的染色方案是所有珠子均为白色。