405041: GYM101745 F Yet Another Binary Matrix

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Yet Another Binary Matrixtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

For this problem, we will be working in the field mod 2.

Harry has a n × n binary matrix.

Let R denote some set of rows of this matrix, and C denote some set of columns of this matrix. Let W(P, Q) be a |P| by |Q| matrix, where the element in the i-th row and j-th column is equal to the element in the P[i]-th and Q[j]-th row of the given matrix. Notation S[i] means the i-th by value element of set S.

Harry has a subset of the row indices A, and a subset of column indices B.

He would like you to find a subset of column indices X such that the following conditions hold:

  1. X is disjoint from B.
  2. The rows of W(A, X + B) are linearly independent (see below for definition).
  3. The rows of W(R - A, C - X - B) are linearly independent.

If no solution exists, print -1. Otherwise, print any valid subset X.

A set of rows is called linearly independent if and only if there is no subset of rows that sums to a row with all zeros. Remember we are working mod 2, so for example, the rows [1, 0, 1], [1, 1, 0], [0, 1, 1] are not linearly independent since the sum of all these rows is zero. Informally, if we consider each row as a base-2 integer, there is no subset of them that xor to zero.

Input

The first line will contain three integers n, a and b (0 ≤ a, b ≤ n, 1 ≤ n ≤ 50).

The next line will contain a integers, the row indices A1, A2, ..., Aa (1 ≤ Ai ≤ n). These indices will be distinct. If a = 0, this line will be left blank.

The next line will contain b integers, the column indices of B1, B2, ..., Bb (1 ≤ Bi ≤ n). These indices will be distinct. If b = 0, this line will be left blank.

The next n lines will contain a binary string of length n, representing the binary matrix.

Output

If no solution exists, print -1.

Otherwise, on the first line, print an integer x, the size of your subset X (0 ≤ x ≤ n). The next line should contain x integers, the column indices of X. These indices must be distinct and disjoint from B.

ExamplesInput
3 1 0
2

001
010
101
Output
1
2
Input
2 1 0
1

11
10
Output
1
2
Input
2 0 0


11
11
Output
-1
Input
6 4 1
1 4 2 3
2
101010
010101
110000
001100
000001
100000
Output
3
3 4 5

加入题单

上一题 下一题 算法标签: