As the manager of the Bajtcorp company, you are responsible for $n$ employees numbered from $1$ to $n$. You have determined that employee $i$ has an efficiency of $a_i$. Now, you would like to divide all employees into teams. Each team must consist of employees whose numbers form a contiguous range, and its efficiency is the sum of the efficiencies of the employees who are part of it.

Unfortunately, some employees have specific requirements regarding their team: they insist on working in a team together with their friends and refuse to work in a team with people they dislike. If even one of an employee's requirements is not met, their efficiency drops to $0$. You have collected $m$ pieces of information about these requirements, each of which is one of two types:

1. Employee $x_i$ wants to work in the same team as employee $y_i$.
2. Employee $x_i$ does not want to work in the same team as employee $y_i$.

Failure to meet such a requirement causes the efficiency of employee $x_i$ to drop to $0$. Note that if employee $x_i$ wants to work in the same team as employee $y_i$, it does not necessarily mean that employee $y_i$ wants to work in the same team as employee $x_i$. In other words, the collected requirements do not have to be symmetric.

Your task is to find a division into teams that maximizes the sum of the efficiencies of all teams.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 500\,000$, $0 \le m \le 1\,000\,000$) denoting the number of employees and requirements. The next line contains $n$ integers, where the $i$-th of them is $a_i$ ($1 \le a_i \le 10^9$) denoting the efficiency of employee $i$. The next $m$ lines contain information about the requirements. The $i$-th of these lines contains three integers $t_i, x_i, y_i$ ($1 \le t_i \le 2$, $1 \le x_i, y_i \le n$, $x_i \neq y_i$) denoting information of type $t_i$ regarding employees $x_i$ and $y_i$, where $t_i = 1$ denotes type 1 information (meaning employee $x_i$ wants to work in the same team as employee $y_i$), and $t_i = 2$ denotes type 2 information (meaning employee $x_i$ does not want to work in the same team as employee $y_i$).

Output

Your program should output a single line containing the maximum sum of the efficiencies of all teams.

Examples

Input 1

5 5
1 2 3 5 4
1 1 3
2 1 4
1 4 5
2 5 4
1 5 2

Output 1

11

Note 1

The optimal division is $\{1, 2, 3\}, \{4, 5\}$. Then at least one of the requirements of employee 5 is not met, so their efficiency drops to 0. The requirements of all other employees are met, so the sum of the efficiencies of all teams is $1 + 2 + 3 + 5 = 11$.

Sample tests

Test 0 is the example above. Additionally:

Test 1: $n = 10, m = 8, a_i = i$ for $i = 1, 2, \dots, 10$. Sequence $t_i$ is $1, 1, 1, 2, 2, 2, 2, 2$. Sequence $x_i$ is $2, 3, 5, 1, 4, 6, 8, 9$. Sequence $y_i$ is $3, 5, 7, 4, 6, 8, 9, 10$. The result is $52$.

Test 2: $n = 100, m = 197$, for $i$ being prime numbers $a_i = i$, while for $i$ not being prime numbers $a_i = 101 - i$. For $i = 1, 2, \dots, 99$ we have $t_i = 1, x_i = i + 1, y_i = i$, while for $i = 100, 101, \dots, 197$ we have $t_i = 2, x_i = i - 99, y_i = i - 97$. The result is $3437$.

Test 3: $n = 100\,000, m = 99\,999$, for $i = 1, 2, \dots, 100\,000$ we have $a_i = (1 + (i \pmod 7))$. For $i = 1, 2, \dots, 99\,999$ we have $t_i = 2, x_i = i, y_i = i + 1$. The result is $400\,000$.

Test 4: $n = 500\,000, m = 0, a_i = 1\,000\,000$ for $i = 1, 2, \dots, 500\,000$. The result is $5 \cdot 10^{11}$.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.