Problem Description

Little D has an integer sequence $a_{1 \dots n}$ of length $n$. She wants to transform it into the sequence $b_i$ through several operations.

Little D has $m$ types of operations to choose from. The $i$-th operation can be described by a triple $(t_i, u_i, v_i)$:

• If $t_i = 1$, then she can either increase both $a_{u_i}$ and $a_{v_i}$ by $1$, or decrease both by $1$.
• If $t_i = 2$, then she can either decrease $a_{u_i}$ by $1$ and increase $a_{v_i}$ by $1$, or increase $a_{u_i}$ by $1$ and decrease $a_{v_i}$ by $1$. Therefore, when $u_i = v_i$, this operation is equivalent to doing nothing.

Little D can perform the operations in any order, and each operation can be used an unlimited number of times. Now you are given the sequences and all operations. Please determine whether there exists a plan to transform $a_i$ into $b_i$. It is guaranteed that both sequences have length $n$. If such a plan exists, output YES; otherwise, output NO.

Input Format

This input contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains two integers $n, m$, representing the sequence length and the number of operation types.
• The second line contains $n$ integers representing $a_i$.
• The third line contains $n$ integers representing $b_i$.
• The next $m$ lines each contain three integers $t_i, u_i, v_i$. Line $i$ describes operation $i$.

Note: The same triple $(t_i, u_i, v_i)$ may appear multiple times in the input.

Output Format

For each test case, output one line containing a string YES or NO, indicating the answer.

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

YES
YES
YES

Hint

Explanation for Sample 1

For the first test case: use operation $1$ once.
For the second test case: use operation $1$ three times.
For the third test case: use operation $1$ three times to increase both $a_1$ and $a_2$ by $3$, then use operation $2$ once to increase both $a_1$ and $a_3$ by $1$.

Constraints and Notes

For test points $1 \sim 5$: $n = 2$, $m = 1$, $a_i, b_i \le 99$, $u_1 \ne v_1$, $t_1 = 1$.
For test points $6 \sim 10$: $n = 2$, $m = 1$, $a_i, b_i \le 99$, $u_1 \ne v_1$, $t_1 = 2$.
For test points $11 \sim 12$: $n = 2$, $a_i, b_i \le 99$, $u_i \ne v_i$.
For test points $13 \sim 16$: $t_i = 2$.
For test point $17$: $n, m \le 20$.
For test point $18$: $n, m \le 10^3$.
For all test points: $1 \le T \le 10$, $1 \le n, m \le 10^5$, $1 \le a_i, b_i \le 10^9$, $t_i \in \{1, 2\}$, $1 \le u_i, v_i \le n$.

Translated by ChatGPT 5