最近，小 Z 对冒泡排序产生了浓厚的兴趣。

下面是冒泡排序的伪代码：

输入: 一个长度为 n 的序列 a[1...n]
输出: a 从小到大排序后的结果
for i = 1 to n do:
    for j = 1 to n - 1 do
        if (a[j] > a[j + 1])
            交换 a[j] 与 a[j + 1] 的值

冒泡排序的交换次数被定义为在排序时进行交换的次数，也就是上面冒泡排序伪代码第六行的执行次数。他希望找到一个交换次数尽量少的序列。

题目描述

小 Z 所研究的序列均由非负整数构成。它的长度为 $n$，且必须满足 $m$ 个附加条件。其中第 $i$ 个条件为：下标在 $[L_i,R_i]$ 中的数，即 $a_{L_i},a_{L_{i+1}},\cdots ,a_{R_i}$ 这些数，其最小值恰好为 $V_i$。

他知道冒泡排序时常会超时。所以，他想要知道，在所有满足附加条件的序列中，进行冒泡排序的交换次数的最少值是多少。

输入格式

本题有多组数据。

输入的第一行包含一个正整数 $T$。

对于每组数据，第一行包含两个正整数 $n,m$。数据保证 $1\le n,m\le {10}^6$。

接下来 $m$ 行，每行三个非负整数 $L_i,R_i,V_i$，表示一组附加条件。数据保证 $1\le L_i\le R_i\le n$, $0\le V_i\le {10}^9$。

输出格式

输出共 $T$ 行，每行一个整数。

对于每组数据，如果存在满足这 $m$ 个附加条件的序列，则输出在所有满足附加条件的序列中，冒泡排序交换次数的最小值。如果不存在满足所有条件的序列，则输出 -1。

样例一

input

1
3 2
1 1 2022
2 3 39

output

1

explanation

这组数据的约束条件为 $a_1=2022,min\{a_2,a_3\}=39$。

若 $a_2=39$，且 $39\le a_3<2022$，则冒泡排序只有第一轮有交换操作，这一轮交换了 $a_1,a_2$ 和 $a_2,a_3$，总交换次数为 $2$。

若 $a_2=39$，且 $a_3\ge 2022$，则冒泡排序只有第一轮有交换操作，这一轮仅仅交换 $a_1,a_2$，总交换次数为 $1$。

若 $a_3=39$，且 $39<a_2<2022$，则冒泡排序算法第一轮交换 $a_1,a_2$ 和 $a_2,a_3$，第二轮交换 $a_1,a_2$。总交换次数为 $3$。

若 $a_3=39$，且 $a_2\ge 2022$，则冒泡排序算法第一轮交换 $a_2,a_3$，第二轮交换 $a_1,a_2$。总交换次数为 $2$。

因此，交换次数的最小值为 $1$。

样例二

见附件下载。

样例三

见附件下载。

这个样例满足测试点 $8\sim 10$ 的条件。

样例四

见附件下载。

这个样例满足测试点 $13\sim 14$ 的条件。

样例五

见附件下载。

这个样例满足测试点 $15\sim 16$ 的条件。

样例六

见附件下载。

这个样例满足测试点 $23\sim 25$ 的条件。

数据范围

本题共 $25$ 个测试点。全部测试点满足：$1\le T\le 1000$，$1\le \sum n,\sum m\le {10}^6$，$1\le L_i\le R_i\le n$，$0\le V_i\le {10}^9$。

其中 $\sum n,\sum m$ 分别表示所有测试点的 $n$ 的总和和 $m$ 的总和。$\sum n^2,\sum m^2,\sum n^3,\sum m^3$ 的含义类似。

• 特殊性质 A：对于 $1\le i\le m$，$0\le V_i\le 1$。
• 特殊性质 B：对于 $1\le i\le m$，$L_i=R_i$。
• 特殊性质 C：输入给出的 $m$ 个区间 $[L_i,R_i]$ 两两不相交。

时间限制：2s$\mathtt{\text{4s}}$

空间限制：$1\mathtt{\text{GB}}$

提示

本题的部分测试点输入量较大。我们建议你使用较为快速的读入方式。