You are given an array $a$ of $n$ positive integers, and $m$ sub-array constraints that must be satisfied.

A subarray of the array $a$ is a sequence of consecutive elements of it: $a_l$,  $a_{l+1}$, $\dots$, $a_r$, for some integers $(l,  r)$ such that $1 \leq l \leq r \leq  n$.  

Each constraint requires the product of a subarray to have a specific parity (either even or odd).

Your task is to change the minimum number of elements in the array $a$ so that all the constraints are satisfied if that is possible.

The first line of input contains a single integer $T$ ($1 \le T \le 100$), the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$), the size of the array $a$ and the number of constraints, respectively.

The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$), the elements of the array.

Each of the following $m$ lines contains three integers $l$, $r$, and $p$ ($1 \le l \le r \le n$, $p \in {0, 1})$, representing a constraint on the subarray $[l, r]$. If $p$ is $0$, the product of the subarray elements $a_l \times a_{l+1} \times \dots \times a_r$ must be even, otherwise it must be odd.

The total sums of $n$ and $m$ over all test cases do not exceed $2\times10^6$.

For each test case, on a single line, if it is impossible to satisfy all the constraints, print $-1$. Otherwise, print the minimum number of elements that need to be changed.