Sequence Transformation using Pairwise Operations

You are given two integer sequences of length \(n\): an initial sequence \(a_{1 \dots n}\) and a target sequence \(b_{1 \dots n}\). You are also given \(m\) operations, each described by a triple \((t_i, u_i, v_i)\). There are two types of operations:

• If \(t_i = 1\): You can either add 1 to both \(a_{u_i}\) and \(a_{v_i}\) or subtract 1 from both.
• If \(t_i = 2\): You can either add 1 to \(a_{v_i}\) and subtract 1 from \(a_{u_i}\), or add 1 to \(a_{u_i}\) and subtract 1 from \(a_{v_i}\). (Note that if \(u_i = v_i\), this operation has no effect.)

You may perform any operation any number of times and in any order. Determine whether it is possible to transform sequence \(a\) into sequence \(b\) using the given operations.

Observation

Define \(d_i = b_i - a_i\). Each operation affects the elements in one of the following ways:

• Type 1: Changes \(a_{u}\) and \(a_{v}\) by either \(+1\) or \(-1\) simultaneously. Hence, the total change in the sum for the indices involved is \(\pm2\).
• Type 2: Transfers one unit from one index to the other, so the overall sum of the two indices remains unchanged.

If we view the indices as vertices of a graph and add an edge between \(u_i\) and \(v_i\) for each operation, then within each connected component:

• If the component does not contain any type 1 operation (i.e. only type 2 operations were available), the sum of \(d_i\) in that component must be exactly 0.
• If the component contains at least one type 1 operation, then the total change can be adjusted by multiples of 2, so the sum of \(d_i\) in that component must be even.

Also, for isolated vertices (vertices not affected by any operation), \(d_i\) must be 0.

Your task is to output YES if the transformation is possible, and NO otherwise.

inputFormat

The input is given as follows:

 n m
 a1 a2 ... an
 b1 b2 ... bn
 t1 u1 v1
 t2 u2 v2
 ...
 tm um vm

Here, \(n\) and \(m\) are integers representing the length of the sequences and the number of operations respectively. The next two lines contain \(n\) integers each representing the sequences \(a\) and \(b\). Then \(m\) lines follow, each containing three integers \(t_i, u_i, v_i\) describing an operation.

outputFormat

Output a single line containing YES if it is possible to transform sequence \(a\) into \(b\) using the given operations, otherwise output NO.

sample

3 2
1 2 3
2 1 3
2 1 2
2 2 3

YES