Path XOR on a GCD Graph

In the year 4202, the 2184th Weihai University Programming Contest was held. In the last problem you are given two positive integer sequences \(\{a_i\}\) and \(\{p_i\}\) as well as a sequence of triples \(\{u_i, v_i, w_i\}\). They define an undirected graph on \(n\) vertices (indexed from 1) where an edge exists between vertex \(i\) and vertex \(j\) if and only if \(\gcd(a_i,a_j)>1\). Each vertex \(i\) carries a weight of \(p_i\>.

Your task is: for each triple \((u,v,w)\), determine whether there exists a simple path from \(u\) to \(v\) whose XOR sum (i.e. \(p_{v_1}\oplus p_{v_2}\oplus\cdots\oplus p_{v_k}\)) of the vertex weights along the path equals \(w\). Note that the path’s vertices are considered exactly once and the XOR operation is taken in binary.

Hint: In any connected component, choose a spanning tree and define for each vertex \(v\) a value \(d(v)\) which is the XOR sum along the unique tree path from the tree root to \(v\) (with the root having \(d(root)=p_{root}\)). Then the XOR sum on the unique tree path between two vertices \(u\) and \(v\) is given by

[ d_{tree}(u,v)=d(u)\oplus d(v)\oplus p(L)]

where \(L=\mathrm{LCA}(u,v)\) in the spanning tree. Non‐tree edges introduce cycles which let you alter the tree–path value by any element in the cycle space. If you compute a linear basis (over \(\mathbf{F}_2\)) for the XOR values of all cycles in each connected component, you can decide whether there is some combination that changes \(d_{tree}(u,v)\) to \(w\). In other words, for query \((u,v,w)\), if \(u\) and \(v\) are in the same connected component and \(w\oplus d_{tree}(u,v)\) can be reduced to \(0\) using the cycle basis then the answer is "Yes"; otherwise, "No".

inputFormat

The first line of input contains two integers \(n\) and \(q\) (the number of vertices and the number of queries).

The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\).

The third line contains \(n\) positive integers \(p_1, p_2, \dots, p_n\) which are the weights of the vertices.

Then \(q\) lines follow. Each of these contains three integers \(u, v, w\) representing a query.

outputFormat

For each query, print a single line with either Yes or No indicating whether there exists a simple path from \(u\) to \(v\) with vertex weights having an XOR sum equal to \(w\).

sample

3 3
2 3 4
1 2 3
1 3 2
2 2 2
1 2 0

Yes
Yes
No