飞行训练

Problem Description

小 Q 是一名见习飞行员，他正在进行飞行训练。 世界上一共有 $n$ 个机场，编号依次为 $1,2,\dots,n$。在这些机场的停机坪上，停放着 $m$ 架飞机。第 $i$ 架飞机位于 $x_i$ 号机场，如果小 Q 驾驶它起飞，将被允许降落在编号在 $[l_i,r_i]$ 的任意机场。一架飞机的燃料只允许它被使用一次。 小 Q 每天将从任意机场 $x$ 挑选一架飞机 $a$ 起飞，合法地降落在机场 $y$（$y\neq x$），然后挑选机场 $y$ 的一架飞机 $b$ 起飞，合法地降落在机场 $z$（$z\neq x$, $z\neq y$），最后挑选 $z$ 的一架飞机 $c$ 起飞，合法地降落在机场 $x$，构成一天的训练计划。 小 Q 现在想知道，一共有多少种不同的训练计划？两个计划被认为不同当且仅当六元组（$a,b,c,x,y,z$）不同。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 15$），表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$（$3\leq n\leq 50\,000$, $1\leq m\leq 50\,000$），分别表示机场和飞机的数量。 接下来 $m$ 行，每行三个正整数 $x_i,l_i,r_i$（$1\leq x_i\leq n$, $1\leq l_i\leq r_i\leq n$, $x_i\notin[l_i,r_i]$），分别描述每架飞机。 输入数据保证 $\sum n\leq 200\,000$ 且 $\sum m\leq 200\,000$。

Output

对于每组数据输出一行一个整数，即本质不同的训练计划数量。

Sample Input

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

Sample Output

3
15

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）