Balcony of the Castle

Time limit2sMemory limit1024 MB

Summary

Given a w by l grid with blocked cells and two start cells, decide whether the king and queen can meet directly, with one 1x3 balcony on the outer border, or not at all.

Level: Medium5 of 10
Topics: Matrix, BFS, Implementation
Solved: No attempts yet

Problem

The king and queen of the Personal Kingdom live, as is proper, in a beautiful castle. The top floor has a view of the whole kingdom, and the couple set up their apartments there. The top floor is one rectangular room $w$ meters wide and $l$ meters long, so it consists of $w \times l$ cells.

The queen's mother, the king's mother-in-law, is a fairy. What else would a fairy do in a small kingdom, even a personal one? She tests the feelings of the couple!

One day, while the king and queen were on the top floor apart from each other, the fairy put barriers on some cells of the floor and blocked the stairs leading off the floor. Simply put, the fairy turned the floor into a maze, and now the king and queen must find each other in it to show their love. If they fail, the calm and pleasant evenings they share will be replaced by hours of lectures.

What can save them from this horror? First, an invention of the castle builders of the Personal Kingdom: the balcony. Current technology allows building one balcony of size $1 \times 3$ meters. The king can order a balcony built over three consecutive outer cells of the floor (either from top to bottom or from left to right) and break the walls between the balcony and those cells of the floor that the fairy did not block. Perhaps the passage formed by the castle balcony will help the couple meet.

Second, you. As programmers of the Personal Kingdom, tell the king what the result of his efforts can be.

Input

The first line contains two integers $w$ and $l$ ( $3 \le w, l \le 1000$ ), the width and length of the floor. Each of the next $w$ lines contains $l$ characters. The character . means a cell can be freely traversed, * means the fairy blocked the cell, and k and q mark the starting positions of the king and the queen.

Output

If the king can meet the queen without building a balcony, print That is not a problem. If only building a balcony helps them meet, print We can build a good balcony to be happy. If even building a balcony does not help them meet, print Good work, dear fairy.

Examples3

Example 1

Input

4 4
k...
****
.***
...q

Expected output

We can build a good balcony to be happy

Example 2

Input

4 4
k...
****
****
...q

Expected output

Good work, dear fairy

Example 3

Input

4 4
k...
.***
.***
...q

Expected output

That is not a problem