def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 M = int(input[idx]) idx += 1 # Read M configurations configs = [] for _ in range(M): mat = [] for _ in range(N): row = input[idx] idx += 1 mat.append(row) # Convert to bitmask bitmask = 0 for i in range(N): for j in range(N): if mat[i][j] == '#': pos = i * N + j bitmask |= (1 << pos) configs.append(bitmask) # Precompute all line flip vectors line_flips = [] # Rows for i in range(N): vec = 0 for j in range(N): pos = i * N + j vec |= (1 << pos) line_flips.append(vec) # Columns for j in range(N): vec = 0 for i in range(N): pos = i * N + j vec |= (1 << pos) line_flips.append(vec) # Diagonals (i + j = s, s from 0 to 2N-2) for s in range(2 * N - 1): vec = 0 for i in range(N): j = s - i if 0 <= j < N: pos = i * N + j vec |= (1 << pos) line_flips.append(vec) # Anti-diagonals (i - j = t, t from -(N-1) to N-1) for t in range(- (N - 1), N): vec = 0 for i in range(N): j = i - t if 0 <= j < N: pos = i * N + j vec |= (1 << pos) line_flips.append(vec) # Gaussian elimination to find basis basis = [] for vec in line_flips: v = vec for (pivot, b) in basis: if (v >> pivot) & 1: v ^= b if v != 0: # Find the first set bit pivot = 0 while (v >> pivot) & 1 == 0: pivot += 1 # Insert into basis in order insert_pos = 0 while insert_pos < len(basis) and basis[insert_pos][0] < pivot: insert_pos += 1 basis.insert(insert_pos, (pivot, v)) # Function to check if a vector is in the row space def is_in_span(vec): v = vec for (pivot, b) in basis: if (v >> pivot) & 1: v ^= b return v == 0 # Prepare the output output = [] for i in range(M): for j in range(i + 1, M): D = configs[i] ^ configs[j] if is_in_span(D): output.append('1') else: output.append('0') # Print the output count = 0 for i in range(M - 1): line = output[count : count + (M - 1 - i)] print(''.join(line)) count += (M - 1 - i) if __name__ == "__main__": main()