At the end on the right

You are walking in the street and, suddenly, you have a physiological urgency. You enter into a bar, and ask for the toilet. They answer “At the end on the right”. Will you know how to find it?

Your task is to write a program that reads several maps of bars, and for each one prints if there is any way that first goes from the bottom to the top at the end, and then on the right.

Input

The input consists of several cases separated by a line in white. Each case consists of two natural numbers $f$ and $c$, followed by $f$ rows with $c$ characters each one. A character |’.’| indicates a position which you can pass. A character |’X’| indicates a position which you cannot pass. The position at end on the right always has a |’.’|. The other positions of the right column always have a |’X’|. A special case with $f = c = 0$ indicates the end of the input.

Output

Your program must print a line for each bar: if there is any way at the end on the right, it must print “bufff”; otherwise, it must print “ui ui ui”.

Precondition

It is known that: $2 \le f \le 1000$, $2 \le c \le 1000$.

Author

Salvador Roura (en: Carlos Molina)

© Jutge.org, 2006–2025.