32960번 - 문자 인식

문제

사진은 높이 $n$과 너비 $m$의 0ドル$과 1ドル$로만 이뤄진 이차원 격자이다.

당신은 어떤 사진에 포함된 글자를 모두 찾으려고 한다. 각 글자를 표현하는 $K$개의 사진과, 글자를 추출할 사진이 주어질 때, 해당 사진에 포함된 글자의 집합 $S$를 구하여라.

높이가 $N,ドル 너비가 $M$인 어떤 사진 $A$와 높이가 $n_i,ドル 너비가 $m_i$인 글자 $B_i$가 있을 때, 사진 $A$에 글자 $B_i$가 포함되어 있다는 것은 1ドル \le p \le N - n_i + 1,ドル 1ドル \le q \le M - m_i + 1$인 어떤 정수 $p,ドル $q$가 존재하여 1ドル \le r \le n_i,ドル 1ドル \le s \le m_i$인 가능한 모든 $(r, s)$ 정수 쌍에 대해 $A[p + r - 1][q + s - 1] = B_i[r][s]$를 만족한다는 것을 의미한다.

입력

첫 번째 줄에 $K$가 주어진다. (1ドル \le K \le 250,000円$)

두 번째 줄부터 $K$개의 글자 사진이 차례대로 주어진다. 이 때 $i$번째로 주어지는 사진의 번호는 $i$이다. 사진의 입력 형식은 다음과 같다. 첫 번째 줄에 사진의 높이 $n_i$과 너비 $m_i$이 차례대로 주어지고, 두 번째 줄부터 $n_i$개의 줄에 걸쳐 0ドル$과 1ドル$로만 이뤄진 길이 $m_i$의 문자열이 주어진다. (1ドル \le n_i, m_i \le 250,000円;$ $\displaystyle\sum_{i=1}^{K}{n_i \times m_i} \le 250,000円$)

이후 글자를 추출할 사진이 주어진다. 사진의 입력 형식은 다음과 같다. 첫 번째 줄에 사진의 높이 $N$과 너비 $M$이 차례대로 주어지고, 두 번째 줄부터 $N$개의 줄에 걸쳐 0ドル$과 1ドル$로만 이뤄진 길이 $M$의 문자열이 주어진다. (1ドル \le N, M \le 250,000円;$ $N \times M \le 250,000円$)

서로 다른 글자가 같은 사진으로 표현될 수 있다. 따라서, 동일한 사진이 여러 개 주어질 수 있음에 주의하라.

출력

첫 번째 줄에 집합의 크기 $|S|$를 출력한다. (0ドル \le \lvert S \rvert \le K$)

두 번째 줄에 집합에 포함된 글자의 번호를 오름차순으로 출력한다.

제한

노트