Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
71 - ZOJ Monthly, October 2008 - Snake
Super Snake

Time Limit: 1 Second      Memory Limit: 32768 KB      Special Judge

"Super Snake" is an old computer game. There are many versions, but all involve maneuvering a "snake" around the screen, trying to avoid running the snake into itself.

We'll simulate a very simplified version here. The game will be played on an infinite large board consisting of squares. The snake is initially a string of some connected squares. Connected squares are adjacent horizontally or vertically. In each second, The snake can move to adjacent squares, but will never move back on itself. Thus the only two squares occupied by the snake that change in any move are its head and tail. Note that the head of the snake can't move to the square just vacated by the snake's tail.

In a game, started from time 0, a snake of length 2 or more moves for t seconds and does'nt move to itself. Now consider all the squares that have ever been occupied by the snake in these t seconds. You are given the time interval these squares were occupied by the snake, and you will output the coordinates for these squares.

Input

There are multiple test cases (less than 1000). There are two parts for each case. The first part is one line with two integers N (2 <= N <= 20) and t (1 <= t <= 50), the number of squares that have ever been occupied by the snake in the game and the total time for the game. The second part consists with N lines. Each line consists of t characters. The ith character (0-based) is either 'Y' or 'N', represents whether the square is occupied by the snake in time i. Each line contains at least one 'Y' and at least one 'N'.

Output

For each case, first print "Case i:" where i is the case number (1-based) and then N lines each with two integers follow. The ith represent the x- and y- coordinate for the ith square in the output. All the coordinate you output must by non-negative and less than 100. If there are more than one possible coordinates set for the squares, you only need to output any one of them. You may assume that there is always at least one solution for each input.

Sample Input

7 5
YNNNN
YYNNN
YYYNN
NYYYN
NNYYY
NNNYY
NNNNY
4 5
YNYYY
NYYYN
YYNYY
YYYNY

Sample Output

Case 1:
0 0
0 1
0 2
0 3
0 4
0 5
0 6
Case 2:
0 1
0 0
1 1
1 0

Author: HANG, Hang
Submit    Status