테트리스 조각 세기

회전만 허용되는 다섯 가지 테트로미노 모양이 격자에 각각 몇 번 나타나는지 세는 문제로, 인접한 도형은 서로 다른 색을 가진다.

보통6구현그래프BFS완전 탐색아직 제출이 없습니다시간 제한1초메모리 제한64 MB

문제

이비차는 컴퓨터 게임을 만들고 있다. 지금까지 만든 부분은 테트리스 조각 다섯 종류를 격자에 놓는 기능이다. 조각은 격자에 놓기 전에 90도 단위로 원하는 횟수만큼 회전할 수 있고, 색을 칠할 수 있다. 뒤집기는 없다. 조각이 격자 밖으로 나가거나 이미 놓인 조각과 겹치면 놓을 수 없다.

다섯 가지 조각은 다음과 같다.

1번 조각2번 조각3번 조각4번 조각5번 조각

같은 그림을 문자로 적으면 아래와 같다. #는 조각이 차지하는 칸이다.

1번    2번     3번    4번    5번
##     ####    .##    ##.    .#.
##             ##.    .##    ###

3번 조각과 4번 조각은 서로 거울상이므로, 아무리 회전해도 겹치지 않는 서로 다른 조각이다.

이비차가 학교에 간 사이에 동생 마리차가 게임을 실행해서 조각을 마음대로 회전하고 색칠해 격자에 놓았다. 인접한 두 조각은 색이 서로 다르다. 두 조각은 변을 맞대고 있거나 꼭짓점만 닿아도 인접한 것으로 본다.

이비차가 돌아와 보니 동생이 놓은 조각이 그대로 남아 있다. 격자에 각 조각이 몇 개씩 놓여 있는지 구하라.

입력

첫째 줄에 격자의 행 개수 NN과 열 개수 MM이 주어진다 (1N,M101 \le N, M \le 10). 다음 NN개 줄에는 격자의 한 행이 MM개의 문자로 주어진다.

각 문자는 빈칸을 뜻하는 .이거나 조각의 일부를 뜻하는 영어 소문자다. 서로 다른 문자는 서로 다른 색을 뜻하고, 한 조각에 속한 네 칸은 모두 같은 문자다.

출력

정확히 다섯 줄을 출력한다. ii번째 줄에는 ii번 조각이 격자에 놓인 개수를 출력한다.

힌트

세 번째 예제의 격자를 그림으로 나타내면 다음과 같다.