Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

For her birthday Alice received an interesting gift from her friends – The Light Square.…

  1. User

    For her birthday Alice received an interesting gift from her friends – The Light Square. The Light Square game is played on an N × N lightbulbs square board with a magical lightbulb bar of size N × 1 that has magical properties. At the start of the game some lights on the square board and magical bar are turned on. The goal of the game is to transform the starting light square board pattern into some other pattern using the magical bar without rotating the square board. The magical bar works as follows:

    It can be placed on any row or column

    The orientation of the magical lightbulb must be left to right or top to bottom for it to keep its magical properties

    The entire bar needs to be fully placed on a board

    The lights of the magical bar never change

    If the light on the magical bar is the same as the light of the square it is placed on it will switch the light on the square board off, otherwise it will switch the light on

    The magical bar can be used an infinite number of times

    Alice has a hard time transforming her square board into the pattern Bob gave her. Can you help her transform the board or let her know it is impossible? If there are multiple solutions print any. Input

    The first line contains one positive integer number N\ (1 ≤ N ≤ 2000) representing the size of the square board.

    The next N lines are strings of length N consisting of 1's and 0's representing the initial state of the square board starting from the top row. If the character in a string is 1 it means the light is turned on, otherwise it is off.

    The next N lines are strings of length N consisting of 1's and 0's representing the desired state of the square board starting from the top row that was given to Alice by Bob.

    The last line is one string of length N consisting of 1's and 0's representing the pattern of the magical bar in a left to right order.

    Output

    Transform the instructions for Alice in order to transform the square board into the pattern Bob gave her. The first line of the output contains an integer number M\ (0 ≤ M ≤ 10^5) representing the number of times Alice will need to apply the magical bar.

    The next M lines are of the form "col X" or "row X", where X is 0-based index of the matrix, meaning the magical bar should be applied to either row X or column X. If there is no solution, print only -1. In case of multiple solutions print any correct one.

    Examples

    Input

    2 11 11 00 01 11

    Output

    -1

    Input

    2 10 00 00 00 10

    Output

    1 row 0

    Input

    3 110 011 100 100 011 100 100

    Output

    3 row 0 col 0 col 1

    Note

    Example 1: It is impossible to transform square board from one format to another

    Example 2: Magic bar can be applied on first row or column.

  2. DeepSeek Assistant

    We need to understand the problem: We have an N x N board of lights (binary). We have a magical bar of size N x 1, with a fixed pattern (string of length N) given. The bar can be placed on any row or column, oriented left-to-right for rows (so the bar's first light corresponds to the first column of that row) or top-to-bottom for columns (so the bar's first light corresponds to the first row of that column). The bar is fully placed on the board. The bar's lights never change. When we apply the bar, for each cell in the row (or column) we compare the bar's light at that position (the i-th in its pattern) with the current light on the board. If they are the same, the board light is switched off (set to 0); otherwise, switched on (set to 1). In other words, it toggles the board light if bar's bit is 1? Let's formalize: Let board value b ∈ {0,1}, bar value a ∈ {0,1}. Operation: new b = b XOR? Actually: if a == b then b becomes 0; else becomes 1. So new b = NOT (a == b)? Let's compute truth table: a=0,b=0 => same -> 0. a=0,b=1 => different -> 1. a=1,b=0 => different -> 1. a=1,b=1 => same -> 0. So new b = a XOR b? Check: 0 xor 0 =0, 0 xor 1=1, 1 xor 0=1, 1 xor 1=0. Yes exactly. So operation is XOR with bar pattern. Because a XOR b yields 1 when they differ, 0 when same. Wait: new b = a XOR b? For a=0,b=0 -> 0. Good. For a=0,b=1 -> 1. For a=1,b=0 -> 1. For a=1,b=1 -> 0. So indeed new b = a XOR b. So applying bar to a row/column does b := b XOR a (where a is bar pattern aligned to that row/col). And the bar pattern is same for all rows? But note: For row placement, the bar pattern is used as given (left-to-right). For column placement, the bar pattern is used as given but oriented top-to-bottom. So the bar pattern is a 1D array of length N. So operation on row i: for each column j, board[i][j] ^= bar[j] (where bar[j] is j-th character). Operation on column j: for each row i, board[i][j] ^= bar[i].

    So essentially, we have an initial matrix A (N x N, bits), and desired matrix B. We can apply operations: add (XOR) a fixed vector to a row (the bar vector r, where r[j] = bar[j]), or add a fixed vector to a column (the bar vector c, where c[i] = bar[i]). Actually row operation adds the same vector across the row (the bar pattern), column operation adds the bar pattern as a column vector. So we have linear operations over GF(2). We need to find a sequence (order independent? Since XOR is commutative, applying same row multiple times cancels? Actually applying twice would be (b xor a) xor a = b, so each row/column operation toggles the board with the given pattern. Since we can apply infinite times, we can treat each row and each column either applied an odd number of times (effectively once) or even times (effectively zero). So we have binary variables x_i for each row i (0 ≤ i < N), indicating whether we apply bar to that row (once, or odd times), and y_j for each column j (0 ≤ j < N), indicating whether we apply bar to that column. The order doesn't matter; the final state after applying all chosen row and column operations is: For each cell (i,j), initial A[i][j] gets XORed with (x_i * bar[j]) XOR (y_j * bar[i]). Because row i contributes bar[j] if x_i=1, column j contributes bar[i] if y_j=1. So final value = A[i][j] XOR (x_i * bar[j]) XOR (y_j * bar[i]) should equal B[i][j]. This gives N^2 equations over GF(2):

    A[i][j] XOR B[i][j] = (x_i * bar[j]) XOR (y_j * bar[i]).

    Let's define D[i][j] = A[i][j] XOR B[i][j] (the required delta). Then we need:

    D[i][j] = (x_i ∧ bar[j]) XOR (y_j ∧ bar[i]).

    Where ∧ is AND (since multiplication mod 2, i.e., product of bits). Write as:

    D[i][j] = (x_i * bar_j) + (y_j * bar_i) mod 2.

    We have unknowns x_i (N) and y_j (N). Given bar vector known of length N (bits). Need to find binary vectors x, y satisfying these equations.

    Constraints: N up to 2000, so N^2 = 4 million, but we can't solve naive linear system of N^2 equations with 2N unknowns. However the structure is special.

    We can rewrite:

    D[i][j] XOR (x_i * bar_j) XOR (y_j * bar_i) = 0.

    Alternatively, think of it as:

    D[i][j] = x_i * bar_j + y_j * bar_i. (mod 2)

    Consider cases based on bar_i and bar_j.

    If bar_i = 0 and bar_j = 0, then RHS = 0. So D[i][j] must be 0. If not, impossible.

    If bar_i = 0, bar_j = 1: then RHS = x_i * 1 + y_j * 0 = x_i. So D[i][j] = x_i.

    If bar_i = 1, bar_j = 0: then RHS = x_i0 + y_j1 = y_j. So D[i][j] = y_j.

    If bar_i = 1, bar_j = 1: then RHS = x_i + y_j (mod 2). So D[i][j] = x_i XOR y_j.

    Thus we have constraints linking x_i, y_j based on bar pattern.

    Observations: For positions where bar_i = 0, bar_j = 1, D[i][j] must equal x_i, and note that for fixed i, for all j such that bar_j = 1, D[i][j] must be same value (equal to x_i). Because from that equation, for any j with bar_j=1 and bar_i=0, x_i is determined by D[i][j]; they must all be consistent. Similarly, for bar_i=1, bar_j=0, D[i][j] = y_j, so for fixed j, all i with bar_i=1 must give same y_j.

    Also for bar_i=1, bar_j=1, D[i][j] = x_i XOR y_j, which must be consistent with previously determined x_i and y_j.

    And for bar_i=0, bar_j=0, D[i][j] must be 0; otherwise impossible.

    Thus we can try to determine x_i and y_j from the equations involving D.

    Plan:

    Let bar array b[0..N-1] bits.

    First, check all (i,j) with b[i]==0 and b[j]==0: require D[i][j]==0; else impossible.

    Second, for each i with b[i]==0: For any j with b[j]==1, we get x_i = D[i][j]. But we need consistency: For that i, all such D[i][j] must be equal. So we can compute a candidate x_i from first such j; if any other j gives different, impossible. If there is no j with b[j]==1? Then x_i is not constrained by these equations? But note other equations may involve x_i? For i where b[i]==0, x_i only appears in equations where bar_j=1 (since when bar_i=0, bar_j=1 gives x_i; and when bar_i=1, bar_j=1 gives x_i XOR y_j; but if b[i]=0, then in that case bar_i=0 so that case is not (1,1). Actually (1,1) requires both bar_i=1 and bar_j=1. So if b[i]=0, x_i does not appear in (1,1) equations because those require bar_i=1. So x_i only appears in equations with bar_i=0 and bar_j=1. So if there is no j with b[j]=1, then N= ? Could be possible if b has no 1's? Then bar is all zeros. Then bar pattern all zeros: row/col operations XOR with zero vector, i.e., no effect. So only possible if A==B. In that case any x,y are irrelevant? Actually if bar all zeros, operations do nothing, so only solvable if A=B, and we can output M=0 (or any with zero operations). But x_i and y_j can be arbitrary but we don't need to output them; we just need sequence. So M=0 is fine. But we need to handle consistent: If bar all zeros, then D must be zero matrix for solvability. Good.

    Similarly, for each j with b[j]==0: For any i with b[i]==1, we get y_j = D[i][j] (since bar_i=1, bar_j=0). Need consistency across i for same j; if any mismatch, impossible. If no i with b[i]=1, then y_j not constrained by these; but may appear elsewhere? For j with b[j]=0, y_j appears only in equations with bar_i=1, bar_j=0, as above. So if b vector has no 1's, then no constraints.

    Now for i with b[i]==1, x_i appears in equations: (i, j) with b[j]=1 gives x_i XOR y_j = D[i][j]. Also maybe with b[j]=0? That gave y_j = D[i][j] earlier, which doesn't involve x_i. So x_i only appears in (1,1) equations. Similarly y_j with b[j]=1 appears only in (1,1) equations.

    Thus after we might have determined some x_i from those where b[i]=0 (if any 1 in bar), and some y_j from those where b[j]=0. For indices with b[i]=1, x_i unknown; for indices with b[j]=1, y_j unknown. Then we have constraints from (1,1) cells: for all i with b[i]=1, j with b[j]=1, we have D[i][j] = x_i XOR y_j.

    This is reminiscent of a system where we need to assign binary values to x_i (for i in set S = {i | b[i]=1}) and y_j (for j in set T = {j | b[j]=1}) such that D[i][j] XOR x_i XOR y_j = 0. This is like we have a matrix M[i][j] = D[i][j] (given) and we need to find row bits u_i and column bits v_j such that M = u_i XOR v_j (i.e., M = u ⊕ v^T? Actually M[i][j] = u_i XOR v_j). That's possible if and only if for any i1,i2,j1,j2 we have M[i1][j1] XOR M[i1][j2] XOR M[i2][j1] XOR M[i2][j2] = 0. In other words, M is of rank at most 1 as a sum of row and column vectors. Since we have N up to 2000, we can solve by picking arbitrary assignments.

    Approach: If S (indices where bar=1) is nonempty, choose an arbitrary index i0 in S. Then set u_{i0} arbitrarily (say 0). Then for each j in T, we have u_{i0} XOR v_j = M[i0][j] => v_j = M[i0][j] XOR u_{i0}. Then for each i in S, for any j in T (say same j), we have u_i XOR v_j = M[i][j] => u_i = M[i][j] XOR v_j. This must be consistent across all j; we need to check that. So we can compute u_i from the first j (or any) and then verify for all j that M[i][j] = u_i XOR v_j. If any mismatch, impossible.

    Alternatively, we can treat the system as a bipartite graph. But the simple check with i0 works.

    But also there may be interactions with previously determined x_i for b[i]=0 and y_j for b[j]=0. However note that those x_i and y_j don't appear in (1,1) equations, so they are independent.

    Also, note that there is possibility of no j with b[j]=1 but some i with b[i]=1? That can't happen because if there is any i with b[i]=1, then there is at least one j? Actually j indexes columns, so if there is any index with bar=1, then both rows and columns share the same bar pattern; it's possible that bar has some 1s. So both S (rows) and T (columns) are same set? Actually bar is a 1D array; for rows, the pattern is applied across columns; for columns, applied across rows. So the indices of bar correspond to columns for row operations, and to rows for column operations. So S = set of indices i where b[i]=1; T = set of indices j where b[j]=1. They are essentially the same set of positions in the bar, but used as rows and columns. So if b has at least one 1, then both S and T are non-empty (since same set, they have same size, maybe >0). So both S and T have the same cardinality. So it's fine.

    Now after we have x_i for all i (including those with b[i]=0 we determined) and y_j for all j (including those with b[j]=0 we determined), we must also check any leftover constraints: For cells where bar_i=0, bar_j=0 already checked; bar_i=0, bar_j=1 used to determine x_i (and must have consistency); bar_i=1, bar_j=0 used to determine y_j; bar_i=1, bar_j=1 used to determine x_i XOR y_j, which we enforced. But we also need to consider cells where bar_i=0, bar_j=1 but we used those to set x_i; after we compute x_i, the equation automatically holds for all such j if we ensured consistency. However, if there is no j with b[j]=1 for some i with b[i]=0, then x_i is not constrained, but what about the equation D[i][j] = x_i? There would be no such j. But then any x_i is fine? But we must also consider equations where bar_i=0, bar_j=0 already done. There is no other equation that involves x_i. So x_i can be arbitrary. But could it affect something else? No. So we can set x_i arbitrarily, e.g., 0. However, we must be careful: When b[i]=0 but there exists some j with b[j]=1? Actually if b has any 1, then for each i with b[i]=0, there is at least one j with b[j]=1 because the bar pattern is of length N. If N>0 and b has at least one 1, then for any i, we can pick j among those where b[j]=1. So indeed for each i with b[i]=0, there exists at least one j? Not necessarily if N=1? But if N=1, bar pattern is single bit. If b[0]=1, then b[i]=0 doesn't exist; if b[0]=0, then b has no 1. So fine.

    Thus for i with b[i]=0, we have at least one j with b[j]=1 if b has any 1, because the set of j is the same as indices. So unless b is all zeros, for each i there is at least one j such that b[j]=1? Actually if b has at least one 1, then for any i, we can choose a column j that has b[j]=1. So yes, because columns are all indices. So there exists at least one column j with b[j]=1. Thus for each row i, we have at least one equation: if b[i]=0, we have D[i][j] = x_i for that j. So x_i is forced. Similarly for each column j with b[j]=0, there is at least one row i with b[i]=1, because there is at least one row i with b[i]=1 (since bar has at least one 1). So y_j is forced. Therefore, if bar has any 1s, then all x_i and y_j are uniquely determined? Possibly, except that for indices i with b[i]=1, x_i may have two possibilities depending on assignment? Actually from (1,1) equations, if we choose u_{i0} arbitrarily, we get one set of solutions: if we flip all x_i (i∈S) and y_j (j∈T) simultaneously, the equations x_i XOR y_j remain same because flipping both adds 0? Actually if we flip all x_i (i∈S) and also flip all y_j (j∈T), then x_i XOR y_j unchanged. But are x_i for i in S allowed to flip individually? Not unless we also flip y_j appropriately? Let's analyze: For S and T, the system M[i][j] = x_i XOR y_j. If (x_i, y_j) is a solution, then (x_i XOR c, y_j XOR c) for any constant c (same for all) is also a solution because (x_i XOR c) XOR (y_j XOR c) = x_i XOR y_j. So there is a degree of freedom: we can choose a global constant c to flip all x_i and y_j simultaneously. But note that x_i for i in S may also affect equations where b[i]=1? Only (1,1) equations involve them. Also, y_j for j in S? Actually j in T. And there may be dependencies with other rows/cols? No, x_i for i with b[i]=1 don't appear elsewhere. So indeed there is one binary degree of freedom: we can choose c=0 or 1, which flips all x_i (i∈S) and all y_j (j∈T). But wait: y_j for j with b[j]=0 are already determined from earlier constraints, and they are not part of this flip. So flipping y_j for j in T (where b[j]=1) may conflict with y_j for j where b[j]=0? No, because they are separate sets. So indeed the solution may not be unique; there could be two possible assignments for the S,T sets, if they exist. So we can choose any.

    Now if bar has no 1s (all zeros), then the operations do nothing. In that case, we require D all zeros. If so, any sequence of operations (or none) works, but we can output M=0 (since we want M as small as possible? Not required, any solution up to 1e5 moves, but we can output 0). If D is not all zeros, impossible.

    Now what about the case bar has both 0 and 1? As we described.

    Now, after determining x_i and y_j (binary), we need to produce a sequence of operations (rows and columns) that yields that final state. Since operations are XOR and order independent, we can simply output all rows i with x_i=1 as "row i", and all columns j with y_j=1 as "col j". The total number M = sum(x_i) + sum(y_j). We must ensure M ≤ 100000, but N ≤ 2000, so maximum M = 2N = 4000 < 1e5, so fine. Also we can output in any order, but ensure format: each line "row X" or "col X" with X 0-based.

    Potential issue: Could there be a solution requiring more than 1 application per row/col? Since we can apply multiple times, odd/even is enough. So binary solution is sufficient.

    Now we must verify that the derived x_i, y_j satisfy all equations. We will construct the solution step by step and check for consistency.

    Implementation plan:

    Read N. Read initial board as list of strings -> matrix A (int 0/1). Read desired board B. Read bar string -> list b (int 0/1).

    Compute D[i][j] = A[i][j] XOR B[i][j].

    If all b[k]==0: if all D[i][j]==0: output 0 (just a line with 0, no further lines). Actually output format: first line M, then M lines. So if M=0, just print 0. That's acceptable. else print -1. done.

    Otherwise (at least one 1 in bar): // Check zeros: for all i,j where b[i]==0 and b[j]==0: D[i][j] must be 0. // We'll loop over i,j? N up to 2000, N^2=4e6, acceptable. But we need O(N^2) maybe okay. 4 million is fine. We'll just check all pairs. Could be borderline but Python should handle 4e6 loops with simple operations. We'll try to be efficient.

    // We'll also compute x array of size N (initialize maybe None), y array of size N (None).

    // For rows i with b[i]==0: // Find first j with b[j]==1, set x_i = D[i][j]. Then verify for all j with b[j]==1 that D[i][j] == x_i. If any mismatch -> impossible. // If no j with b[j]==1? Not possible because bar has at least one 1. But if N=0? N>=1. So there is at least one j.

    // For columns j with b[j]==0: // Find first i with b[i]==1, set y_j = D[i][j]. Then verify for all i with b[i]==1 that D[i][j] == y_j. If mismatch -> impossible.

    // For rows i with b[i]==1: // x_i to be determined later. Possibly set to None for now.

    // For columns j with b[j]==1: // y_j to be determined later.

    // Now for the set S = indices where b[i]==1, T = indices where b[j]==1 (they are the same set but we treat separately). Need to solve x_i XOR y_j = D[i][j] for all i in S, j in T.

    // Approach: // Pick i0 in S (any). Choose x_i0 arbitrarily, say 0. // Then for each j in T: y_j = D[i0][j] XOR x_i0. // Then for each i in S: // For any j in T (e.g., first), compute x_i = D[i][j] XOR y_j. // Then verify for all j in T: D[i][j] == (x_i XOR y_j). If not -> impossible. // Note: we must also consider that x_i or y_j might have been already set? No, they are not set yet because we only set x_i for b[i]==0 and y_j for b[j]==0. So all indices in S and T are untouched.

    // After this, we have all x_i and y_j.

    // But wait: There could be overlap? For rows i with b[i]==1, we set x_i from the above. For columns j with b[j]==1, we set y_j.

    // However, we also need to check consistency with previously determined values? No, because there is no cross constraints between x_i (i in S) and y_j (j not in T) or vice versa. But note: For cells with b[i]==1, b[j]==0, we already used to determine y_j; that gave y_j = D[i][j]. But we haven't used x_i there. So after we compute x_i, we must check that those cells still satisfy? Wait, we already used those cells to determine y_j; we enforced that for a given j, all i with b[i]==1 give same D[i][j], which we set as y_j. That condition ensures that for all i in S, D[i][j] = y_j. But note that according to our model, the equation for (i,j) with b[i]=1, b[j]=0 is D[i][j] = y_j. There is no x_i term. So after we determine y_j from these equations, it must hold for all i. That is already checked. So no further constraint.

    // Similarly for cells with b[i]=0, b[j]=1: D[i][j] = x_i, and we checked consistency across j. So after we set x_i accordingly, it's fine.

    // But there is also the case b[i]=1,b[j]=1: we already solved.

    // So overall, after we have x_i and y_j defined, all equations should be satisfied. However, we might have to also check the equations for b[i]=0,b[j]=1 and b[i]=1,b[j]=0 again? Already done.

    // Additionally, there might be equations for b[i]=0,b[j]=0: we already checked D[i][j]==0. That's consistent regardless of x,y.

    // So algorithm done.

    // After obtaining x_i and y_j, we can output rows with x_i=1 and columns with y_j=1.

    But careful: The algorithm for b[i]=0 and b[j]=0 check must be performed before setting x,y? It's independent.

    Edge Cases:

    • N=1. bar may be '0' or '1'. If bar='0', then operation does nothing. So we need A[0][0] == B[0][0] to be solvable. If bar='1', then we have b[0]=1. Then S={0}, T={0}. For b[0]=0? none. The equations: For (i,j) with b[i]=1,b[j]=1: D[0][0] = x_0 XOR y_0. Also note there are no b[i]=0,b[j]=1 or b[i]=1,b[j]=0 because no indices with 0. So we just have that equation. We can solve by picking x_0 arbitrary (0) and then y_0 = D[0][0] XOR x_0. So always solvable? But wait: There might also be check for b[i]=0,b[j]=0: none. So for N=1, bar=1, there is always a solution? Let's test: A=0,B=1 -> D=1. So we need x_0 XOR y_0 = 1. Choose x_0=0,y_0=1 or x_0=1,y_0=0. So solution exists. That seems plausible: applying bar to row XORs with 1, flipping that cell; applying bar to column also flips; both together flip twice? Actually operations are XOR with 1 for both row and column (since bar=1). Starting from 0, apply row -> 1; apply column -> flip again? Wait: row operation on the only cell: b := b XOR 1. Column operation also on same cell: b := b XOR 1. So if we apply exactly one of them (row or column), we get 1; if we apply both, we get 0 because two flips. So to go from 0 to 1, we need exactly one operation. So there are solutions. So algorithm fine.

    • What about if bar has 1s but there exist i with b[i]=0, but there is a j with b[j]=1, we set x_i = D[i][j]. But we must also check that for all such j, D[i][j] are consistent. That's necessary.

    • Similarly for j with b[j]=0.

    Now time complexity: O(N^2) to scan D and check consistency. But we need to be careful to avoid O(N^3) loops. We can do:

    For i in range(N): if b[i]==0: # find a j0 with b[j0]==1 (we can precompute list of indices where b is 1, call ones.) for each j in ones: check D[i][j] consistent. But if there are many ones, that could be O(N^2) overall? For each i with b[i]==0, iterating over all ones. Number of ones can be up to N. So total operations for this part could be: (#zeros)*(#ones) ≤ N^2. Similarly for columns with b[j]==0 iterating over ones. So total O(N^2). Good.

    Check for b[i]==0,b[j]==0 cells: we need to verify D[i][j]==0. That is also O(N^2) but can be done by iterating over i where b[i]==0 and j where b[j]==0. That's at most N^2. So overall O(N^2).

    For solving the (1,1) part: For each i in S and each j in T we need to verify after solving. That's also |S|*|T| ≤ N^2.

    Thus O(N^2) works for N=2000.

    Memory: store A, B as bits? Could store as list of ints for each row. But N^2=4e6, storing two matrices as list of strings or list of list of ints is okay.

    Implementation details:

    • Read input lines. The input format: first line N, then N lines for initial, N lines for desired, then bar line. There might be blank lines? The examples show blank lines but likely just formatting. We'll just read all lines using sys.stdin.read().splitlines().

    • Convert strings to list of ints for easier XOR? We'll keep as list of strings but compute XOR by comparing characters. But better to convert to ints (0/1) for each cell. We can store D as list of list of ints? Or compute on the fly? Since we need D for many indices, we should precompute D as 2D list of ints. N=2000, D is 4 million ints, which is fine (~32 MB if Python ints? Actually Python ints are bigger, but we can use bytearray or list of lists of bool? Better to use list of list of ints (0/1) using Python int, memory maybe high (28 bytes per int) which would be ~112 MB per matrix, not good. We need to be careful: 4 million Python ints is about 28 bytes each => 112 MB. Two matrices would be 224 MB, plus D another 112 MB -> too much. So we need a more memory-efficient representation.

    N=2000, N^2=4e6. Each int in Python list of lists overhead is large. We can use bit-packed representation? For example, store each row as an integer using bit operations? Python ints can hold arbitrary bits, but for N=2000, we can store as a string and index characters; but character comparison may be slower but memory efficient. Since we have to perform many XOR operations across rows/cols, we may want to compute D bits quickly.

    Alternative: Since we need to access D[i][j] frequently (for each i,j in subsets), we could compute D on the fly as A[i][j] ^ B[i][j] when needed, but that would be many recalculations. However we can precompute D as a list of lists of ints but using bytearray per row? In Python, we can store each row as a bytearray of 0/1 values. Bytearray each element is a byte, 4 million bytes = 4 MB, which is fine. So we can read the strings and convert to bytearray for A and B, then compute D as a list of bytearray where D[i][j] = A[i][j] ^ B[i][j]. We'll need to store A and B? Not necessarily after computing D, we could discard them? But we need D for checks. But we also need A? Actually we only need D for solving equations. So we can compute D directly while reading. But we need A and B separately? Not after D computed. So we can read A lines, store as list of strings, read B lines, compute D on the fly and store D as bytearray per row. Then discard A and B (or keep as strings if needed). But careful: In checks for b[i]=0,b[j]=0, we need D[i][j]. So D is sufficient.

    Thus we can do:

    • Read N.
    • Read next N lines as A strings.
    • Read next N lines as B strings.
    • Compute D matrix: For i in range(N): for each j, D[i][j] = (int(A[i][j]) ^ int(B[i][j])). Could store as list of bytearray: row = bytearray(N); for j, row[j] = (A[i][j] != B[i][j])? Actually XOR as int 0/1. We'll parse char to int: ord(char)-48 or simply char == '1'. So D[i][j] = (A[i][j] == '1') ^ (B[i][j] == '1').
    • Then read bar string: b = [1 if ch=='1' else 0 for ch in bar_str]

    Now we have D (list of bytearray) and b (list of ints). We also might want lists of indices where b is 1 and 0.

    ones = [idx for idx, val in enumerate(b) if val == 1] zeros = [idx for idx, val in enumerate(b) if val == 0]

    If len(ones) == 0: // all zeros Check if all D[i][j]==0. If yes, print 0. else -1. return.

    Now we need to set x = [None]*N, y = [None]*N.

    First, check zero-zero cells: For i in zeros, j in zeros: if D[i][j] != 0: impossible. We can iterate: for i in zeros: for j in zeros: if D[i][j]: impossible. This is O(|zeros|^2) which could be up to N^2, still ok.

    But we can perhaps skip if we later check? Better to do.

    Second, for rows i with b[i]==0: (i in zeros) We have ones list (non-empty). For such i, we can set x_i = D[i][ones[0]] (since D[i][j] for j in ones should equal that). Then for each j in ones: if D[i][j] != x_i: impossible. Also note: need to ensure that for i in zeros, the ones list exists. Since we have at least one 1, yes.

    Third, for columns j with b[j]==0: (j in zeros) For each j, set y_j = D[ones[0]][j] (using any i in ones). Check for all i in ones: D[i][j] == y_j. If mismatch: impossible.

    Now we have x_i set for i in zeros, y_j set for j in zeros.

    Now S = ones (indices where b==1). For i in S, x_i unknown; for j in S, y_j unknown.

    We need to solve for these.

    We pick i0 = ones[0] (some index in S). We'll set x_i0 = 0 (choice). Then for each j in S: y_j = D[i0][j] ^ x_i0.

    Then for each i in S (including i0 maybe): We need to pick a j in S (e.g., ones[0]) to compute x_i = D[i][j] ^ y_j. But careful: For i0, x_i0 already set to 0; using the formula should give consistent value? Let's compute: For i0, x_i0 = 0, then using j=ones[0] we get x_i0_calc = D[i0][j] ^ y_j. Since y_j was defined as D[i0][j] ^ x_i0 = D[i0][j] ^ 0 = D[i0][j], so x_i0_calc = D[i0][j] ^ (D[i0][j]) = 0, consistent. So okay. For other i, compute x_i using first j (say j0 = ones[0]). Then we must verify for all j in S: D[i][j] == (x_i ^ y_j). If any fails -> impossible.

    After verification, we have all x_i and y_j.

    Now, check for any remaining constraints? Possibly we should also verify the cells used to set x_i and y_j (i zeros, j ones) and (i ones, j zeros) have been checked already? Yes, we checked consistency for i zeros with all j ones, and j zeros with all i ones. But what about i zeros and j zeros? Already checked. So all cells are covered.

    Now we have solution.

    Now output M = sum(x_i) + sum(y_i) (note y_i for columns j). But careful: x_i for i=0..N-1, y_j for j=0..N-1.

    Then for each i where x_i == 1, print "row i". For each j where y_j == 1, print "col j". Order arbitrary.

    Make sure to output M first. Also note that M can be 0, then just print 0 (no further lines). That is valid.

    Now we need to ensure that we handle large N efficiently. O(N^2) loops with Python may be near time limit but should be okay for 2000: 4 million operations, each simple integer or byte comparison, probably okay (< 1 second?). But we also have multiple passes over ones and zeros. Could be up to 4 passes of ~4M operations, total maybe 16M, still okay.

    But we need to be careful with using Python's loops, especially nested loops over indices. Use local variables, precompute lists, and use for loops with early exits.

    Potential improvements:

    • For checking zero-zero cells: iterate over i in zeros: row = D[i]; for j in zeros: if row[j] != 0: impossible. Accessing row[j] is fast.

    • For checking rows with b[i]==0: for i in zeros: row = D[i]; expected = row[ones[0]]; for j in ones: if row[j] != expected: impossible.

    • For checking columns with b[j]==0: for j in zeros: expected = D[ones[0]][j]; for i in ones: if D[i][j] != expected: impossible. This inner loop over i. That's fine.

    • For solving S,T: we need to access D[i][j] for i,j in ones often. Could precompute a submatrix? But we can just access directly.

    Now, one nuance: When we compute y_j for j in S using i0, we need D[i0][j] which is accessible. Then for each i in S, we compute x_i from j0, then we verify for all j in S. So verification is double loop over |S|^2, which can be up to N^2 (if all ones). That's fine.

    Now, potential pitfalls: What if we have consistency conflicts across the board that we haven't caught? Our systematic checks should be complete.

    Let's test with the given examples.

    Example 1:

    N=2 A: 11 -> [1,1] 11 -> [1,1] B: 00 -> [0,0] 01 -> [0,1] bar: 11 -> [1,1]

    Compute D: row0: A^B = 1^0=1, 1^0=1 => [1,1] row1: 1^0=1, 1^1=0 => [1,0]

    b = [1,1] (ones=[0,1], zeros=[])

    Check zeros: none.

    Since no zeros, we skip setting x_i from zeros and y_j from zeros.

    Now S=T={0,1}. We pick i0=0, set x0=0. Then y_j = D[0][j] ^ x0: j=0: D[0][0]=1 => y0=1 j=1: D[0][1]=1 => y1=1 Now compute x_i for i in S: i=0: x0=0 (set). i=1: use j0=0: x1 = D[1][0] ^ y0 = D[1][0]=1? D[1][0] = 1, y0=1 => 0. So x1=0. Now verify for i=1, all j: j=0: D[1][0]=1, x1^y0 = 0^1=1 OK. j=1: D[1][1]=0, x1^y1 = 0^1=1 => 0? Actually 0^1=1, but D[1][1]=0 => mismatch. So impossible. Good, we output -1.

    Example 2:

    N=2 A: 10 00 B: 00 00 bar: 10

    Compute A: row0: [1,0]; row1: [0,0] B: all zeros D: row0: [1,0]; row1: [0,0] bar: [1,0] => ones=[0], zeros=[1]

    Check zero-zero: i=1, j=1 => D[1][1]=0 OK.

    Rows i with b[i]==0: i=1. ones=[0]. So x_1 = D[1][0] = 0. Check for j in ones (only j=0) => D[1][0]=0 consistent.

    Columns j with b[j]==0: j=1. ones=[0]. So y_1 = D[0][1] = 0? Wait D[0][1]=0. Check for i in ones (i=0) => D[0][1]=0 consistent.

    Now S = {0} for rows and T = {0} for columns. Solve: i0=0, set x0 arbitrarily 0. Then y0 = D[0][0] ^ x0 = 1 ^ 0 = 1. Then verify for i=0, j=0 already holds. So x0=0,y0=1.

    Now we have: x = [0,0] (since i=1 is zero and x1=0) y = [1,0] (y0=1, y1=0)

    Output M= sum(x)+sum(y)=0+1=1. Print row? Actually column? y0=1 means apply to column 0. But example output says "row 0". Let's check: They output "row 0". Hmm maybe our solution gives column 0? Let's double-check: In example 2, initial board is [[1,0],[0,0]]; desired [[0,0],[0,0]]; bar = "10". So bar pattern: index0=1, index1=0. So if we apply bar to row 0, we XOR row0 with [1,0]: row0 becomes [1^1,0^0]=[0,0] -> matches. If we apply bar to column 0, we XOR column0 with [1,0]? Wait column operation uses bar[i] for row i. So column 0: for each row i, board[i][0] ^= bar[i]. bar[0]=1, bar[1]=0. So column0: row0:1^1=0; row1:0^0=0. That also yields [0,0] in column0; the rest (col1) remains [0,0] because unchanged? Actually row0 col1 is 0, row1 col1 is 0. So final board all zeros. So both row0 or column0 work. In our solution we got column0 (y0=1). That's also valid. But the example output chose row0. So any correct solution is accepted. Our algorithm could output either depending on the arbitrary choice of x_i0=0. If we had chosen x0=1, then y0 = D[0][0] ^ 1 = 1^1=0, so x0=1,y0=0, output row0. So we can choose to output row0 by setting x_i0=1? Wait we set x_i0 arbitrarily; we chose 0 but we could choose 1. The solution would still be valid. But the problem says "If there are multiple solutions print any". So either is fine. In our algorithm, we can output either based on the arbitrary constant c. But we need to ensure that we output a solution with M ≤ 1e5, which is fine. However, if we want to minimize M maybe? Not required. So we can stick with arbitrary choice (e.g., x_i0=0). But we might also output both row and column if needed? But that would increase M. Our solution produces M=1 which is fine.

    Example 3:

    N=3 A: 110 011 100 B: 100 011 100 bar: 100

    Let's compute D.

    A rows: 0:1,1,0 1:0,1,1 2:1,0,0

    B rows: 0:1,0,0 1:0,1,1 2:1,0,0

    D: row0: (1^1=0, 1^0=1, 0^0=0) -> 0,1,0 row1: (0^0=0, 1^1=0, 1^1=0) -> 0,0,0 row2: (1^1=0, 0^0=0, 0^0=0) -> 0,0,0

    So D matrix: [0,1,0] [0,0,0] [0,0,0]

    bar: "100" -> [1,0,0] => ones=[0], zeros=[1,2].

    Check zero-zero: i in zeros (1,2), j in zeros (1,2). Check D[1][1]=0, D[1][2]=0, D[2][1]=0, D[2][2]=0. OK.

    Rows i with b[i]==0: i=1,2. For i=1: ones=[0] => x_1 = D[1][0] = 0. Check others? only j=0, OK. For i=2: x_2 = D[2][0] = 0. OK.

    Columns j with b[j]==0: j=1,2. For j=1: ones=[0] => y_1 = D[0][1] = 1? D[0][1]=1. Check for i in ones: i=0 => D[0][1]=1 consistent. OK. For j=2: y_2 = D[0][2] = 0? D[0][2]=0. Check i=0 => D[0][2]=0 consistent.

    Now S = {0} (rows with b=1), T = {0} (columns with b=1). Solve: i0=0, set x0=0. Then y0 = D[0][0] ^ x0 = 0 ^ 0 = 0. Then verify: i=0, j=0: D[0][0]=0, x0^y0=0 OK.

    Now we have: x = [0,0,0] (x1=0, x2=0, x0=0) y = [0,1,0] (y0=0, y1=1, y2=0)

    Output: rows with x=1 none, columns with y=1: col 1. That gives M=1. But example output says: 3 row 0 col 0 col 1

    That is a different solution. Our solution seems to produce only column 1, but does that transform correctly? Let's test: Starting A: 110 011 100 Apply column1 (bar pattern [1,0,0] to column 1): For rows i, col1 ^= bar[i]. bar[0]=1, bar[1]=0, bar[2]=0. So: row0 col1: 1 xor 1 = 0 -> row0 becomes 1,0,0 -> 100 row1 col1: 1 xor 0 = 1 -> row1 stays 0,1,1? Actually row1 was 0,1,1; after xor col1: col1 becomes 1 xor? Wait we need to apply only column1. row1 col1 originally 1, bar[1]=0 => remains 1. So row1 remains 0,1,1 -> 011 (desired row1 is 011, yes) row2 col1: 0 xor 0 = 0 -> row2 remains 1,0,0 -> 100 (desired 100). So final board is 100,011,100, which matches B. So indeed column1 alone works. So our solution M=1 is also correct. But the example output shows M=3 with row0, col0, col1. Both are valid. So our algorithm yields a valid solution. The problem says any correct solution is fine. So our output would be accepted.

    Thus algorithm seems correct.

    But we should also consider the possibility of multiple solutions due to the constant c. We arbitrarily set x_i0=0. That's fine.

    Now we need to ensure we correctly handle all consistency checks, including cases where we have to set x_i for zeros but there might be no ones? That only when bar all zeros, which we already handled separately.

    Edge Cases:

    • bar has exactly one 1. Then ones list size = 1. Then for rows with b[i]=0, we set x_i = D[i][the one column]. For columns with b[j]=0, set y_j = D[the one row][j]. For the (1,1) block, it's just a single cell (i_one, j_one). The equation: D[i0][j0] = x_i0 XOR y_j0. We have x_i0 unknown, y_j0 unknown. We can choose x_i0 arbitrarily and set y_j0 accordingly. Also note that we may have already set x_i for zeros and y_j for zeros. That is fine.

    Check consistency: The verification step for (1,1) block would only involve the single cell, so it's fine as long as we set accordingly. However, we need to verify that for other i in S? Only one i. So verification passes trivially.

    Now, what about potential conflict: For i in zeros, we set x_i = D[i][j_one]. For j in zeros, we set y_j = D[i_one][j]. And for (i_one, j) with b[j]=0, we also require D[i_one][j] = y_j, which we used to set y_j and checked consistency for all i_one? Actually we check for each column j (zero) that all i in ones give same D[i][j] equal to y_j. Since only one i_one, it's consistent by definition. Similarly for rows i (zero) and j in ones.

    Thus the algorithm covers.

    Now, we must also consider that in (1,1) verification we check all i in S, j in T. That ensures that the previously set x_i and y_j from the zeros part are not conflicting because they are not involved. So all good.

    Now, we need to ensure that when we compute y_j for j in S using i0 and x_i0, we must also verify that for those j, there is no conflict with previously determined y_j? But j in S have b[j]=1, so they are not set previously. So fine.

    Now about the overall complexity: For N=2000, we will have loops that go over zeros and ones, potentially up to 4 million operations each, but we have about 4 such loops: check zero-zero (|zeros|^2), set x for zeros (|zeros||ones|), set y for zeros (|zeros||ones|), solve S,T (|ones|^2). Sum ≤ 2*(|zeros|*|ones|) + |zeros|^2 + |ones|^2 = (|zeros|+|ones|)^2 = N^2. So total O(N^2) which is fine.

    Now we need to be careful to avoid using too much memory for D. We'll use list of bytearray for D. Bytearray holds bytes; we can store 0 or 1 as bytes. However, arithmetic XOR on bytes? For D we compute as integer 0/1. But for checks we compare to 0 or 1. So that's fine.

    Implementation details:

    • We'll read using sys.stdin.buffer.read() and splitlines for speed.

    Pseudo:

    import sys

    def main(): data = sys.stdin.buffer.read().splitlines() # data: list of bytes lines; need to decode? Could treat as bytes and compare to b'1'. # First line is N. it = iter(data) N = int(next(it).decode()) A = [next(it).decode().strip() for _ in range(N)] B = [next(it).decode().strip() for _ in range(N)] bar_str = next(it).decode().strip() # But careful: there might be blank lines? Usually not.

    But for safety, maybe read all lines, strip whitespace. We'll assume exactly as described.

    Alternative: use sys.stdin.readline.

    I'll use sys.stdin.readline in a loop.

    Now compute D as list of bytearray:

    D = [] for i in range(N): a_line = sys.stdin.readline().strip() # Actually we need to read A lines then B lines then bar. But we need to read in order.

    Simplify: read all lines sequentially using sys.stdin.buffer. We'll keep as bytes.

    Implementation steps:

    • read N
    • read N lines for initial board -> store as list of strings (or bytes)
    • read N lines for desired board -> store as list
    • read 1 line for bar -> store as string

    We'll use sys.stdin.buffer.readline to avoid decoding overhead for char comparison? Possibly easier to decode and compare.

    Given N up to 2000, it's okay.

    We'll convert each line to string (strip newline).

    Compute D:

    D = [bytearray(N) for _ in range(N)] for i in range(N): a = A[i] b = B[i] row = D[i] for j in range(N): # XOR: (a[j]=='1') ^ (b[j]=='1') row[j] = (a[j] != b[j]) ? 1 : 0 # Actually XOR: 1 if different. # Or: row[j] = (int(a[j]) ^ int(b[j])) # But careful: need int conversion. We'll do: row[j] = (a[j] != b[j]) and 1 or 0? But bool to int. # Use: row[j] = (a[j] != b[j]) returns bool, but bytearray expects int 0-255. So we can set: row[j] = (a[j] != b[j]) which will cast? In Python, bytearray assignment expects integer; bool works as 0/1? Actually bool is subclass of int, True=1, False=0. So it's fine. # However, we might do row[j] = (a[j] == '1') ^ (b[j] == '1') which yields bool. But ^ on bool returns bool. So ok.

    But note: Using a[j] != b[j] yields True if they differ, which is exactly XOR. So that works.

    Now bar = [1 if ch == '1' else 0 for ch in bar_str]

    Now proceed.

    Now we also need to precompute ones and zeros:

    ones = [i for i, val in enumerate(bar) if val == 1] zeros = [i for i, val in enumerate(bar) if val == 0]

    If len(ones) == 0: # all zeros # Check all D[i][j] == 0 possible = all(all(v == 0 for v in row) for row in D) if possible: print(0) else: print(-1) return

    Now check zero-zero:

    for i in zeros: row = D[i] for j in zeros: if row[j] != 0: print(-1); return

    Now assign x = [None]*N, y = [None]*N

    For rows with b[i]==0

    for i in zeros: # Since ones nonempty, get j0 = ones[0] expected = D[i][ones[0]] # Check consistency for j in ones: if D[i][j] != expected: print(-1); return x[i] = expected

    For columns with b[j]==0

    for j in zeros: expected = D[ones[0]][j] for i in ones: if D[i][j] != expected: print(-1); return y[j] = expected

    Now for S (ones). We'll treat rows and columns separately.

    if ones: # always true here i0 = ones[0] # We'll choose x_i0 = 0 (or could be arbitrary) # But we need to ensure that x[i0] is not already set? It shouldn't be because i0 is in ones, and we only set x for zeros. So x[i0] is None. x[i0] = 0 # choose 0 # Set y for j in ones for j in ones: # y[j] = D[i0][j] ^ x[i0] y[j] = D[i0][j] ^ 0 # i.e., D[i0][j] # Now compute x for other i in ones # Use j0 = ones[0] as reference to compute x_i j0 = ones[0] for i in ones: if i == i0: continue # Compute x[i] = D[i][j0] ^ y[j0] x[i] = D[i][j0] ^ y[j0] # Now verify all (i in ones, j in ones) for i in ones: xi = x[i] # already set for j in ones: if D[i][j] != (xi ^ y[j]): print(-1); return

    At this point, x and y should be all assigned. But we should also set x for ones? Already set.

    Also, ensure x and y for zeros are already set.

    Now we have x and y.

    Now output:

    M = sum(x_i for i in range(N) if x_i==1) + sum(y_j for j in range(N) if y_j==1) print(M) for i, val in enumerate(x): if val == 1: print(f"row {i}") for j, val in enumerate(y): if val == 1: print(f"col {j}")

    That's it.

    Now test with some custom cases.

    Case: N=1, bar=1, A=0, B=0. D=0. ones=[0], zeros=[].

    Check zero-zero: none.

    Rows zeros: none.

    Columns zeros: none.

    Now ones: i0=0, set x0=0; y0 = D[0][0] ^ 0 = 0. Then verify: i=0,j=0: D[0][0]=0, x0^y0=0 OK.

    x = [0], y=[0], M=0 -> output 0. That's correct: no operation needed.

    If A=0,B=1: D=1. ones: i0=0, x0=0; y0=1; verify: D[0][0]=1, 0^1=1 OK. x=[0], y=[1] -> M=1 col0. Or if we set x0=1, y0=0 -> row0. Both fine.

    Now case where bar has mix but inconsistencies.

    Let's try N=2, bar=01 (ones=[1], zeros=[0]). A: any, B: any. We'll manually check conditions.

    But algorithm should detect.

    Now, complexity: For checking zero-zero, we did nested loops over zeros. That's fine. However, we might also need to check for i in zeros, j in ones consistency (we did). For j in zeros, i in ones consistency (we did). And S,T verification (we did). So all cells covered.

    But we haven't explicitly checked cells where b[i]=0,b[j]=1 after setting x_i, but we already checked consistency when we set x_i (ensuring all j in ones have same value). So that's done.

    Similarly for b[i]=1,b[j]=0.

    Now, is there any cell we missed? b[i]=0,b[j]=0 we checked. b[i]=0,b[j]=1 we checked. b[i]=1,b[j]=0 we checked. b[i]=1,b[j]=1 we checked. So all.

    Thus algorithm complete.

    Now, we need to ensure we handle the case when ones size is 0 (all zeros) correctly, we did.

    Now, let's consider an edge where bar has ones but zeros list empty (i.e., bar all ones). Then zeros=[], ones=[0..N-1].

    Check zero-zero: none.

    Rows with b[i]==0: none.

    Columns with b[j]==0: none.

    Now we directly go to S,T with all indices. We'll pick i0, set x_i0=0, compute y_j = D[i0][j], compute x_i = D[i][j0] ^ y_j0, verify all. So works.

    Now, what about the condition for cells with b[i]=0,b[j]=1? There are none because no zeros. So fine.

    Now, one more nuance: In our earlier steps, for rows i with b[i]=0, we set x_i = D[i][ones[0]] and checked consistency for all j in ones. But what if there are also columns j with b[j]=0? We don't involve them. That's fine.

    Now, verify that after we set x_i for i in zeros, we haven't created inconsistency with the (1,1) equations? Because x_i for zeros does not appear in (1,1) equations. So no conflict.

    Thus overall logic.

    Now, we must also ensure that we don't inadvertently produce a solution with M > 100000, but as argued, max 4000.

    Now, implement carefully.

    Potential performance improvements: In the loops, using Python's for loops with bytearray indexing is fine.

    We also need to be careful about using D[i][j] multiple times; we can store row references.

    Now, test with random small cases by brute force to verify. We'll do a mental check.

    But there is one more subtlety: The operation can be applied multiple times, but we assume each row/col can be applied at most once (since XOR). However, is it allowed to apply the same row multiple times? Yes, but it cancels. So binary representation is sufficient.

    Now, confirm the derived equation: D = (x_i * b_j) XOR (y_j * b_i). We used. Good.

    Now, check scenario where bar has both 0 and 1, but there is a case where for a row i with b[i]=0, we set x_i = D[i][ones[0]], but also we could have set x_i from other j; we checked consistency. However, we haven't considered that the same x_i might be forced by two separate j sets? Not needed.

    Now, one more check: For b[i]=0, b[j]=1, equation D[i][j] = x_i. So x_i is forced. So that's fine.

    Now, we also need to check if after we set y_j for zeros, it's consistent with the x_i for zeros? Not directly, because there is no equation linking them. But there is no equation involving both x_i (i zero) and y_j (j zero) because when both are zero, equation is D=0 (checked). So no interaction.

    Now, double-check with a more complex case: Suppose bar = [1,0,1] for N=3. So ones indices: 0,2; zeros: 1.

    We'll test with random D consistent with some x,y.

    Let’s pick x = [a0,a1,a2], y = [b0,b1,b2] with a1 determined by zeros, etc.

    We'll generate a solution by picking arbitrary x and y, then compute D accordingly, then run algorithm to see if recovers.

    But trust.

    Now, one more nuance: When setting y_j for j in zeros, we used D[ones[0]][j] as expected. But we must ensure that for each such column j, all i in ones give the same D[i][j]. That's the consistency check. So we did.

    Now, after that, we set x_i for i in zeros, similarly checked.

    Now, what about rows i with b[i]=0 that also have some columns j with b[j]=0? Already handled.

    Now, after we have determined all x and y, we might want to double-check all equations to be safe (could be done but not necessary).

    Now, consider the case where N is large and we allocate D as list of bytearray. That should be fine.

    Now, the output: If M>0, we need to output lines. Order is arbitrary; we will output rows first then columns, or any.

    Now, potential pitfalls: Reading input with extra blank lines; we can just use sys.stdin.read().split()? But that will split on whitespace and treat each string. Since the board lines are strings of 0/1 without spaces, that could work: all tokens after N are N strings for A, then N strings for B, then one string for bar. However, careful: If there are blank lines, split will ignore them. That's fine. We can read all tokens via sys.stdin.read().split(). That gives list of strings. First token is N. Then next N tokens are initial board rows, then next N tokens are desired rows, then last token is bar. That is simpler and robust.

    Thus:

    import sys

    def main(): data = sys.stdin.read().split() if not data: return it = iter(data) N = int(next(it)) A = [next(it).strip() for _ in range(N)] B = [next(it).strip() for _ in range(N)] bar_str = next(it).strip() # Check that lengths are correct. Assume correct. # Now compute D as bytearray.

    But careful: If there are spaces or line breaks, split will handle. Good.

    Now, implement.

    Now, memory: A and B strings we keep only for computing D. We can compute D row by row while reading, but we already have them as strings; it's fine. After D computed, we can discard A and B (by not referencing).

    Now, Implementation details:

    D = [bytearray(N) for _ in range(N)] for i in range(N): a = A[i] b = B[i] row = D[i] for j in range(N): # XOR: 1 if a[j] != b[j] else 0 row[j] = (a[j] != b[j]) # bool to int

    But note: In Python, bytearray expects integer 0-255. Assigning a bool works as it's subclass of int. So ok.

    Alternatively, use row[j] = (a[j] == '1') ^ (b[j] == '1') which yields bool.

    Now, bar = [c == '1' for c in bar_str] # list of bool? But we need ints for later XOR operations. We'll keep as ints (0/1). So bar = [1 if c=='1' else 0 for c in bar_str].

    Now, ones = [i for i, v in enumerate(bar) if v == 1] zeros = [i for i, v in enumerate(bar) if v == 0]

    If not ones: ... handled.

    Now, we need to check zero-zero cells quickly. Could we skip this check if we later check other equations? Because if bar_i=0, bar_j=0, equation demands D=0. This is independent. So we must check.

    Now, implement:

    for i in zeros: row = D[i] for j in zeros: if row[j]: print(-1); return

    Now, set x = [None]*N, y = [None]*N

    Now, for i in zeros: # get expected from first one column j0 = ones[0] expected = D[i][j0] # check all ones for j in ones: if D[i][j] != expected: print(-1); return x[i] = expected

    Now, for j in zeros: i0 = ones[0] expected = D[i0][j] for i in ones: if D[i][j] != expected: print(-1); return y[j] = expected

    Now, if ones: i0 = ones[0] x[i0] = 0 # set y for ones for j in ones: y[j] = D[i0][j] # since x[i0]=0 # compute other x j0 = ones[0] for i in ones: if i == i0: continue x[i] = D[i][j0] ^ y[j0] # verification for i in ones: xi = x[i] for j in ones: if D[i][j] != (xi ^ y[j]): print(-1); return

    After all, we should also set any remaining None? Should be none.

    Now, output.

    But wait, what about the case where ones list is empty? Already handled earlier. But we also need to handle the case where after setting x_i for zeros, we might have that x_i is None for some i? All zeros indices are processed, so x[i] set. For ones indices, x[i] set in the block. So all x set. Similarly y.

    Now, one more nuance: In the block for ones, we used j0 = ones[0] to compute x[i] for i != i0. But we also need to ensure that for i0, x[i0] is set already (0). The verification will include i0. So okay.

    Now, also ensure that we didn't miss setting x[i] for i in ones if len(ones)==1. In that case, the for loop for i in ones (with if i == i0 continue) will skip the only one, so x[i0] already set. So fine.

    Now, after verification, we have x and y.

    Now, output M and operations.

    Now, test with example 2 to see which output we get. We got column 0. That's fine.

    Now, test with some random cases using brute force for small N to ensure algorithm always finds a solution if exists. Let's do mental reasoning: Our derivation shows that the necessary conditions we check are exactly the conditions for existence. And we construct a solution when conditions hold. So it should be correct.

    But need to be careful: The equation for b[i]=0,b[j]=1 gave x_i = D[i][j]. However, if there are multiple j, they must be consistent; we check. That ensures that x_i is forced uniquely. Similarly for y_j.

    Now, there is also a potential constraint from b[i]=0,b[j]=1 and b[i]=1,b[j]=0 that we haven't cross-checked with x_i and y_j? Already done.

    Now, what about the case where there is a row i with b[i]=0 but also some column j with b[j]=0? No relation.

    Now, one more: The condition for b[i]=0,b[j]=0 we checked D[i][j]==0. Could there be a scenario where D[i][j]==0 automatically from other constraints? Possibly, but we need to check it's actually satisfied. So we must check.

    Now, about the arbitrariness in setting x_i0: we chose 0. But what if the chosen x_i0 leads to y_j that conflict with something else? But since we only used the (1,1) equations, and those are satisfied by construction, and we verified, no conflict.

    Now, consider the possibility that for some i in zeros, there are no j with b[j]=1? That only if ones is empty, but we handled that. So fine.

    Now, confirm with another edge: N=2, bar = [0,1] (ones=[1], zeros=[0]). A and B such that D:

    • For zero-zero: (i=0,j=0) must be 0.
    • For rows i=0 (zero), x0 = D[0][1] (since j=1 is one) -> set x0 = some value, and must be consistent for all j in ones (only j=1).
    • For columns j=0 (zero), y0 = D[1][0] (since i=1 is one) -> set y0 = D[1][0], and check that for all i in ones (i=1) it's consistent (trivial).
    • For the (1,1) block: i=1,j=1: D[1][1] = x1 XOR y1. We will solve x1, y1.

    Now, check all constraints.

    Now, could there be an interaction that D[1][0] used to set y0, but also D[1][0] must equal y0 by definition, that's fine.

    Now, test with a potential inconsistency: Suppose we have bar = [0,1], D matrix: Row0: (0,0) must be 0; (0,1)=1 -> so x0=1. Row1: (1,0)=0 -> y0=0; (1,1)=? Let's say D[1][1]=1. Now, from (1,1): 1 = x1 xor y1. From zeros? None else. We have x0=1, y0=0, x1,y1 unknown. Now, does any other constraint? For i=1 (b=1) and j=0 (b=0): D[1][0]=0 must equal y0=0, ok. For i=0 (b=0) and j=1 (b=1): D[0][1]=1 must equal x0=1, ok. Zero-zero: (0,0)=0 ok. Thus constraints satisfied. So there should be a solution. Let's see if our algorithm finds: ones=[1], zeros=[0]. Check zero-zero: (0,0)=0 ok. Rows i=0: expected = D[0][1]=1; check all ones (j=1) -> ok; x[0]=1. Columns j=0: expected = D[1][0]=0; check all ones (i=1) -> ok; y[0]=0. Now ones: i0=1, set x[1]=0; y[1] = D[1][1] ^ x[1] = 1 ^ 0 = 1. Then verify: i=1,j=1: D=1, x1^y1=0^1=1 ok. So x=[1,0], y=[0,1]. Then operations: row0, col1? Actually x0=1 => row0; y1=1 => col1. So two operations. Check if starting from A? But we didn't define A and B, just D; we assume they exist. This is consistent.

    Now, test an inconsistent case: same bar, D matrix: Row0: (0,0)=0 ok; (0,1)=1 -> x0=1. Row1: (1,0)=1 -> y0 must be 1? Wait for j=0 zero, we set y0 = D[1][0] = 1; check for i in ones (i=1) it's consistent (trivial). So y0=1. But also from (i=1,j=0) we need D[1][0]= y0, okay. Now (1,1) say D[1][1]=0. Then from (1,1): 0 = x1 xor y1. Our algorithm: set x1=0, then y1 = D[1][1] ^ 0 = 0. Then verification passes. So it's consistent? But is there any hidden constraint? Let's see: (i=0,j=0) is 0 ok. So appears consistent. But maybe we can find actual A and B? Since we can always construct A and B given x,y? Actually if we have x,y and bar, we can compute D = (x_ib_j) xor (y_jb_i). Let's compute using our x=[1,0], y=[1,0]? Wait we got y0=1, y1=0, x=[1,0]. Then compute D: b=[0,1] For (0,0): b0=0,b0=0 -> 0. (0,1): b0=0,b1=1 -> x0=1. (1,0): b1=1,b0=0 -> y0=1. (1,1): b1=1,b1=1 -> x1 xor y1 = 0 xor 0 = 0. So D matrix would be [[0,1],[1,0]]. That's exactly our D. So consistent. So actually it's consistent. So no inconsistency.

    Now, find an inconsistent example: Need violation of condition like for i zero, D[i][j] not same across j ones. Or for j zero, D[i][j] not same across i ones. Or zero-zero not zero. Or (1,1) block not of form x_i xor y_j.

    For (1,1) block, suppose bar all ones. Then D must satisfy that for any i1,i2,j1,j2, D[i1][j1] xor D[i1][j2] xor D[i2][j1] xor D[i2][j2] = 0. That's the condition for being expressible as x_i xor y_j. Our verification with one reference will catch if not satisfied.

    Now, is there any condition we missed regarding the fact that x_i for zeros are forced by D[i][j] with j in ones, and y_j for zeros forced by D[i][j] with i in ones, and these might impose constraints on (1,1) block indirectly? For example, consider i in zeros and k in ones, j in ones: D[i][j] = x_i. Also D[k][j] = x_k xor y_j. But no relation between x_i and x_k. So no cross constraint.

    Thus algorithm stands.

    Now, let's test with a more complex scenario: N=3, bar=[1,0,1] (ones indices 0,2; zero index 1). Let's generate random x and y, compute D, then run algorithm.

    Pick x = [1,0,1] (x1 is zero because b[1]=0, but we'll compute later) Actually b[1]=0 so x1 is forced by D. But we can compute D from arbitrary x,y and then see if algorithm recovers some solution.

    First, we need to respect that for b[i]=0 (i=1), x1 must be equal to D[1][j] for any j in ones. So if we pick x1 arbitrarily, we must set D accordingly. Better to start with arbitrary x and y and compute D. But then x1 must equal D[1][j] (since b[1]=0). Let's compute D from arbitrary x and y, but we have to ensure that the condition holds, else D would not be consistent with some solution? Wait any D produced from some x,y automatically satisfies all constraints. So we can pick any x,y (with x1 determined by others? Actually x1 is free? In the equation D[1][j] = x1 * b_j + y_j * b_1. Since b_1=0, D[1][j] = x1 * b_j. b_j is 1 for j=0,2; 0 for j=1. So for j in ones, D[1][j] = x1. For j zero (j=1), D[1][1] = 0 (since both b's zero). So indeed x1 determines those entries. So if we pick x1 arbitrarily, D[1][j] for j in ones will be that value. So D will satisfy the condition. So we can choose arbitrary x and y.

    Let's pick x = [1,0,1] (but note for i=1 (zero) we set x1=0). y = [1,1,0] arbitrary. b = [1,0,1].

    Compute D: For each i,j: if b_i=1,b_j=1: D = x_i xor y_j. if b_i=1,b_j=0: D = y_j. if b_i=0,b_j=1: D = x_i. if b_i=0,b_j=0: D = 0.

    Let's compute:

    i=0 (b1), j=0 (b1): D00 = x0 xor y0 = 1 xor 1 = 0. i=0, j=1 (b0): b_i=1,b_j=0 => D01 = y1 = 1. i=0, j=2 (b1): D02 = x0 xor y2 = 1 xor 0 = 1. i=1 (b0), j=0 (b1): D10 = x1 = 0. i=1, j=1 (b0): D11 = 0. i=1, j=2 (b1): D12 = x1 = 0. i=2 (b1), j=0 (b1): D20 = x2 xor y0 = 1 xor 1 = 0. i=2, j=1 (b0): D21 = y1 = 1. i=2, j=2 (b1): D22 = x2 xor y2 = 1 xor 0 = 1.

    So D matrix: [0,1,1] [0,0,0] [0,1,1]

    Now run algorithm.

    bar ones=[0,2], zeros=[1].

    Check zero-zero: i=1,j=1 => D[1][1]=0 ok.

    Rows i zeros: i=1. j0 = ones[0]=0 => expected = D[1][0]=0. Check j in ones: j=0 => D[1][0]=0; j=2 => D[1][2]=0 => consistent. So x[1]=0.

    Columns j zeros: j=1. i0 = ones[0]=0 => expected = D[0][1]=1. Check i in ones: i=0 => D[0][1]=1; i=2 => D[2][1]=1 => consistent. So y[1]=1.

    Now ones: i0 = 0 (choose first). x[0] = 0 (choice). Then y[0] = D[0][0] = 0; y[2] = D[0][2] = 1. Now compute other x: j0 = ones[0] = 0. For i=2: x[2] = D[2][0] ^ y[0] = D[2][0]=0 ^ 0 = 0. Now verification: i=0: x0=0; y0=0 => D00=0 ok; y2=1 => D02 should be 1, actual=1 ok. i=2: x2=0; y0=0 => D20=0 ok; y2=1 => D22 should be 1, actual=1 ok. Thus solution: x=[0,0,0], y=[0,1,1]. (But we also have y[1]=1 from earlier). So y=[0,1,1]. Compare to original y=[1,1,0]? Different but still valid because we found another solution: x all zeros, y for ones: 0,1? Actually our derived y: y0=0, y1=1, y2=1. Original y was [1,1,0]. But both satisfy D? Let's check with x all zeros: D from these: For (0,0): b1,b1 => 0 xor 0=0; (0,1): b1,b0 => y1=1; (0,2): 0 xor 1=1; (1,0): b0,b1 => x1=0; (1,1):0; (1,2): x1=0; (2,0): x2 xor y0 =0; (2,1): y1=1; (2,2): x2 xor y2 =0 xor1=1. Yes matches D. So algorithm found a valid solution. Good.

    Thus algorithm works.

    Now, confirm that we never assign x[i] or y[j] multiple times inconsistently. For i in zeros we set x[i]. For i in ones we set x[i] in the ones block. No overlap. For y similarly.

    Now, for some edge case: if ones list is nonempty, but there might be some i in zeros that we haven't set x because we used ones[0] but if zeros list is empty, fine.

    Now, we need to ensure that after setting y for ones, we didn't override any y that were set earlier for zeros. But ones and zeros are disjoint. So fine.

    Now, output: we need to output M and then operations. We'll iterate over x and y.

    Now, one more nuance: The bar's orientation is left-to-right for rows, top-to-bottom for columns. Our equations assume that bar pattern for row i is bar[j] (same across rows) and for column j is bar[i] (same across columns). That's correct.

    Now, is there any possibility that the same solution could require applying a row and column on the same index multiple times? Not needed.

    Now, we must consider that operations are applied sequentially, and they can be applied in any order. The final result is XOR of all applied patterns. Since XOR is commutative and associative, order does not matter.

    Now, what about the possibility that the bar pattern length N is given as a string of length N, but what about if it has spaces? No.

    Now, we have to ensure that we respect the limit M ≤ 10^5. For N ≤ 2000, sum(x)+sum(y) ≤ 4000, so ok.

    Now, implement.

    But we need to be careful about performance: The double loops over ones and zeros may be expensive if we use Python's list comprehension each time inside loops. We'll use local variables for speed.

    Potential issues: In the check for zero-zero, we do for i in zeros: row = D[i]; for j in zeros: if row[j]: ... This may be heavy if zeros is large (like 2000), that's 4 million checks. That's okay.

    But we need to be careful to avoid using Python's built-in all with generator over 4 million, but we are using explicit loops, which is fine.

    Now, consider using memoryviews or numpy? Not needed.

    Now, we might also consider early exit if inconsistency found to save time.

    Now, final implementation.

    Now, let's test with given examples by running mental simulation.

    Example 1: we already did, returns -1.

    Example 2: we got M=1 col0 or row0 depending on choice. The problem accepts any. So if we output col0, that's valid. But the example output says row0. But it's okay because problem says any. However, we might want to match the example? No need. Our code might output col0. That's fine.

    But what if the judge expects any correct solution? Usually they accept any.

    Now, example 3: we got M=1 col1. That's also correct. So output may differ.

    Now, we need to make sure we don't produce M=0 when there is a solution with M>0? M=0 is also a solution if initial == desired? But not necessarily minimal; any solution is allowed.

    Now, one more test: N=2000 with all ones bar, and D constructed from random x,y; our algorithm should find solution.

    Now, check potential bug: In ones block, we set y[j] = D[i0][j] ^ x[i0] (with x[i0]=0). But what if we later compute x[i] using j0 and y[j0]? That's fine. However, note that for i0, we have x[i0]=0, and y[j0] = D[i0][j0] ^ 0 = D[i0][j0]. So x[i0] ^ y[j0] = D[i0][j0] obviously. Good.

    Now, verification step will check all pairs; but we might have a situation where for some i, j, D[i][j] does not equal xi ^ yj, but we missed because we only set xi using j0 and assume it works for others. But we verify all, so if any fails, we declare impossible.

    Now, note: In the verification step we also check i0 against all j, which is fine.

    Now, after verification, we have solution.

    Now, what about the case where ones list is empty? Already handled.

    Now, double-check the condition for zero-zero: For i with b[i]=0, j with b[j]=0, we require D[i][j]=0. This is necessary. Is it also automatically implied by other conditions? Not necessarily, so we must check.

    Now, consider if zeros list is large; we are doing nested loops, which is okay.

    Now, we might want to precompute D rows as bytearray for faster indexing.

    Now, implementation details:

    • We'll use if row[j]: for checking non-zero because row[j] is 0 or 1.

    • When we set x[i] = expected, expected is 0 or 1 from D[i][j0]; it's int.

    • For XOR: we can use ^ operator.

    Now, final code.

    But there is one more nuance: The bar pattern is given as a string of length N. However, in our derivation, we used bar bits for both rows and columns. That's correct.

    Now, we must also consider that the bar pattern might be something like "010". It's fine.

    Now, after solving, we output the operations. But we need to output "col X" or "row X" with X 0-based. We'll output rows first then columns.

    Now, potential pitfalls: The input may contain extra spaces or newline at the end. Using split() handles.

    Now, test with custom case: N=1, bar=0, A=0, B=1. Then D=1, but bar all zeros -> we check all zeros and D not all zero -> print -1. Correct: impossible because operations do nothing.

    Now, test N=1, bar=0, A=0, B=0 -> D all zero -> output 0.

    Now, test N=1, bar=1, A=0, B=0 -> D=0 -> output 0 (since no operation needed). Or maybe we could apply row and column both to get zero? But 0 is fine.

    Now, test N=2, bar=11, A=00, B=11. D = 11; all ones? D[0][0]=1, etc. bar all ones, so zeros list empty. ones=[0,1]. We'll solve: pick i0=0, x0=0; then y0 = D[0][0]=1; y1 = D[0][1]=1. Then j0=0; compute x1 = D[1][0] ^ y0 = D[1][0]=1? D[1][0] = 1 (since D matrix all ones) -> 1 ^ 1 = 0. So x1=0. Then verify: x0^y0=1? Actually 0^1=1 matches D[0][0]=1; x0^y1=1 matches; x1^y0=0^1=1 matches; x1^y1=0^1=1 matches. So solution: x=[0,0], y=[1,1] -> apply col0 and col1. Starting from A=00, apply col0 (bar=11) to col0: rows become [1,0]? Actually col0 operation: for rows i, board[i][0] ^= bar[i]. bar[0]=1, bar[1]=1. So row0 col0: 0^1=1; row1 col0:0^1=1 -> board becomes [[1,0],[1,0]]. Then apply col1: same: row0 col1:0^1=1; row1 col1:0^1=1 -> board becomes [[1,1],[1,1]] = B. So works.

    Alternatively, could do row operations. So fine.

    Now, consider a case where bar has ones and zeros but zeros list nonempty and some D zero-zero not zero; algorithm catches.

    Now, let's check if we can simplify by not explicitly checking zero-zero if we later enforce other constraints? For example, if we enforce rows i zeros, columns j zeros, and the (1,1) block, does zero-zero automatically become zero? Not necessarily. Because zero-zero cells are not involved in any equation with x_i or y_j; they are required to be 0. So we must check.

    Now, are there any other cells we missed? b[i]=1,b[j]=0 and b[i]=0,b[j]=1 we checked.

    Now, we should also consider that the operations are XOR; the order of operations doesn't matter. So our binary solution is correct.

    Now, confirm that the solution we output is indeed a sequence of operations that transforms A to B. Since we built x and y from equations, final XOR of patterns should give D, so A XOR D = B, correct.

    Now, let's think about a scenario where multiple solutions exist. Our algorithm picks a specific one based on choice x_i0=0. That's fine.

    Now, we must ensure that we don't exceed M=1e5, but with N <= 2000, it's fine.

    Now, potential memory optimization: Instead of storing D as bytearray of N per row, we could store as list of ints? Bytearray is more compact.

    But Python's bytearray indexing returns integer (0-255). So row[j] gives an int. That's fine.

    Now, might there be any issue with using boolean XOR (^) with ints? No.

    Now, we should also consider if the bar pattern string length might be less than N? No.

    Now, final code.

    But before finalizing, double-check the indexing: bar pattern indices correspond to columns for row operations, and rows for column operations. In our equations, we used bar[j] for row contribution and bar[i] for column contribution. That's correct because when applying to row i, we use bar at column j; when applying to column j, we use bar at row i.

    Now, let's test with a random small N using brute force in mind. But we can't run code here; trust.

    Now, one more edge case: N=2000, bar all ones. Then zeros list empty, we skip zero-zero, rows zeros, columns zeros. Then we go to ones block with N=2000. Setting i0=0, x0=0, then loop over j (2000) to set y[j] = D[0][j]. That's O(N). Then compute x[i] for i=1..1999 using j0=0: O(N). Then verification double loop O(N^2) which is 4 million, okay. So fine.

    Now, we might consider early exiting verification if any mismatch, but still worst-case O(N^2).

    Now, about input reading: using sys.stdin.read().split() may treat each line as token. But if the lines have spaces? They don't. So it's safe.

    However, note that the input format may have blank lines between sections (like examples show). Using split() will ignore blank lines. So fine.

    Now, implement.

    Now, after printing -1, we should exit.

    Now, test with examples:

    Example 1 input:

    2 11 11 00 01 11

    Our code:

    N=2 A=["11","11"] B=["00","01"] bar="11" D: row0: 1^0=1, 1^0=1 => [1,1] row1: 1^0=1, 1^1=0 => [1,0] bar ones=[0,1], zeros=[]. Check zero-zero: none. Rows zeros: none. Columns zeros: none. Ones: i0=0, x0=0; y0=D[0][0]=1; y1=D[0][1]=1. j0=0; compute x1 = D[1][0] ^ y0 = 1 ^ 1 = 0. Verification: i=0: x0=0, y0=1 -> D00=1 OK; y1=1 -> D01=1 OK. i=1: x1=0, y0=1 -> D10=1 OK; y1=1 -> D11 should be 1, but D11=0 -> fail. So print -1. Matches.

    Example 2:

    2 10 00 00 00 10

    N=2 A=["10","00"]; B=["00","00"]; bar="10" D: row0: 1^0=1,0^0=0 => [1,0] row1: 0^0=0,0^0=0 => [0,0] bar: [1,0] => ones=[0], zeros=[1] Check zero-zero: i=1,j=1 => D[1][1]=0 OK. Rows zeros: i=1, j0=0: expected = D[1][0]=0; check j in ones: only j=0 => D[1][0]=0 OK => x[1]=0. Columns zeros: j=1, i0=0: expected = D[0][1]=0; check i in ones: i=0 => D[0][1]=0 OK => y[1]=0. Ones: i0=0, set x0=0; y0 = D[0][0] = 1; verification: i0 only, j0 only? ones size 1, verification: i=0,j=0: D00=1, x0^y0=1 OK. So x=[0,0], y=[1,0]. Output M=1, col0. That's acceptable.

    But if we wanted row0, we could set x0=1 then y0=0, producing row0. But we choose 0.

    Now, example 3:

    3 110 011 100 100 011 100 100

    We computed D as: [0,1,0] [0,0,0] [0,0,0] bar="100" => ones=[0], zeros=[1,2]

    Check zero-zero: i=1,2; j=1,2 all D zero -> ok. Rows zeros: i=1: expected = D[1][0]=0; check j=0 (only) -> ok => x1=0. i=2: expected D[2][0]=0 -> ok => x2=0. Columns zeros: j=1: expected = D[0][1]=1; check i in ones: i=0 -> D[0][1]=1 ok => y1=1. j=2: expected = D[0][2]=0 -> D[0][2]=0 ok => y2=0. Ones: i0=0, set x0=0; y0 = D[0][0] = 0; verification: only one cell, ok. So x=[0,0,0], y=[0,1,0]? Wait y0=0, y1=1, y2=0 from earlier? But we set y0 from ones: y0=0. And we had y1=1,y2=0 from zeros. So y=[0,1,0]. Output: col1 only. M=1. That's valid.

    Thus all good.

    Now, let's think about potential overflow or errors: Using XOR on ints fine.

    Now, we also need to ensure that we don't mistakenly treat bar bits as bool when doing multiplication? But we used product implicitly: x_i * bar_j is just x_i if bar_j==1 else 0. Since we derived equations case by case, we didn't directly multiply; we used the cases. So fine.

    Now, consider the possibility that bar has both 0 and 1 but ones list is small; loops over ones are fine.

    Now, we should also consider that we may have D values not just 0/1 but from bytearray they are ints 0 or 1.

    Now, finalize.

    But I recall that the bar pattern is given as a string of length N. In our reading using split, if there are blank lines, the bar string may be at the end. Using split() will give tokens in order, so bar will be the last token after 2N board lines. So we need to ensure we read exactly N lines for A and N lines for B. If there are blank lines, split will ignore them, but the number of tokens might still be 2N+1? Actually if there are blank lines, they are empty strings? No, split() splits on any whitespace and returns non-whitespace tokens. So blank lines produce no tokens. So the sequence will be N, then N strings for A, then N strings for B, then one string for bar. So fine.

    But caution: The board lines may contain spaces? No, they are strings of 0/1 without spaces. So split works.

    However, if there are trailing spaces, split will also ignore.

    Thus we can read using:

    import sys

    def solve(): data = sys.stdin.read().split() if not data: return it = iter(data) N = int(next(it)) A = [next(it) for _ in range(N)] B = [next(it) for _ in range(N)] bar_str = next(it) ...

    But need to ensure that bar_str length N. If there are more tokens? Should not.

    Now, note: The lines may be given with spaces? Not.

    Now, finalize code.

    Now, test with a case where solution exists but with M=0.

    N=2, bar=10, A=00, B=00. D all zero.

    bar ones=[0], zeros=[1].

    Check zero-zero: i=1,j=1 D[1][1]=0 ok.

    Rows zeros: i=1: expected = D[1][0]=0, ok => x1=0. Columns zeros: j=1: expected = D[0][1]=0, ok => y1=0. Ones: i0=0, set x0=0; y0 = D[0][0]=0. Verification ok. x=[0,0], y=[0,0] -> M=0. Print 0.

    Works.

    Now, what about a case where bar=10, A=10, B=00, D row0: [1,0], row1: [0,0]. Then we get x1=0, y1=0, x0=0, y0=1 -> M=1 col0. That works: apply column0, starting from 10, column0 flips row0 col0 (1^1=0), row1 col0 (0^0=0) -> 00. Good.

    Now, check if we can handle large N with maximum recursion? Not.

    Now, ensure we output M and then lines. For M=0, we only print 0 (no extra lines). That's according to output format.

    Now, final code.

    But there is a catch: The bar pattern is given as "one string of length N". But in examples, for N=2, bar string "11" etc. So correct.

    Now, we must also consider that the output instructions may be "col X" or "row X". We'll output with lowercase? The examples use lowercase. Use "row" and "col". Ensure correct spelling.

    Now, edge-case: N=2000, bar all ones, and D matrix maybe all zeros? Then we will set x0=0, y=D[0][j]=0 for all j, then compute x_i = D[i][0] ^ y0 = 0, so all zeros, M=0. Good.

    Now, a nuance: In the case bar all ones, we don't have zeros, so the rows zeros and columns zeros steps are skipped. Then in ones block we set x_i and y_j. That covers all.

    Now, one more: bar all ones but D not of the form x_i xor y_j? Then verification fails, we output -1. Good.

    Now, what about bar with ones but zeros list nonempty but maybe zeros list includes indices where D[i][j] for j in ones are not consistent? We check.

    Now, all good.

    Now, we can also consider an alternative approach: treat the system as linear equations and solve via Gaussian elimination on 2N variables? That would be O(N^3) not possible.

    Our approach is efficient.

    Now, final code.

    But we must be careful: When we set x[i] for i in zeros, we used ones[0] to get expected. But we also need to check that for j in ones, D[i][j] is same. That's done.

    Now, we might want to precompute ones list and zeros list as lists of ints.

    Now, after obtaining x and y, we need to output. Note that we used 0-based indexing as required.

    Now, test with another custom case: N=3, bar=010, ones=[1], zeros=[0,2]. Construct D from some x,y. Let's pick x = [?, ?, ?] but we need to respect constraints: for i in zeros, x_i = D[i][1]; for i in ones, x1 free? Actually b[1]=1 so x1 appears in (1,1) block only? For j zero? b[j]=0, equation gives y_j = D[1][j] etc.

    Let's pick arbitrary: set x0=1 (zero index), x2=0 (zero index), x1=1. y0=0 (zero index), y2=1 (zero index), y1? (ones) free? Actually b[1]=1 so y1 is for ones.

    But we must compute D accordingly. Let's compute b=[0,1,0]. Set x = [1,1,0] (i=0,1,2) Set y = [0,? ,1] with y1 unknown; let's set y1=1. Now compute D: i=0(b0),j=0(b0) -> 0 i=0,j=1(b1) -> x0=1 i=0,j=2(b0) -> 0 i=1(b1),j=0(b0) -> y0=0 i=1,j=1(b1) -> x1 xor y1 = 1 xor 1 = 0 i=1,j=2(b0) -> y2=1 i=2(b0),j=0(b0) -> 0 i=2,j=1(b1) -> x2=0 i=2,j=2(b0) -> 0 So D matrix: [0,1,0] [0,0,1] [0,0,0]

    Now run algorithm:

    ones=[1], zeros=[0,2].

    Check zero-zero: i=0,2; j=0,2. Check D[0][0]=0; D[0][2]=0; D[2][0]=0; D[2][2]=0 OK.

    Rows zeros: i=0: expected = D[0][1] = 1. Check j in ones (only j=1) => consistent => x0=1. i=2: expected = D[2][1] = 0 => consistent => x2=0.

    Columns zeros: j=0: expected = D[1][0] = 0. Check i in ones (i=1) => D[1][0]=0 consistent => y0=0. j=2: expected = D[1][2] = 1. Check i in ones => D[1][2]=1 consistent => y2=1.

    Ones: i0=1, set x1=0 (choice). Then y1 = D[1][1] = 0. Verification: i=1,j=1: D[1][1]=0, x1^y1=0 OK. So we get x=[1,0,0] (since x0=1, x1=0, x2=0) and y=[0,0,1] (y0=0, y1=0, y2=1). Check if this satisfies D? Compute using x,y: i=0,j=1: x0=1 -> D01=1 correct; i=1,j=0: y0=0 -> D10=0 correct; i=1,j=2: y2=1 -> D12=1 correct; i=2,j=1: x2=0 -> D21=0 correct; all others zero. Indeed matches D. So solution found. Our original arbitrary solution had x1=1,y1=1, but we found a different one. Both valid.

    Now, consider a scenario where bar has ones and zeros but zeros list includes index that appears in both row and column. Already handled.

    Now, we should also think about the case where there is exactly one zero and many ones. That's fine.

    Now, we also need to handle the case where after we set x and y, we might have x_i or y_j that are None due to bug. But we covered.

    Now, double-check the steps for zeros: If zeros list is empty, loops skip.

    Now, confirm that after ones block, we have assigned all x and y. For rows with b[i]=0, we set x[i] in the zeros loop. For rows with b[i]=1, we set x[i] in ones block. So all rows set. Similarly for columns.

    Now, consider the possibility that we have a row i with b[i]=0 but there is no column j with b[j]=1? That would require ones list empty, which we handled separately. So in the case ones nonempty, for each i in zeros, there is at least one j in ones; thus we set x[i].

    Now, consider columns similarly.

    Thus all set.

    Now, we are ready to code.

    Now, I'll implement the solution in Python.

    After writing, test with the examples.

    Example 1 -> -1 Example 2 -> either 1 col0 or row0. Our code will output col0. Example 3 -> 1 col1.

    But because the problem allows any solution, it's fine.

    Now, potential improvements: We might want to avoid verification double loop if we trust the construction? But we need to check for consistency to detect impossible cases. Because if the matrix D is not of the required form, the verification will fail. So it's necessary.

    We can combine verification with construction to reduce loops, but it's fine.

    Now, one more nuance: In the ones block, we compute x[i] for i != i0 using j0. But if the ones list has size 1, then there is no other i. So we only have i0. Then we don't compute other x's. Verification will just check i0 against j0? Actually verification double loop will iterate i in ones (only i0) and j in ones (only j0). That's fine.

    Now, what about if ones list size > 1 but we compute x[i] using j0 and then verify all j. That's sufficient.

    Now, check if the verification will also catch issues if we had mis-assigned y[j]? Yes.

    Now, check if we need to also verify the (i, j) with i in ones and j in zeros? Already checked when we set y for zeros and verified consistency across i in ones. That ensures that for each j zero, all i in ones have D[i][j] = y_j. But we haven't re-checked after we set x_i? But those equations do not involve x_i. So they remain satisfied.

    Similarly for i in zeros, j in ones, we checked consistency across j, but after setting y_j maybe? Actually those equations are D[i][j] = x_i, and we set x_i from those, and verified consistency across j. They don't depend on y_j. So fine.

    Now, we could also re-check all cells at the end, but it's not needed.

    Now, implement.

    Now, think about the problem constraints: N up to 2000, so N^2 = 4e6. In Python, double nested loops of 4e6 may take around 0.2-0.5 seconds if optimized, maybe up to 1 second. But we have multiple such loops, so total maybe a few seconds. We need to be efficient. Possibly we can combine some checks.

    But 4 million is not huge; typical Python can do about 50-100 million simple operations per second? Actually Python is slower: ~30-50 million integer operations per second? Actually loops with indexing might be slower. For 4 million, it's okay. We have maybe 3-4 passes of 4 million => up to 16 million operations, which should be fine under 2 seconds.

    But we need to be careful with Python overhead in nested loops over lists of ints and accessing D[i][j]. Using bytearray may be efficient.

    We can also use for loops with local variables.

    Let's attempt to write efficient loops:

    • For zero-zero check: zeros_list = zeros D_local = D for i in zeros_list: row = D_local[i] for j in zeros_list: if row[j]: print(-1); return

    • For rows with b[i]==0: ones_list = ones for i in zeros_list: row = D[i] expected = row[ones_list[0]] for j in ones_list: if row[j] != expected: print(-1); return x[i] = expected

    • For columns with b[j]==0: for j in zeros_list: expected = D[ones_list[0]][j] for i in ones_list: if D[i][j] != expected: print(-1); return y[j] = expected

    • For ones: we already have loops.

    Now, note that in columns check we access D[i][j] many times. Could precompute column-wise? But not necessary.

    Now, implement.

    Now, about using ^ operator on ints: It's fast.

    Now, additional micro-optimizations: Store ones_list[0] as i0_ref for rows and columns? We used ones[0] multiple times.

    Now, for the ones block:

    i0 = ones[0] x[i0] = 0

    set y

    for j in ones: y[j] = D[i0][j] # because x[i0]=0

    compute other x

    j0 = ones[0] y_j0 = y[j0] for i in ones: if i != i0: x[i] = D[i][j0] ^ y_j0

    verification

    for i in ones: xi = x[i] row_i = D[i] for j in ones: if row_i[j] != (xi ^ y[j]): print(-1); return

    This is efficient.

    Now, note that in verification we can break early if mismatch.

    Now, after that, we output.

    Now, we also need to consider if we need to check that the found x and y are within 0/1, they are.

    Now, final code.

    One more nuance: The bar pattern might have length N, but maybe there are extra spaces? Using split() ensures we get the tokens.

    Now, I'll produce final answer.

    But before finalizing, let's test with a custom case that could be tricky.

    Consider N=3, bar=[1,1,0] (ones=[0,1], zeros=[2]). Suppose we want to test a scenario where the (1,1) block fails the condition. For example, let D be: We'll construct D not satisfying the condition. For i=0,1 and j=0,1, set D arbitrary not of the form xi xor yj. For zeros parts, we set appropriately to avoid earlier inconsistency. How? For rows i=2 (zero), we need D[2][0] and D[2][1] equal to x2, and D[2][2]=0. So set D[2][0]=a, D[2][1]=a (consistent), D[2][2]=0. For columns j=2 (zero), we need D[0][2] and D[1][2] equal to y2, so set them equal. And zero-zero: D[2][2]=0.

    Now, for (1,1) block, choose values that don't satisfy the rank condition: e.g., D[0][0]=0, D[0][1]=0, D[1][0]=0, D[1][1]=1. This fails because 0 xor 0 xor 0 xor 1 = 1, not 0.

    Now, run algorithm:

    ones=[0,1], zeros=[2].

    Check zero-zero: i=2,j=2 => D[2][2]=0 OK.

    Rows zeros: i=2: expected = D[2][0] = a; check j in ones: D[2][0]=a, D[2][1]=a => consistent => x2=a.

    Columns zeros: j=2: expected = D[0][2] = some value b; check i in ones: D[0][2]=b, D[1][2]=b => consistent => y2=b.

    Now ones: i0=0, set x0=0; y0 = D[0][0] = 0; y1 = D[0][1] = 0? Actually D[0][1]=0 so y1=0. Now j0=0, y_j0=0. Compute x1 = D[1][0] ^ y_j0 = 0 ^ 0 = 0. Now verification: i=0: x0=0, y0=0 => D00=0 OK; y1=0 => D01=0 OK. i=1: x1=0, y0=0 => D10=0 OK; y1=0 => D11 should be 0 but D11=1 -> mismatch. So prints -1. Good.

    Thus detection works.

    Now, consider a case where zeros list is nonempty but the rows zeros consistency check fails. For example, bar=[1,0], ones=[0], zeros=[1]. Let D[1][0] = 0, but D[1][? only one j] okay. But if we had more than one one? Actually ones size 1, so no conflict. To cause conflict, need bar with at least two ones. For example, bar=[1,1,0] (ones=[0,1], zeros=[2]). For i=2 (zero), if D[2][0] != D[2][1], then rows zeros check fails. So algorithm catches.

    Now, confirm that we didn't forget to check columns zeros for consistency across ones. Already do.

    Thus algorithm seems sound.

    Now, one more thought: Could there be a scenario where the solution exists but our arbitrary assignment of x_i0 = 0 leads to a contradiction? No, because if a solution exists, then any choice of c (global flip) yields a valid solution. Setting x_i0=0 corresponds to picking one of the two possibilities. So it will work.

    Proof: Suppose there exists a solution (x*, y*). For indices in S, define c = x*[i0] (since x*[i0] is either 0 or 1). Then (x' = x* XOR c, y' = y* XOR c) also satisfies the equations for S,T, and has x'[i0] = 0. Additionally, for zeros, x_i are uniquely determined and must match either x* or maybe different? For i in zeros, x_i is forced by D[i][j] = x_i, and that must equal (x*_i * b_j) XOR (y*_j * b_i) = x*_i because b_i=0. So x_i = x*_i. So the zero x_i are fixed and cannot be flipped. However, if we try to apply the global flip to the entire (S,T) set, it does not affect zeros. So the solution with x'[i0]=0 is simply (x* with possible flip on S,T) if the flip constant c = x*[i0]. That solution still satisfies all equations because flipping all x_i (i∈S) and y_j (j∈T) preserves (1,1) equations, and does not affect zero equations. So it's valid. So our choice of x_i0=0 yields a valid solution if any exists. Good.

    Now, final code.

    Potential issues: In the columns zeros check, we use expected = D[ones[0]][j]. But what if ones[0] index is not defined? ones nonempty, so fine.

    Now, ensure that we handle the case where N=0? N≥1.

    Now, finalize.

    One more check: When we set y[j] for j in ones, we use D[i0][j]. But what if D[i0][j] is not 0/1? It is.

    Now, also need to think about the possibility of overflow in loops: No.

    Now, test with random small N using brute-force: We could write a small test harness but not now.

    Now, I'll code.

    Potential improvements: Use sys.stdout.write for faster output if many lines, but M ≤ 4000, so print is fine.

    Now, code.

    Let's write the solve() function and call it.

    Now, final answer.

    But before concluding, I'll think about any misinterpretation of the problem: The magical bar can be placed on any row or column, orientation left-to-right or top-to-bottom. We assumed that the bar pattern is used as given for rows (left-to-right) and for columns (top-to-bottom). That seems correct.

    But is there any restriction that the bar must be placed entirely on the board? That's automatically satisfied if we place on a row/column.

    Also, the lights of the magical bar never change. So the bar pattern is fixed.

    Thus our model is correct.

    Now, the transformation: if the light on the magical bar is the same as the light on the square board it will switch the light off, otherwise on. That's XOR.

    Thus everything consistent.

    Now, the answer.

    Now, I'll produce final code.

    But one more nuance: In input, the strings may be given without spaces, but there might be a blank line between sections. As we use split, it's fine.

    Now, final code:

    import sys
    
    def main():
        data = sys.stdin.read().split()
        if not data:
            return
        it = iter(data)
        N = int(next(it))
        A = [next(it) for _ in range(N)]
        B = [next(it) for _ in range(N)]
        bar_str = next(it)
        # Compute delta matrix D as bytearray rows
        D = [bytearray(N) for _ in range(N)]
        for i in range(N):
            a_row = A[i]
            b_row = B[i]
            d_row = D[i]
            for j in range(N):
                # d = 1 if bits differ
                d_row[j] = (a_row[j] != b_row[j])
        # bar pattern as list of ints
        bar = [1 if ch == '1' else 0 for ch in bar_str]
        ones = [idx for idx, val in enumerate(bar) if val == 1]
        zeros = [idx for idx, val in enumerate(bar) if val == 0]
    
        # Case: bar all zeros
        if not ones:
            # operations do nothing; must have D all zero
            for i in range(N):
                if any(D[i][j] for j in range(N)):
                    print(-1)
                    return
            print(0)
            return
    
        # Check cells where bar[i]==0 and bar[j]==0: must be 0
        for i in zeros:
            row = D[i]
            for j in zeros:
                if row[j]:
                    print(-1)
                    return
    
        x = [None] * N
        y = [None] * N
    
        # Determine x for rows with bar[i]==0
        for i in zeros:
            expected = D[i][ones[0]]
            for j in ones:
                if D[i][j] != expected:
                    print(-1)
                    return
            x[i] = expected
    
        # Determine y for columns with bar[j]==0
        for j in zeros:
            expected = D[ones[0]][j]
            for i in ones:
                if D[i][j] != expected:
                    print(-1)
                    return
            y[j] = expected
    
        # Solve for indices where bar == 1
        i0 = ones[0]
        x[i0] = 0  # arbitrary choice
        # set y for ones
        for j in ones:
            y[j] = D[i0][j]  # since x[i0] = 0
        # compute x for remaining ones
        j0 = ones[0]
        y_j0 = y[j0]
        for i in ones:
            if i == i0:
                continue
            x[i] = D[i][j0] ^ y_j0
        # verify the (1,1) block
        for i in ones:
            xi = x[i]
            row_i = D[i]
            for j in ones:
                if row_i[j] != (xi ^ y[j]):
                    print(-1)
                    return
    
        # Now we have a solution
        M = sum(xi for xi in x if xi) + sum(yj for yj in y if yj)
        print(M)
        for i, val in enumerate(x):
            if val:
                print(f"row {i}")
        for j, val in enumerate(y):
            if val:
                print(f"col {j}")
    
    if __name__ == "__main__":
        main()
    

    Now, this should pass.

    But we must confirm that in the output we print "col X" and "row X" exactly as in examples. Good.

    Now, check the case where M=0: we print only "0". That's correct.

    Now, final answer.

    But maybe we can further optimize by using early exit in loops. Already we return on first failure.

    Now, consider reading input with sys.stdin.buffer.read().split() might convert bytes to strings using default encoding? Actually sys.stdin.read() returns string; but using .split() on string splits on whitespace and returns list of strings. That's fine. However, for large input, reading as string may be okay.

    But we might want to use sys.stdin.buffer.read().split() which returns list of bytes. Then we need to decode numbers. For simplicity, we can use sys.stdin.read().

    But for speed, using bytes might be slightly faster, but not necessary.

    Let's keep as is.

    Now, final answer.

    Now, we need to produce the solution explanation as well? The user asks "For her birthday Alice..." They likely want code.

    So final output: Python code.

    But before finalizing, test with a few more cases mentally.

    Case: N=2, bar=11, A=01, B=10. D = [0^1? Actually A=01 -> row0:0,1; B=10 -> row0:1,0 => D00=1, D01=1; row1: A=?? Actually need A and B both 2 lines. Let's define: A: row0=01, row1=10; B: row0=10, row1=01. So D: row0: 0^1=1, 1^0=1 -> [1,1]; row1: 1^0=1, 0^1=1 -> [1,1]. So D all ones. bar all ones. Solve: ones=[0,1], zeros=[]. i0=0, x0=0; y0=D[0][0]=1; y1=D[0][1]=1; j0=0; compute x1 = D[1][0] ^ y0 = 1^1=0; verify: all good. x=[0,0], y=[1,1] => apply col0 and col1. Check transformation: Starting A=01,10? Actually A: [[0,1],[1,0]]. Apply col0 (bar=11): column0: row0:0^1=1, row1:1^1=0 => board becomes [[1,1],[0,0]]? Wait row0 col0 becomes 1, row1 col0 becomes 0, row0 col1 unchanged 1, row1 col1 unchanged 0 => [[1,1],[0,0]]. Then apply col1: column1: row0:1^1=0, row1:0^1=1 => [[1,0],[0,1]]? Actually after col1: row0 col1: 1^1=0, row1 col1: 0^1=1 -> board becomes [[1,0],[0,1]] which is B? B is [[1,0],[0,1]]? Wait B was row0=10, row1=01 => [[1,0],[0,1]]. Yes matches. So works.

    Now, if we had chosen x0=1, then y0=0, y1=0, x1 = D[1][0]^y0=1^0=1; solution x=[1,1], y=[0,0] => rows operations. Also works.

    Thus fine.

    Now, final code.

    But I see a potential bug: In the verification for (1,1) block, we used row_i[j] != (xi ^ y[j]). This works because xi and y[j] are ints. Good.

    Now, also note that in the columns zeros check we used D[ones[0]][j]. But what if ones[0] is not defined? We already ensured ones nonempty. Good.

    Now, confirm that we used for i in zeros: for rows zeros, and for columns zeros we used for j in zeros:. That's correct.

    Now, about the case where zeros list is empty, we skip those loops. Good.

    Now, final answer.

    But perhaps we should also consider that the bar pattern could be given with spaces? No.

    Now, I'll finalize.

    But before concluding, let's test with a tricky scenario: N=2000, bar has exactly one 1. Then ones size=1, zeros size=1999. The algorithm:

    • zero-zero check: loops over zeros (1999) twice => ~4 million checks. Good.

    • rows zeros: loop over zeros (1999), for each check over ones (1) -> 1999 checks. Good.

    • columns zeros: similar 1999 checks.

    • ones block: ones size=1: set x[i0]=0; set y for ones (1); compute other x (none); verification double loop over ones size 1: trivial.

    So total operations ~4M + 4k, fine.

    Now, if bar has half ones half zeros, loops are roughly N^2/4 each, still O(N^2).

    Now, memory: D as list of bytearray of length N each: total ~N*N bytes = 4MB. Good.

    Now, done.

    Now, I'll output final answer code. ```python

    import sys

    def solve() -> None: data = sys.stdin.read().split() if not data: return it = iter(data) N = int(next(it))

    # read boards
    A = [next(it) for _ in range(N)]
    B = [next(it) for _ in range(N)]
    bar_str = next(it)
    
    # delta matrix D = A xor B
    D = [bytearray(N) for _ in range(N)]
    for i in range(N):
        a = A[i]
        b = B[i]
        row = D[i]
        for j in range(N):
            row[j] = (a[j] != b[j])          # 1 if different
    
    # bar pattern
    bar = [1 if ch == '1' else 0 for ch in bar_str]
    ones = [idx for idx, v in enumerate(bar) if v == 1]
    zeros = [idx for idx, v in enumerate(bar) if v == 0]
    
    # ----- bar all zeros -----
    if not ones:
        # operations do nothing, D must be all zero
        for i in range(N):
            if any(D[i][j] for j in range(N)):
                print(-1)
                return
        print(0)
        return
    
    # ----- check cells with bar[i]=0, bar[j]=0 -----
    for i in zeros:
        row = D[i]
        for j in zeros:
            if row[j]:
                print(-1)
                return
    
    x = [None] * N
    y = [None] * N
    
    # ----- rows with bar[i] = 0 -----
    for i in zeros:
        expected = D[i][ones[0]]
        for j in ones:
            if D[i][j] != expected:
                print(-1)
                return
        x[i] = expected
    
    # ----- columns with bar[j] = 0 -----
    for j in zeros:
        expected = D[ones[0]][j]
        for i in ones:
            if D[i][j] != expected:
                print(-1)
                return
        y[j] = expected
    
    # ----- solve for indices where bar = 1 -----
    i0 = ones[0]
    x[i0] = 0                     # arbitrary choice, the other possibility is 1
    for j in ones:
        y[j] = D[i0][j]           # because x[i0] = 0
    j0 = ones[0]
    yj0 = y[j0]
    for i in ones:
        if i == i0:
            continue
        x[i] = D[i][j0] ^ yj0
    
    # verify the (1,1) block
    for i in ones:
        xi = x[i]
        row_i = D[i]
        for j in ones:
            if row_i[j] != (xi ^ y[j]):
                print(-1)
                return
    
    # ----- output -----
    M = sum(v for v in x if v) + sum(v for v in y if v)
    print(M)
    for i, v in enumerate(x):
        if v:
            print(f"row {i}")
    for j, v in enumerate(y):
        if v:
            print(f"col {j}")
    

    if name == "main": solve()