Snake is a video game where a 'snake' attempts to maneuver around a game board in an attempt to collect the most amount of fruit possible (by passing the fruit over with the 'head' of the snake). At any given time there is only one fruit on the game board, when the fruit is collected the length of the snake increases by ~1~ and a new fruit gets added to the game board in a random location. The game is lost when the snake either collides with the edge of the game board, an obstacle, or itself. The game is won when the snake reaches a length equal to the number of empty spaces on the game board (it grows into itself and the game ends).

Given a ~N~ by ~M~ snake board where empty spaces are denoted by . and obstacles are denoted by # can the snake reach a length where it completely fills all the blank spaces at once?

Note that the snake can only move forward (from the snake's perspective) or turn left/right.

Input Specification

The first line contains two integers ~N~ and ~M~, ~(1 \le N, M \le 6)~, the height and width of the snake board respectively.

The next ~N~ lines will consist of ~M~ . or # characters (or a combination thereof), the game board.

Output Specification

A single line containing Chomp! if it is possible to win a game with the given board. Otherwise output Sadge..

Subtasks

Subtask 1 (5%)

There are no obstacles.

Subtask 2 (95%)

No further constraints.

Sample Input 1

5 6
...#..
.#.#..
.#.#..
.#....
......

Sample Output 1

Chomp!

Sample Input 2

5 6
......
......
..#...
.#.#..
......

Sample Output 2

Sadge.

It is recommended that you play at least one game of snake before attempting to solve this problem.