월리를 찾아라

「월리를 찾아라(Where's Wally)」라는 유명한 아동 도서 시리즈를 아는가? 각 책에는 수백 명의 사람이 등장하는 다양한 그림이 담겨 있고, 독자는 그 군중 속에서 월리라는 인물을 찾아야 한다.

「월리를 찾아라」는 이차원 그래픽 이미지에 대한 일종의 패턴 매칭이라고 볼 수 있다. 그림 속에서 월리의 모습을 찾는 것이다. 「월리를 찾아라」를 푸는 컴퓨터 프로그램을 작성하면 흥미롭겠지만, 그림 속 월리의 모습이 조금씩 다를 수 있어 쉬운 일이 아니다. 그래서 그 생각은 접고 문제를 훨씬 풀기 쉽게 바꾸었다. 여러분은 이 그래픽 패턴 매칭 문제의 더 쉬운 버전을 풀면 된다.

이미지 하나와 패턴 하나가 주어진다. 둘 다 비트로 이루어진 직사각형 행렬이다(단, 패턴은 항상 정사각형이다). $0$은 흰색, $1$은 검은색을 뜻한다. 이 문제에서는 이미지 안에 패턴이 몇 번 나타나는지, 즉 패턴과 정확히 일치하는 정사각형 영역이 이미지 안에 몇 개 있는지를 센다. $90$도의 배수만큼 회전하거나, 뒤집어서 거울상이 된 형태로 나타나는 패턴도 모두 고려해야 한다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

w h p
이미지 데이터
패턴 데이터

데이터셋의 첫째 줄에는 세 양의 정수 $w$, $h$, $p$가 주어진다. $w$는 이미지의 너비, $h$는 이미지의 높이이며, 둘 다 비트 수로 센다. $p$는 패턴의 너비이자 높이로, 패턴은 항상 정사각형이다. $1 \le w \le 1000$, $1 \le h \le 1000$, $1 \le p \le 100$이라고 가정해도 된다.

이어지는 $h$개의 줄은 이미지를 나타낸다. 각 줄은 $\lceil w/6 \rceil$개($\lfloor (w + 5)/6 \rfloor$과 같다)의 문자로 이루어지며, 이미지의 한 가로줄에 대응한다. 각 문자는 이미지 한 줄의 여섯 비트를 왼쪽에서 오른쪽 순서로 나타내며, BASE64 인코딩의 변형 방식을 따른다. 인코딩 규칙은 아래 표와 같다. 표에 있는 값의 최상위 비트가 이미지의 가장 왼쪽 비트에 대응한다. 마지막 문자는 이미지 너비를 넘어서는 몇 개의 비트를 나타낼 수도 있는데, 이 비트들은 무시해야 한다.

마지막 $p$개의 줄은 패턴을 나타낸다. 각 줄은 $\lceil p/6 \rceil$개의 문자로 이루어지며, 이미지와 같은 방식으로 인코딩된다.

세 개의 $0$으로 이루어진 줄은 입력의 끝을 나타낸다. 입력 전체의 크기는 $2$메가바이트를 넘지 않는다.

입력의 각 데이터셋에 대해, 이미지 안에서 일치하는 정사각형의 개수를 한 줄에 출력한다. 출력 줄에는 다른 문자가 포함되어서는 안 된다.

일치하는 정사각형 두 개 이상이 서로 겹칠 수 있다. 이 경우에는 각각 따로 센다. 반면, 하나의 정사각형은 예를 들어 원래 패턴과 그 회전 형태 모두에 일치하더라도 두 번 이상 세지 않는다.