My solution: each bit is independent so let us consider them separately.
Now notice that if the first row and colmn are already filled, the whole grid is uniquely determined.
Use a dsu to maintain the equality relationship between the positions and the final time complexity is $$$\mathcal O((n + q) \log V \alpha n)$$$.
I have tested the code in mashups and it runs 2499ms, which means that the constant is too big. Can any one help me to optimize the code?
Code
