필터

데이터베이스 엔진 ICPC(Instant Compression and Processing Codec)는 사용자 활동 기록을 저장한다. 기록마다 정수 사용자 식별자가 하나씩 붙는다. 기록은 압축된 데이터 파일에 들어 있고, 한 파일에 여러 사용자의 기록이 섞여 있을 수 있다. 파일을 압축 해제하는 데 CPU 시간이 많이 들기 때문에, 엔진은 파일을 읽기 전에 그 파일에 특정 사용자의 기록이 있을 가능성이 있는지를 적은 비용으로 판별해야 한다.

엔진은 이 판별을 블룸 필터로 한다. 데이터베이스마다 다음 정수 매개변수를 고정한다.

• $m$: 필터의 비트 수
• $f$: 해시 함수의 개수
• $a_i$ ($0 \le i < f$): $i$번 해시 함수의 곱수

데이터 파일마다 $m$비트 벡터인 필터 값이 하나씩 있다. 필터 값의 $j$번 비트($0 \le j < m$)가 1인 것은, 그 파일에 어떤 사용자 식별자 $u_k$의 기록이 있고 어떤 해시 함수 $i$($0 \le i < f$)에 대해

$j = (u_k \times a_i) \bmod m$

이 성립하는 것과 같다.

파일에 사용자 식별자 $u_k$의 기록이 있을 가능성이 있다는 것은, 모든 $i$($0 \le i < f$)에 대해 그 파일 필터 값의 $(u_k \times a_i) \bmod m$번 비트가 1이라는 것과 같다.

필터 매개변수, 각 데이터 파일의 필터 값, 질의 사용자 식별자 집합이 주어진다. 질의 집합의 식별자 가운데 적어도 하나의 기록이 있을 가능성이 있는 데이터 파일을 모두 구하라.

첫째 줄에 필터 매개변수 $m$, $f$와 $a_i$ ($0 \le i < f$)가 주어진다 ($1 \le m \le 1000$, $1 \le f \le 100$, $1 \le a_i < 2^{31}$).

둘째 줄에 데이터 파일의 개수 $n$이 주어진다 ($1 \le n \le 1000$). 이어지는 $n$개 줄에는 각 데이터 파일의 필터 값이 16진수로 주어진다. 필터 값은 0123456789abcdef 중의 문자 정확히 $\lceil m/4 \rceil$개로 이루어진 문자열이다. 첫 번째 문자는 필터 값의 0번부터 3번 비트를 담고, 16진수 한 자리의 최하위 비트부터 최상위 비트 순서로 놓인다. 두 번째 문자는 4번부터 7번 비트, 세 번째 문자는 8번부터 11번 비트를 담고, 그다음도 같은 방식이다. $m \bmod 4 \ne 0$이면 마지막 문자는 남은 $m \bmod 4$개 비트를 최하위 비트부터 담고, 나머지 비트는 0이다.

다음 줄에 질의에 포함된 사용자 식별자의 개수 $q$ ($1 \le q \le 1000$)와 서로 다른 식별자 $q$개 $u_k$ ($1 \le u_k < 2^{31}$)가 주어진다.

한 줄에 질의 집합의 식별자 가운데 적어도 하나의 기록이 있을 가능성이 있는 데이터 파일의 개수 $s$를 출력하고, 이어서 그 파일의 0부터 시작하는 번호 $d_t$ ($0 \le d_t < n$)를 증가하는 순서로 출력한다. 줄 안의 모든 수는 공백 하나로 구분한다. $s = 0$이면 $0$만 출력한다.