The first key observation is that process of ghosts removing moves from their routines is identical to the symmetric difference of the sets of moves each ghost performs (this is similar to the exclusive or operator). We can represent the moves a ghost performs as a binary integer with ~4~-bits (bitmask). Since there are at most ~16~ groups of ghosts, with each containing at most ~9~ ghosts, we can brute force all ~H^K~ possible assignments (where ~H~ is the number of ghost houses and ~K~ is the maximum size of a group) and determine for each assignment which moves will be performed in which house. This can be done by taking the bitwise ~xor~ of the bitmasks of the moves for each ghost. Be sure to ensure that at least half of the ghosts in that group are in the same house.

We then need to merge the results of the groups together. There are a number of ways this can be done. This editorial will walk through one of the more interesting interpretations of the problem.

We can represent the result of each group as a frequency array of the moves that are performed in each house. Since each move in each house is either performed once, or not at all, there are ~2^{M \times H}~ possible combinations (where ~M~ is the number of moves). This can be represented as a bitmask with ~M \times H~ bits. When merging two frequency arrays ~A~ and ~B~, we can see that if there are ~A[i]~ ways for a combination with mask ~i~ to occur in the first group, and ~B[j]~ ways for a combination with mask ~j~ to occur in the second group, then it contributes ~A[i] \times B[j]~ ways for a combination with mask ~i \oplus j~ to occur with both groups combined (~\oplus~ is the xor operator). This is similar to polynomial multiplication, with the exception that ~i \times j~ is now ~i \oplus j~. Since the size of the polynomials are quite large, the standard quadratic multiplication algorithm will take too long. In addition, the polynomials have enough nonzero terms, such that sparse multiplication will also take too long. One way to multiply polynomials quickly is using Fast Fourier Transforms. Fast Fourier Transforms can be modified to support the ~\oplus~ operator, as well as modular arithmetic. This is known as the Fast Walsh-Hadamard Transform. This will provide us the number of combinations a specific combination of moves will occur in each house, for all groups combined.

The sum of the scariness of the houses can then be recovered easily for each element in the merged frequency array. To answer the queries, we can maintain a prefix sum array after the merged frequency array is sorted by the sum of scariness of the houses. Each query can then be answered in ~\mathcal{O}(\log(2^{M \times H})) = \mathcal{O}(M \times H)~ time by binary searching the prefix sum array.

Time Complexity: ~\mathcal{O}(G \times ((H + K) \times H^K + M \times H \times 2^{M \times H}) + Q \times M \times H)~

Where ~G~ is the number of groups, ~K~ is the maximum size of a group, ~H~ is the number of haunted houses, ~M~ is the number of moves, ~N~ is the number of ghosts, and ~Q~ is the number of queries.

For this problem, ~G = 16~, ~K = 9~, ~H = 5~, and ~M = 4~.