Problem Description

There is a grid of H * W squares. The square located in the $i$-th row (from the top, $1 \leq i \leq H$) and $j$-th column (from the left, $1 \leq j \leq W$) is referred to as square $ (i, j) $.
The square $ (i, j) $ is painted black if $ c_{i, j} $ = # and white if $ c_{i, j} $ = ..

The figure below is an example of a grid when $ H = 5 $ and $ W = 5 $.

Now, consider connecting $ 1,000,000,000 = 10^9 $ of these grids horizontally. For example, connecting the above grid horizontally $ 10^9 $ times would look like the following:

Square1001 wants to move from the top-left square $ (1, 1) $ to the bottom-right square $(H, 10^9 \times W)$ in this vast grid. However, he must move under the following conditions:

• He must move without passing through any black squares.
• From square $ (i, j) $, he can only move to square $ (i + 1, j) $ or square $ (i, j + 1) $.
• Moving outside the grid is not allowed.

Determine whether he can move according to these conditions.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ c_{1, 1} $$ c_{1, 2} $$ c_{1, 3} $...$ c_{1, W} $ $ c_{2, 1} $$ c_{2, 2} $$ c_{2, 3} $...$ c_{2, W} $ $ c_{3, 1} $$ c_{3, 2} $$ c_{3, 3} $...$ c_{3, W} $ ... $ c_{H, 1} $$ c_{H, 2} $$ c_{H, 3} $...$ c_{H, W} $

Output Format

Output Yay! if Square1001 can move from the top-left to the bottom-right square, otherwise output :(.

Sample Input and Output

Sample Input #1

1 3
...

Sample Output #1

Yay!

Sample Input #2

1 3
.#.

Sample Output #2

:(

Sample Input #3

3 3
.##
...
##.

Sample Output #3

Yay!

Sample Input #4

7 7
..###..
...#...
#.....#
##.#.##
#.....#
...#...
..###..

Sample Output #4

:(

Notes/Hints

Constraints

• $ H, W $ are integers between $ 1 $ and $ 100 $ inclusive.
• $ c_{i, j} $ is either # or ..
• $ c_{1, 1} $ is ..
• $ c_{H, W} $ is ..

Partial Points

This problem is divided into several sub-tasks, and you are considered to have solved a sub-task if you correctly answer all test cases for that sub-task.
The score of your submitted source code is the sum of the points for the sub-tasks you solved.

1. (60 points): $ H = 1 $
2. (130 points): $ H = 2 $
3. (210 points): No additional constraints.

Sample Explanation 1

The grid looks like this, and you can achieve the goal by moving as shown in the figure below.

Sample Explanation 2

In this case, it is impossible to achieve the goal. Moreover, it is not even possible to reach $ (1, 3) $!

Sample Explanation 3

You can achieve the goal by moving as shown in the figure below.

见题面 Input 部分

见题面 Output 部分