Given a sequence of positive integers $[a_1, \dots, a_n]$ and $m$ triples $(l_j, r_j, v_j)$ ($1 \le j \le m$).

You need to find a sequence of positive integers $[b_1, \dots, b_n]$ such that for all $1 \le j \le m$, $\min_{l_j \le k \le r_j} b_k = v_j$. Based on this, minimize the value of $\sum_{1 \le i \le n} |a_i - b_i|$. You only need to output the minimum value of $\sum_{1 \le i \le n} |a_i - b_i|$.

If no sequence $b$ satisfies all triples, output -1.

Input

This problem supports multiple test cases. The first line contains a positive integer $t$ ($1 \le t \le 1000$), representing the number of test cases. The following lines contain $t$ test cases.

For each test case: The first line contains two integers $n, m$ ($1 \le n \le 5 \times 10^5, 1 \le m \le 5 \times 10^5$). The next line contains $n$ positive integers $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$). The next $m$ lines each contain three positive integers $l_j, r_j, v_j$ ($1 \le l_j \le r_j \le n, 1 \le v_j \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$, and the sum of $m$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

1
3 2
2023 40 41
1 1 2022
2 3 39

Output 1

2

Note

One optimal solution for the sample is $b = [2022, 39, 41]$.