Building a Binary Grid

For $N \geq 5$, initially fill the rows with 0, 1, 0, 1, and so on. Move right when the next character is equal, and move one row up or down when it changes. Invert the first column so that both fully alternating strings have a vertical path.

Inverting that column breaks the two constant strings, so change $(2,N)$ to 0 and $(3,N)$ to 1. These cells complete paths for 00...0 and 11...1. Strings with exactly one change use rows 4 and 5. Strings with at least two changes can be placed without reaching the modified final-column cells.

For $N \leq 4$, there are at most $16$ cells. Enumerate all grids and use depth-first search to find the required paths. Constructing all reported paths takes $O(NQ)$ time apart from this constant-size search.