The fifirst line of the input contains a single integer T (1 ≤ T ≤ 4), the number of test cases.
For each case, the fifirst line of the input contains two integers n and m (1 ≤ n ≤ 500 000, 1 ≤ m ≤ 10 000),
denoting the number of nodes and the number of operations.
The second line of the input contains n integers col1, col2, . . . , coln (1 ≤ coli ≤ n), denoting the initial
color of each node.
Each of the following n n 1 lines contains two integers ui and vi (1 ≤ ui
, vi ≤ n, ui = vi), denoting an
bidirectional edge between the ui-th node and the vi-th node.
Each of the next m lines describes an operation in formats described in the statement above, except that
some parameters are encrypted in order to enforce online processing.
Let cnt be the number of queries that you answered “Yes” before in this test case. Note that cnt should
be reset to 0 in each new test case. For each operation, x, y, a, b, c and d are encrypted. The actual values
of x, y, a, b, c and d are x ⊕ cnt, y ⊕ cnt, a ⊕ cnt, b ⊕ cnt, c ⊕ cnt and d ⊕ cnt. In the expressions above, the
symbol “⊕” denotes the bitwise exclusive-or operation. Also note that the constraints described in the
statement above apply to the corresponding parameters only after decryption, the encrypted values are
not subject to those constraints.
It is guaranteed that f(a, b) ≥ 2f(c, d) or f(c, d) ≥ 2f(a, b) always holds for each query