克莱尔喜欢画线条。她收到一张纸,上面有 $$$n \times n$$$ 网格,并开始在上面画“线”。嗯——这里的“线”的概念不是我们通常想到的。克莱尔将每条线称为一组连续的垂直网格单元。当她画线时,这些单元格都被黑色墨水覆盖。最初,所有单元格都是白色的,画线会使其中一些单元格变成黑色。画了几条线后,克莱尔想知道:她可以用多少种方法将额外的白细胞着色为黑色,以便剩余的白细胞不会形成单个连接的组件。
如果两个单元共享一条边,则它们直接相连。如果存在单元格序列 $$$c_0, c_1, \ldots, c_k$$$ 且 $$$k > 1$$$ 使得 $$$c_0 = x$$$, $$$c_k = y$$$,并且对于每个 $$$i \in \{1, 2, \ldots, k\}$$$ 单元格,则两个单元格 $$$x$$$ 和 $$$y$$$ 间接连接$$$c_i$$$ 和 $$$c_{i-1}$$$ 直接相连。如果一组单元格中的每对单元格直接或间接连接,则该组单元格形成单个连接组件。
网格有 $$$n$$$ 行和 $$$n$$$ 列,索引都从 $$$1$$$ 到 $$$n$$$。克莱尔将画 $$$q$$$ 线。第 $$$i$$$ 行绘制在第 $$$y_i$$$ 列中,从第 $$$s_i$$$ 行到第 $$$f_i$$$ 行,其中 $$$s_i \leq f_i$$$ 对于每个 $$$i \in \{1, 2, \ldots, q\}$$$。请注意,至少有一根 $$$q$$$ 线经过的单元格颜色为黑色。下图显示了 $$$20\times 20$$$ 网格的示例,其中包含 $$$q=67$$$ 行。标有红星符号的网格单元指的是这样的单元:如果克莱尔将该单元涂成黑色,则所有白色单元不再形成单个连接的组件。
您可以假设,绘制 $$$q$$$ 线后,剩余的白色单元格形成具有至少三个白色单元格的单个连通分量。
输入
第一行正好包含一个整数$$$t$$$,表示测试用例的数量。对于每个测试用例,它以恰好包含两个整数 $$$n$$$ 和 $$$q$$$ 的行开头。这表明网格是 $$$n$$$ by $$$n$$$ 并且 Claire 在其上绘制了 $$$q$$$ 线。然后是 $$$q$$$ 行。对于每个 $$$i \in \{1, 2, \ldots, q\}$$$,$$$q$$$ 行中的第 $$$i$$$ 行恰好包含三个整数 $$$y_i$$$、$$$s_i$$$ 和 $$$f_i$$$。
- $$$1\let \le 125$$$
- $$$2\leq n \leq 10^9$$$
- $$$q\ge 1$$$;所有 $$$q$$$ 值的总和最多为 $$$10^5$$$。
- $$$1\leq y_i \leq n$$$
- $$$1\leq s_i \leq f_i \leq n$$$
- 至少有三个白细胞,所有白细胞形成一个连通分量。
输出
在一行上打印一个整数,指示 Claire 可以通过多少种方式将额外的白色单元格涂成黑色,以便其余的白色单元格不会形成单个连接组件。
示例
输入 #1
2 3 1 2 1 2 5 2 2 1 4 4 2 5
输出 #1
5 15