시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

The main room of your home is square, n×n feet. Unfortunately, the floor is dirty. You’re a college student, so you hate to clean! Rather than clean it, you buy an area rug s×s feet square to cover some of the dirty spots.

Consider all of the ways that you could place the s×s area rug in the n×n room so that all s×s square feet of it cover part of the floor, axis aligned (no rotation). How many ways are there to cover a certain number of dirty spots?

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.

Each test case will begin with a line with two space-separated integers n (1 ≤ n ≤ 1,000) and s (1 ≤ s ≤ min[n,100]), where n is the size of one side of the room, and s is the size of one side of the new area rug.

Each of the next n lines will have a string of exactly n characters, consisting only of ‘C’ (a clean spot on the floor) or ‘D’ (a dirty spot on the floor).

출력

For each count of dirty floor spots covered, from 0 to s2, if the number of ways of covering that many dirty spots with an area rug of size s×s is greater than 0, output the number of spots and the number of ways of covering them on a line, separated by a space. Output them in order, smallest number of dirty spots to largest.

예제 입력 1

10 5
DDDDDDDDDD
DCCCCCCCCD
DCCCCCCCCD
DCCCCCCCCD
DCCCCCCCCD
DCCCCCCCCD
DCCCCCCCCD
DCCCCCCCCD
DCCCCCCCCD
DDDDDDDDDD

예제 출력 1

0 16
5 16
9 4

In this example, there are 4 ways to cover 9 dirty spots (the corners), 16 ways to cover 5 dirty spots (the non-corner edges), and 16 ways to cover 0 dirty spots (the interior)