For the first subtask, a few initial observations are needed. Note that if ~x_i = x_j~ for some ~i~ and ~j~, then nodes ~i~ and ~j~ may be connected at no cost, even after updates. So multiple nodes with the same value may be discarded and there will be at most ~2^K~ important nodes. Another observation is that there are only ~2^K~ residues modulo ~2^K~, so we can precompute the answer for each of these residues and then answer each update in ~\mathcal{O}(1)~. With these in mind, a straightforward implementation of Kruskal's can pass in time.

Time Complexity: ~\mathcal{O}(N+Q+K\cdot 2^{3K})~

For the next subtask, the Kruskal's must be optimized to subquadratic time. Split the nodes into two sets: those with the largest bit, and those without. Note that because the edges are sorted by weight, the edges between nodes in the same set will always be considered before the edges between the two sets. To combine the two sets, only one edge is necessary (since each set is already connected) and this edge can be found by building a trie from one set and checking every node in the other set against the trie.

Time Complexity: ~\mathcal{O}(QNK^2)~

Note that the Kruskal's in the solution to the second subtask implicitly formed a binary tree. For the third subtask, we will focus on this structure. Consider the subtrees with height ~J~ from the bottom of the complete binary tree. Note that if ~32~ divides ~c~, then for ~J=5~, these subtrees will move but they themselves will not change. Then we can precompute the total weight within each of these subtrees, as well as the minimum weight between every two of these subtrees. Then for each update, we only need to apply the Kruskal's to the first ~K-J~ levels and use the precomputed values. Finally, since ~32~ divides ~c~, there are only ~2^{K-J}~ important residues mod ~2^K~.

Time Complexity: ~\mathcal{O}(J^2 \cdot 2^J + J\cdot 2^{2K-J}+K^2\cdot 2^{2(K-J)})~

For the final subtask, we build on this idea of unchanging subtrees of height ~J~. To force this condition in subtask 3, we can construct a sequence of ~c~'s which has most ~c~'s divisible by ~2^J~. For example, when ~K=4~, one such sequence of ~c~'s would be ~c=0, 2^2, 2^2, 2^2, 1, 2^2, 2^2, 2^2, 1, 2^2, 2^2, 2^2, 1, 2^2, 2^2, 2^2~ which covers all residues mod ~2^4~. However, even after constructing this sequence, we cannot simply apply the exact same idea as subtask 3. This is because we need to do the precomputing between every pair of subtrees for each time ~c~ is not divisible by ~2^J~, which is ~2^J~ times. This would lead to a time complexity of ~\mathcal{O}(J\cdot 2^{2K})~ for precomputing alone.

To deal with this, an optimization is necessary for the precomputation. Consider subtrees of height ~P~ in these subtrees of height ~J~. There are only ~2^{2^P}~ possible subtrees. The minimum edge weight between every two of these subtrees can be precomputed and this only needs to be done once. Then, these values are used in precomputing the values of subtrees of height ~J~, and then the solution from subtask 3 can be used.

Time Complexity: ~\mathcal{O}(P^2\cdot 2^{2^{P+1}} + J^2 \cdot 2^{2J} + J^2\cdot 2^{2K-P}+K^2 \cdot 2^{2K-J})~

In the model solution, we choose ~P=3, J=7~.