Background

Recently, Xiao Z has developed a keen interest in bubble sort. The pseudocode for bubble sort is as follows:

1 Input: a sequence a[1...n] of length n
2 Output: the result of sorting a in non-decreasing order
3 for i = 1 to n do:
4     for j = 1 to n - 1 do
5         if (a[j] > a[j + 1])
6             swap the values of a[j] and a[j + 1]

The number of swaps in bubble sort is defined as the number of times the swap operation is performed, which is the number of times line 6 in the pseudocode above is executed. He wants to find a sequence that minimizes this number of swaps.

Description

The sequences studied by Xiao Z consist of non-negative integers. The sequence has length $n$ and must satisfy $m$ additional conditions. The $i$-th condition is: the minimum value among the numbers with indices in $[L_i, R_i]$, i.e., $a_{L_i}, a_{L_i+1}, \dots, a_{R_i}$, is exactly $V_i$.

He knows that bubble sort often times out. Therefore, he wants to know the minimum number of swaps required for bubble sort among all sequences that satisfy the additional conditions.

Input

The input is read from the file bubble.in. There are multiple test cases in this problem. The first line contains a positive integer $T$. For each test case, the first line contains two positive integers $n, m$. It is guaranteed that $1 \le n, m \le 10^6$. The next $m$ lines each contain three positive integers $L_i, R_i, V_i$, representing an additional condition. It is guaranteed that $1 \le L_i \le R_i \le n$ and $0 \le V_i \le 10^9$.

Output

The output is written to the file bubble.out. Output $T$ lines in total, each containing one integer. For each test case, if there exists a sequence satisfying these $m$ additional conditions, output the minimum number of swaps for bubble sort among all such sequences. If no sequence satisfies all conditions, output $-1$.

Examples

Input 1

1
3 2
1 1 2022
2 3 39

Output 1

1

Note 1

The constraints for this data are $a_1 = 2022$ and $\min\{a_2, a_3\} = 39$. If $a_2 = 39$ and $39 \le a_3 < 2022$, bubble sort only performs swaps in the first pass, swapping $a_1, a_2$ and $a_2, a_3$, for a total of 2 swaps. If $a_2 = 39$ and $a_3 \ge 2022$, bubble sort only performs swaps in the first pass, swapping only $a_1, a_2$, for a total of 1 swap. If $a_3 = 39$ and $39 < a_2 < 2022$, bubble sort swaps $a_1, a_2$ and $a_2, a_3$ in the first pass, and $a_1, a_2$ in the second pass. The total number of swaps is 3. If $a_3 = 39$ and $a_2 \ge 2022$, bubble sort swaps $a_2, a_3$ in the first pass and $a_1, a_2$ in the second pass. The total number of swaps is 2. Therefore, the minimum number of swaps is 1.

Example 2

See bubble/bubble2.in and bubble/bubble2.ans in the contestant directory.

Example 3

See bubble/bubble3.in and bubble/bubble3.ans in the contestant directory. This example satisfies the conditions for test cases 8 to 10.

Example 4

See bubble/bubble4.in and bubble/bubble4.ans in the contestant directory. This example satisfies the conditions for test cases 13 to 14.

Example 5

See bubble/bubble5.in and bubble/bubble5.ans in the contestant directory. This example satisfies the conditions for test cases 15 to 16.

Example 6

See bubble/bubble6.in and bubble/bubble6.ans in the contestant directory. This example satisfies the conditions for test cases 23 to 25.

Constraints

There are 25 test cases in total. All test cases satisfy: $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$.

Here $\sum n$ and $\sum m$ represent the sum of $n$ and $m$ over all test cases, respectively. The meanings of $\sum n^2, \sum m^2, \sum n^3, \sum m^3$ are similar.

Special Property A: For $1 \le i \le m$, $0 \le V_i \le 1$. Special Property B: For $1 \le i \le m$, $L_i = R_i$. Special Property C: The $m$ intervals $[L_i, R_i]$ given in the input are pairwise disjoint.

Note

Some test cases for this problem have large input sizes. We recommend using fast I/O methods.